[洛谷]P2697 宝石串(经典好题！)

思路：

对于一个类似的东西进行前缀和：

G R G G R G

G：1 1 2 3 3 4

R：0 1 1 1 2 2

差：1 0 1 2 1 2

所得关于差的数列，同样的数最左最右的位置差为一个答案，选取最大的答案即为解，注意为0特判位置即答案。

至于为什么，用前缀和的思想，同位差相等那么这段区间的差就相等，所以记录一个差的最早出现位置就行，注意负数溢出，加上一个常数便可。

ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int p[2*N],la=N,ans;
string s;
void solve() {cin>>s;int len=s.size();for(int i=1; i<=len; i++) {if(s[i-1]=='R')la++;else la--;if(p[la]==0)p[la]=i;else ans=max(ans,i-p[la]);if(la==N)ans=i;}cout<<ans<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t=1;
//	cin>>t;while(t--) {solve();}return 0;
}

over~