http://www.lydsy.com/JudgeOnline/problem.php?id=4236 我们的4.12模拟赛T2 直接把J个数-O个数还有O个数-I个数用hash存一下历史最早值 如果发现原本hash值已有说明符合答案要求直接求出长度取max即可 map也可以
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD1=1000007; const ll MOD2=1299709; char c[200001]; ll ha1[1000007][3]={0},ha2[1299709][3]={0}; inline ll h1(ll x,ll y){ ll xx=x+200000,yy=y+200000; ll i=(xx*MOD2%MOD1+yy%MOD1)%MOD1; while(ha1[i][0]&&(ha1[i][0]!=x||ha1[i][1]!=y))i=(i+1)%MOD1; return i; } inline ll h2(ll x,ll y){ ll xx=x+200000,yy=y+200000; ll i=(xx*MOD1%MOD2+yy%MOD2)%MOD2; while(ha2[i][0]&&(ha2[i][0]!=x||ha2[i][1]!=y))i=(i+1)%MOD2; return i; } int main() { ll n,J,O,I,ans;J=O=I=ans=0;scanf("%lld",&n); scanf("%s",c+1); for(int i=0;i<1000007;i++)ha1[i][2]=-1; for(int i=0;i<1299709;i++)ha2[i][2]=-1; int p1=h1(0,0),p2=h2(0,0); ha1[p1][2]=ha2[p2][2]=0; for(int i=1;i<=n;i++){ if(c[i]=='J')J++; if(c[i]=='O')O++; if(c[i]=='I')I++; p1=h1(J-O,O-I),p2=h2(J-O,O-I); if(ha1[p1][2]!=-1)ans=max(ans,i-ha1[p1][2]); else{ ha1[p1][0]=ha2[p2][0]=J-O; ha1[p1][1]=ha2[p2][1]=O-I; ha1[p1][2]=ha2[p2][2]=i; } } if(!ans)printf("0"); else printf("%lld",ans); return 0; }