自动搬运

查看原文

来自洛谷，原作者为

	Falashiro 丝之歌什么时候出

搬运于2025-08-24 22:29:23，当前版本为作者最后更新于2021-02-08 13:18:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• subtask 1

略

• subtask 2

最优轮数为 $n+m$，方案为 $ABAB\dots AB$ 或 $BABA\dots BA$，正确性显然。

• subtask 3

设 $N=n+m$，$M=\sum N$，

设 $f_{i,j}$ 表示第 $i$ 轮过后 Alice 能否恰好有 $j$ 个石子，需要保证 $0\le j\le N$，使得 Bob 的石子数也合法，

初始 $f_{0,n}=1$，如果对于某个 $i$ 和所有合法的 $j$ 都有 $f_{i,j}=0$，即无法进行到这一轮，最优轮数为 $i-1$，方案可以倒推得到，这个显然可以 $O(N^2)$ 转移。

总时间复杂度为 $O(M^2)$。

• subtask 4

使用 bitset 优化 subtask3 的做法，复杂度 $O(\frac{M^2}{\omega})$。

• subtask 5

设 $S=\lceil\sqrt{2N}\rceil$，

在数据较大时，通过 $1-S$ 的数的加减可以得到任何一个 $N$ 以内的正整数 $x$（在奇偶性满足的情况下），且运算途中值 $x$ 始终满足 $0\le x\le N$，

考虑在 $S$ 轮后获得一个状态，使得之后不断 $ABAB\dots AB$ 或 $BABA\dots BA$ 即可得到最优轮数，因为可以获得任何满足奇偶性的状态，所以若满足奇偶性，最优轮数为 $N$，否则为 $N-1$，

分类讨论并整合后可以得到，当 $abs(n-m)\equiv2\pmod4$ 时，答案为 $N-1$，否则答案为 $N$（注意结论只对大数据成立）。

若最优轮数为 $N$，最后 Alice 只可能有 $0$ 或 $N$ 个石子，
若最优轮数为 $N-1$，最后 Alice 只可能有 $0$，$1$，$N-1$ 或 $N$ 个石子，

钦定 $S$ 轮之后的方案为 $ABAB\dots AB$ 或 $BABA\dots BA$，可以根据答案轮数得到最后一轮后的状态，从而倒推出 $S$ 轮结束后 Alice 的石子数，

之后使用和 subtask4 相同的做法，但是只需要计算前 $S$ 轮的 $f$ 值即可，由于 $S$ 为 $\sqrt{N}$ 级别，单次复杂度为 $O(\frac{N\sqrt{N}}{\omega})$，总复杂度为 $O(\frac{M\sqrt{M}}{\omega})$。

对于小数据，可以直接采用 subtask4 的做法。

经实践，$N\ge18$ 时，关于最优轮数的结论成立。

注意，如果实现时 bitset 定长，则复杂度错误，为 $O(\frac{M\sqrt{MT}}{\omega})$，每次 $N=\frac{M}{T}$ 即可卡满，手写 bitset 可以达到正确的复杂度，如果不手写 bitset 通过调节阈值或设置多个阈值也可以通过。

• subtask 6

以下同样基于数据较大。

设 $S=6\lceil\sqrt{N}\rceil$，沿用 subtask5 部分做法，得到最优轮数，得到最后一轮的状态，钦定 $S$ 轮之后的方案，并倒推得到 $S$ 轮的状态，设当前状态 $S$ 轮结束后 Alice 有 $t$ 个石子。

考虑直接构造求解，设 $now$ 为当前 Alice 的石子数，为了方便，可以先用若干轮把 $now$ 减到尽量小，之后使用若干轮把 $now$ 加到尽量接近 $t$，此时需要分 $2$ 种情况讨论，一种是 $now\le t$，另一种是 $now>t$，这两种情况的奇偶性是不相同的，

因为 $\sum\limits_{i=1}^{\lceil2\sqrt{N}\rceil}i\ge2N$，所以此时 $now$ 和 $t$ 的差最多为 $\lceil2\sqrt{N}\rceil$，之后每次可以利用 $2$ 轮来使 $now$ 加 $1$ 或减 $1$，一直到 $now=t$ 为止，花费轮数最多为 $3\times\lceil2\sqrt{N}\rceil\le6\lceil\sqrt{N}\rceil$，即取 $S=6\lceil\sqrt{N}\rceil$ 一定足够，若当前轮数仍未到达 $S$，可以每次花费 $4$ 轮使 $now$ 加 $1$ 再减 $1$，若无法恰好用尽 $S$ 轮，本次构造失败，否则可以直接输出方案。

