题解 「EZEC-6」游戏

- ### 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： ```cpp #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; } ```