自动搬运

查看原文

来自洛谷，原作者为

	asuldb 哭晕了喵

搬运于2025-08-24 21:52:31，当前版本为作者最后更新于2019-08-22 21:12:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

一个显然的暴力就是枚举$\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$的个数显然是相等的，等于这次前缀和“回归0”过程中的数的个数一半，其中所有$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;
}