[CTSC2017]密钥

红太狼 2023-10-11 04:49 10阅读 0赞

[题目][Link 1]

一个显然的暴力就是枚举\\(\\rm X\\)的位置，把\\(\\rm A\\)视为\\(1\\)，\\(\\rm B\\)视为\\(-1\\)，从这个位置开始求一遍前缀和，特征值即为所有前缀和大于\\(0\\)的\\(A\\)

我们对第一个空位置做一遍这个暴力，考虑一下\\(\\rm X\\)移动会对其他位置的前缀和产生什么样的影响

如果移动到的位置原来是一个\\(\\rm B\\)，相当于把这个\\(-1\\)放到了最后处理，于是前缀和数组整体\\(+1\\)

移动到的位置是一个\\(A\\)，那么除了这个\\(A\\)以外的前缀和少了最初的一个\\(+1\\)，整体\\(-1\\)，而\\(A\\)位置的前缀和再处理下一个位置的时候就变成了\\(pre\_n-pre\_i+pre\_i-1\\)，又因为\\(pre\_n=0\\)，所以变成了\\(-1\\)

于是我们维护一个桶，开一个指针表示当前\\(0\\)的位置，整体\\(+1,-1\\)可以直接移动指针，特殊修改直接结合当前指针的值在桶里修改即可

这样第一二问就做完了，第三问显然可以在用上述的方法模拟一遍，但是有这样一个结论，**一个\\(k\\)个\\(1\\)，\\(k\\)个\\(-1\\)组成序列，\\(k\\)个\\(1\\)中前缀和大于\\(0\\)的个数加上\\(k\\)个\\(-1\\)中前缀和小于\\(0\\)的个数等于\\(k\\)**

证明非常简单，当一个前缀和从\\(0\\)变大在变成\\(0\\)的过程中，\\(1\\)和\\(-1\\)的个数显然是相等的，等于这次前缀和“回归”的个数的一半，其中所有\\(1\\)的前缀和必然是大于\\(0\\)的：前缀和从\\(0\\)变小再变成\\(0\\)同理，所以这个结论是正确的

于是对于第三问，我们只需要判断一下当前前缀和大于\\(0\\)（在第三问中对应了所有\\(B\\)的前缀和小于\\(0\\)的个数）是否等于\\(k-S\\)即可

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    const int maxn=2e7+5;
    int p[maxn],pre[maxn],tax[maxn],np[maxn],id[maxn];
    int seed,n,k,S,tot,now,ans1,ans2,beg,ans3;
    inline int getrand() {
        seed=((seed*12321)^9999)%32768;
        return seed;
    }
    void generateData() {
        scanf("%d%d%d",&k,&seed,&S);
        int t=0;n=k*2+1;
        for( int i = 1; i <= n; ++i ) 
            p[i]=(getrand()/128)%2,t+=p[i];
        int i=1;
        while(t>k) {
            while(p[i]==0) ++i;
            p[i]=0;--t;
        }
        while(t<k) {
            while(p[i]==1) ++i;
            p[i]=1;++t;
        }
    }
    inline void calc(int pos) {
        if(tot==0) ans1=id[pos];
        if(tot==S) ans2=id[pos];
        if(tot==k-S) ans3=id[pos];
        if(ans1&&ans2&&ans3) {
            printf("%d\n%d\n%d\n",ans1,ans2,ans3);
            exit(0);
        }
    }
    int main() {
        generateData();
        for(re int i=1;i<=n;i++) if(!p[i]) {beg=i;break;}
        for(re int i=1;i<=n;i++) {
            id[i]=beg;np[i]=p[beg++];if(beg>n) beg=1;
        }
        for(re int i=2;i<=n;i++) pre[i]=(pre[i-1])+(np[i]?1:-1);
        for(re int i=2;i<=n;i++) if(np[i]) tax[pre[i]+k]++;
        for(re int i=k+1;i<=k+k;++i) tot+=tax[i];
        calc(1);now=k;
        for(re int i=2;i<=n;i++) 
            if(np[i]) ++now,tot-=tax[now],
                tax[pre[i]+k]--,tax[pre[i]+k-1]++;
            else tot+=tax[now],--now,calc(i);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11396887.html

[Link 1]: https://www.luogu.org/problem/P3770