2 条题解

  • 5
    @ 2023-12-23 13:46:05

    呜呜呜,蒟蒻根据洛谷上做此题的经验,写了个暴力,没想到没过,看了只能想正解了

    ACAC CodeCode

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 2e6 + 5;
    string s;
    int ans, f[MAXN], t = 1000000;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin >> s;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == 'R')
                t++;
            else
                t--;
            if (!f[t])
                f[t] = i + 1;
            else
                ans = max(ans, i + 1 - f[t]);
            if (t == 1000000)
                ans = i + 1;
        }
        cout << ans << endl;
        return 0;
    }
    
    • 0
      @ 2023-11-5 20:15:40

      把G看成1,R看成-1,题目即可转化成求最长的和为0的区间。枚举区间的右端点i,设1到i的前缀和为sum,用pos[x]数组表示前缀和为x的最小的位置,那么i对应的区间长度即为i-pos[sum],取所有情况的最大值即可。

      核心代码
      
      cin >> s;
      sum = n = s.size();
      s = " " + s;
      memset(pos, -1, sizeof(pos));
      pos[sum] = 0;
      for (int i = 1; i <= n; i++) {
          if (s[i] == 'G') {
              sum++;
          } else {
              sum--;
          }
          if (pos[sum] < 0) {
              pos[sum] = i;
          } else {
              ans = max(ans, i - pos[sum]);
          }
      }
      cout << ans;   
      
      • 1

      信息

      ID
      545
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      (无)
      递交数
      247
      已通过
      138
      上传者