题解 P2697 【宝石串】

· · 题解

【为美好的前缀和献上祝福】

可以认为G是-1，R是1，然后求一个前缀和s

如果s[i]==s[j]，那么j--->i这一整段，一定是一个和为0的区间，即红绿相等的稳定区间

为了让其长度最长，可以维护一个最小值num[i]表示i这个值第一次出现在什么地方

由于有负数，所以要统一+n

然后第一个0出现在序列一开始的地方（别忘了转化0）

以下是c艹的代码

【跟我一起对那个奇技淫巧的人竖中指，滑稽】

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
#define inf 1<<30
using namespace std;
int f[N],n,ans;
int num[2*N];
char a[N];
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    for(int i=1;i<=n;++i)
    {
        if(a[i]=='G') f[i]-=1;
        if(a[i]=='R') f[i]+=1;
    }
    for(int i=1;i<=2*n+2;++i) num[i]=inf;
    num[0+n+1]=0;
    for(int i=1;i<=n;++i)
    {
        f[i]+=f[i-1];
        num[f[i]+n+1]=min(i,num[f[i]+n+1]);
        ans=max(ans,i-num[f[i]+n+1]);
    }
    printf("%d",ans);
    return 0;
}