原题传送门:P2697 宝石串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路
将 G 看作 1 , R 看作 -1 ,对序列进行前缀和,那么就可以很容易得到某一段序列的和,当某序列的和为 0 时,该序列长度就是可能的答案长度。
初始化last数组为-1,这个很重要。
将last[0]设为0。
只需要用last[x + n]记录下prefix[x]第一次出现的位置,然后不断更新答案即可。
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <algorithm> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define sc scanf #define pb push_back #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } /*--------全局变量--------*/ const int maxn = 1e6 + 10; char s[maxn]; int last[maxn * 2]; int prefix[maxn]; /*--------自定义函数-------*/ signed main() { cin >> s + 1; int len = strlen(s + 1); memset(last, -1, sizeof last); last[0 + len] = 0; int ans = 0; for(int i = 1;i <= len; ++ i) { if(s[i] == 'G')prefix[i] = prefix[i - 1] + 1; else if(s[i] == 'R')prefix[i] = prefix[i - 1] - 1; if(last[prefix[i] + len] == -1)last[prefix[i] + len] = i; ans = max(ans, i - last[prefix[i] + len]); } pr("%lld\n",ans); return 0; }
Comments NOTHING