题目 https://www.luogu.org/problem/P3770
一个显然的暴力就是枚举 \(\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;
- }
[CTSC2017] 密钥
来源: http://www.bubuko.com/infodetail-3166071.html