2 条题解
-
5
呜呜呜,蒟蒻根据洛谷上做此题的经验,写了个暴力,没想到没过,看了只能想正解了
:
#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
把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
- 上传者