[CTSC2017]密钥

传送门：http://uoj.ac/problem/297

“无论哪场比赛，都要相信题目是水的”

这不仅是HNOI2018D2T3的教训，也是这题的教训，思维定势真的很可怕。

普及组水题，真是愧对CTSC的头衔。

A当作1，B当作-1，开个桶计数即可。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int M=;

 bool p[M];

 int cnt[M],A[M],B[M],seed,n,k,T,S,ans1,ans2,ans3;

 int getrand(){

     seed = ((seed * ) ^ ) % ;

     return seed;

 }

 void generateData(){

     scanf("%d%d%d",&k,&seed,&S);

     int t = ;

     n = k *  + ;

     memset(p, , sizeof(p));

     for (int i = ; i <= n; i++)

     {

         p[i] = (getrand() / ) % ;

         t += p[i];

     }

     int i = ;

     while (t > k)

     {

         while (p[i] == )

             i++;

         p[i] = ;

         t--;

     }

     while (t < k)

     {

         while (p[i] == )

             i++;

         p[i] = ;

         t++;

     }

 }

 int main(){

     freopen("cipher.in","r",stdin);

     freopen("cipher.out","w",stdout);

     generateData();

     rep(i,,n) p[i+n]=p[i];

     A[]=n+; rep(i,,n<<) A[i]=A[i-]+(p[i]?:-);

     rep(i,,n) if(p[i]) cnt[A[i]]++,T+=A[i]>A[];

     rep(i,,n){

         if(p[i]) T-=cnt[A[i]],cnt[A[i]]--; else T+=cnt[A[i]+];

         if(!p[i]){

             if(T==) ans1=i;

             if(T==S) ans2=i;

             if(T==k-S) ans3=i;

         }

         if (p[i]) cnt[A[i+n]]++,T+=A[i+n]>A[i];

     }

     printf("%d\n%d\n%d\n",ans1,ans2,ans3);

     return ;

 }