这些情况已经涵盖了所有 subtask5 对最优轮数的讨论 甚至还多了一些，在大数据下一定可以找到方案，时间复杂度为 $O(N)$。

接下来讨论这个做法的适用数据范围，在关于最优轮数的结论成立的情况下，只要保证 $n,m$ 合法即可，倒推到 $S$ 轮时 $n,m$ 的差约为 $S$（正负不超过 $2$），不妨设 $n\le m$，只要 $n\ge S$，就不会出现不合法情况，算上 $\lceil2\sqrt{N}\rceil$ 的步长，$N\ge 2(S+\lceil2\sqrt{N}\rceil)+m-n$ 时适用，$m-n\le S+2$，即 $N\ge 3S+4\lceil\sqrt{N}\rceil+2=22\lceil\sqrt{N}\rceil+2$，$N\ge23^2=529$ 时，做法适用。

在运算过程中多次把下界往大算，所以这个界非常松，但是没必要卡得更紧了，实际的下界约为 $300$ 多，若多进行一些分类讨论，可以做到 $100$ 多。

做法不适用时，使用 subtask4 的算法即可，此处增加的运算次数最多为 $T\times529\times\lceil\frac{529}{64}\rceil=4761000$，再乘上一些常数，显然可以接受。

忽略上述常数，总复杂度为 $O(M)$。

实现时，倒推可以 $O(1)$ 解决，使用 $O(N)$ 的算法也可以通过，只是常数略大。

code：

#include<bits/stdc++.h>
using namespace std;
#define N 20000005
#define M 529
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w*f;
}
int n,m,s,flag;
char ans[N];
bitset<M>f[M],base;
void get(int x,int y){
	if(!x)return;
	if(y-x>=0)
		if(f[x-1][y-x]){
			get(x-1,y-x);
			ans[x]='A';
			return;
		}
	if(y+x<=n+m)
		if(f[x-1][y+x]){
			get(x-1,y+x);
			ans[x]='B';
			return;
		}
}
void brute(){
	base.reset();
	for(int i=0;i<=n+m;i++)
		base[i]=1;
	f[0].reset();
	f[0][n]=1;
	for(int i=1;i<=n+m;i++)
		f[i]=(f[i-1]<<i|f[i-1]>>i)&base;
	for(int i=n+m;i>=0;i--){
		if(!f[i].any())continue;
		int x=0;
		for(int j=0;j<=n+m&&!x;j++)
			if(f[i][j])x=j;
		printf("%d\n",i);
		get(i,x);
		puts(ans+1);
		memset(ans+1,0,sizeof(char)*i);
		return;
	}
}
void add(int&x,int&y){
	ans[y]='A',x+=y,y++;
}
void sub(int&x,int&y){
	ans[y]='B',x-=y,y++;
}
void solve(int c,int f,int op){
	if(flag)return;
	int now=1,x=n,t=op&1?n+m-f:f;
	if(op&1)t-=(n+m-c-s)/2;
	else t+=(n+m-c-s)/2;
	if((n+m-c-s)&1){
		if((n+m-c-s-1+op)&1)t-=s+1;
		else t+=s+1;
	}
	while(x>=now)sub(x,now);
	if(op<=1){
		while(x+now<=t)add(x,now);
		while(x<t)sub(x,now),add(x,now);
	}
	else{
		while(x<=t)add(x,now);
		while(x>t)add(x,now),sub(x,now);
	}
	while(now<=s)sub(x,now),add(x,now),add(x,now),sub(x,now);
	if(now!=s+1)return;
	flag=1;
	for(int i=n+m-c;i>s;i--)
		if((n+m-c-i+op)&1)ans[i]='A';
		else ans[i]='B';
	printf("%d\n",n+m-c);
	puts(ans+1);
	memset(ans+1,0,sizeof(char)*(n+m-c));
}
signed main(){
	int T=read();
	while(T--){
		n=read(),m=read(),flag=0;
		if(n+m<M){
			brute();
			continue;
		}
		s=6*ceil(sqrt(n+m));
		if(((n-m)%4+4)%4==2){
			for(int i=0;i<4;i++)
				for(int k=0;k<2;k++)
					solve(1,k,i);
		}
		else{
			for(int i=0;i<4;i++)
				solve(0,0,i);
		}
	}
	return 0;
}