题解 「EZEC-6」游戏

· · 题解

略

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

设 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)。

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

设 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 通过调节阈值或设置多个阈值也可以通过。

以下同样基于数据较大。

设 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;
}