P2697 宝石串（前缀和 + 思维）

原题传送门：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;
}