题解 P2697 【宝石串】

在想Peach · 2019-07-09 14:43:03 · 题解

C艹里算挺短的代码吧

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

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特判位置即答案。

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

code：

#include<iostream>
using namespace std;
string s;
int ans,p[2000005],last=1000000;
int main()
{
    cin>>s;
    for(int i=1;i<=s.length();i++){
        if(s[i-1]=='R')last++;
        else last--;
        if(!p[last])p[last]=i;
        else ans=max(ans,i-p[last]);
        if(last==1000000)ans=i;
    }
    cout<<ans<<endl;
}