IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    BZOJ4236: JOIOJI

    wyfcyx发表于 2015-08-18 20:11:53
    love 0

    题解:

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

    如果这个串要满足$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;
    }


沪ICP备19023445号-2号
友情链接