BZOJ4236: JOIOJI

题解:

考虑任意一个串都是两个前缀之差.

如果这个串要满足$num(J)=num(O)=num(I)$,那么两个前缀$num(J),num(O),num(I)$的相对大小关系必须是相同的.

我们对于每个前缀记下$num(J)-num(O),num(J)-num(I)$,然后利用map随便搞搞就行了.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
typedef pair<int,int> pii;
#define mp make_pair
 
#define N 200010
char s[N];
 
map<pii,int>M;
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
     
    M[mp(0,0)]=0;
    int J=0,O=0,I=0,ans=0;
    for(int i=1;i<=n;++i){
        if(s[i]=='J')
            ++J;
        if(s[i]=='O')
            ++O;
        if(s[i]=='I')
            ++I;
        if(M.count(mp(J-O,J-I)))
            ans=max(ans,i-M[mp(J-O,J-I)]);
        else
            M[mp(J-O,J-I)]=i;
    }
    cout<<ans<<endl;
    return 0;
}