Powered by:NEFU AB-IN

Link

4261. 孤独的照片

• 题意

  Farmer John 最近购入了 N 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。
  奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。
  然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。
  在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。
  给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。
  如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。

• 思路

  因为要找的是所有孤独的牛的照片，找出当前这个点的左边相邻的连续不同的牛 * 右边的相邻连续不同的牛 + 左边的不同牛的长度 - 1 + 右边不同的牛的长度 - 1

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-12-27 18:48:47
  * @FilePath: \Acwing\4261\4261.cpp
  * @LastEditTime: 2023-01-01 11:34:16
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  // #undef int
  
  signed main()
  {
      IOS;
      string s;
      int n;
      cin >> n >> s;
  
      vector<int> l(n), r(n);
  
      int g = 0, h = 0;
      for (int i = 0; i < SZ(s); ++i)
      {
          if (s[i] == 'G')
              l[i] = h, h = 0, g++;
          else
              l[i] = g, g = 0, h++;
      }
      g = h = 0;
      for (int i = SZ(s) - 1; i >= 0; --i)
      {
          if (s[i] == 'G')
              r[i] = h, h = 0, g++;
          else
              r[i] = g, g = 0, h++;
      }
      int res = 0;
      for (int i = 0; i < SZ(s); ++i)
      {
          // cout << l[i] << " " << r[i] << '\n';
          res += (l[i] * r[i]) + max(l[i] - 1, 0LL) + max(r[i] - 1, 0LL);
      }
      cout << res;
      return 0;
  }