BZOJ4236: JOIOJI

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4236

Solution

我打了暴力莫名8分。
szb大佬的算法：
a表示第一种字符出现次数，b,c同上。
记录每个前缀b-a与c-a的值。
显然两个前缀b-a相等，那么这两个前缀相交部分一定有b=a
c-a也同理
要找出这样的一对前缀只需快排一遍就行了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 200005
using namespace std;
struct data{
    ll x,y,sum;
}f[N];
ll n,ans,a,b,c; char ch[N];
bool cmp(data x,data y){
    if (x.x!=y.x) return x.x<y.x;
    else if (x.y!=y.y) return x.y<y.y;
    else return x.sum<y.sum;
}
int main(){
    scanf("%d",&n); scanf("%s",ch+1);
    for (ll i=1;i<=n;i++){
        if (ch[i]=='J') a++;
        if (ch[i]=='O') b++;
        if (ch[i]=='I') c++;
        f[i+1].x=b-a; f[i+1].y=c-a; f[i+1].sum=i;
    }
    sort(f+1,f+n+2,cmp);
    for (ll i=1,j=1;i<=n+1;i=++j){
        while (j<n+1&&f[j+1].x==f[i].x&&f[j+1].y==f[i].y) j++;
        ans=max(ans,f[j].sum-f[i].sum);
    }
    printf("%d",ans);
}