浅谈博弈论

manboo · 2026-05-27 21:58:09 · 算法·理论

声明：本文用 \oplus 符号表示二进制下的按位异或。

1. 博弈入门

博弈，通俗地来说，就是几名参与者进行游戏，游戏有规则，参与者都很聪明，尽可能按照最优策略去决策，使得自己获得的收益更大。OI 里的博弈论，主要研究两名参与者如何决策。

博弈论有几个最重要的概念：

• 局面：任何一种可能出现的游戏情况（包括规则、道具（如石子）、轮到谁等），都属于某一种局面。局面是不可重的，相同的局面所得到的结果相同。

• 先手和后手：先手和后手通常并不指全局里的谁先走、谁后走，而是指在出现某一局面时，该谁走时，谁是先手，另一方是后手。先手和后手的概念，是基于某一局面的。

• 必胜、必败、平局：对于某一局面，如果先手有一种策略使得后手必败，那么先手就可以执行它，使得自己获胜。因此，称该局面为先手必胜，后手必败。如果不论先手怎样决策，后手都是必胜的，那么称该局面为先手必败，后手必胜。如果不论先手怎样决策，后手都不能必败，但存在平局，那么先手就可以执行它，使得平局，那么称该局面为平局。

博弈论有一些常见分类（可以选择不予了解）：

• 对称与非对称博弈：

  • 在对称博弈中，两个参与者面对相同的局面时，获得的收益相同。收益只取决于局面，与先手后手无关。反之，即为非对称博弈。

  • 例如，在同一段序列中取数，无论当前轮到先手还是后手，取相同的数时，收益都是相同的。而对于不同的序列，取数的收益也会不同，但是先后手面对同样的局面取同样的数的收益永远是相同的。

• 完美与不完美信息博弈：

  • 在完美信息博弈中，参与者在任意时刻决策时，了解历史局面及初局面。反之，即为不完美信息博弈。

  • 例如，取石子游戏通常是完美信息博弈，因为参与者知道双方取过多少石子，当前局面剩余多少石子；而多人斗地主是不完美信息博弈，因为参与者不知道对面手里是什么牌（那叫偷窥）。

• 公平与非公平博弈：

  • 在公平博弈中，所有参与者在某种局面的合法决策都相同，该决策仅取决于当前局面，与先手后手无关。同时，博弈中的某一局面不能多次出现，当且仅当参与者无法行动时结束，保证博弈一定会在有限步后以非平局结束。因此，公平博弈总是对称博弈。反之，在非公平博弈中，参与者在某种局面的合法决策与其先后手身份有关。

  • 这与对称博弈近似，对称博弈需要满足收益只与局面有关，而公平博弈需要满足合法决策只与局面有关。

我们 OIer 常见的博弈，通常指完美信息博弈与公平博弈。

下面我们通过几道例题来初步了解博弈。

P2734 [IOI 1996 / USACO3.3] 游戏 A Game

:::info[题解] 设 s_{i,j}=\sum\limits_{k=i}^j a_k 表示区间 \left[i,j\right] 的 a 值之和，f_{i,j} 表示区间 \left[i,j\right] 先手取的最大值，显然有：

也就是先手选左边得到 a_i，轮到后手在剩余的区间 \left[i+1,j\right] 里得到 f_{i+1,j}，先手得到剩余的 s_{i+1,j}-f_{i+1,j}；或者先手选右边，同理。

时间复杂度为 O(n^2)。 :::

:::success[代码]

const int N=105;
int n,a[N],s[N][N],f[N][N];
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int len=1;len<=n;len++)
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            s[i][j]=s[i][j-1]+a[j];
    for(int len=1;len<=n;len++)
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            f[i][j]=max(a[i]+s[i+1][j]-f[i+1][j],a[j]+s[i][j-1]-f[i][j-1]);
    print(f[1][n]),putchar(' '),print(s[1][n]-f[1][n]);
    return 0;
}

:::

AT_dp_k Stones

:::info[题解] 注意到 n,k 很小，设 f_i=0/1 表示当前有 i 个石子，先手必败（f=0）还是先手必胜（f=1）。显然，当且仅当对于全部的 a_j，都有 f_{i-a_j}=1 时，f_i=0（因为无论怎么取都会进入先手必胜状态，使得原本的后手必胜，先手必败）；否则，f_i=1（因为先手必然有一种取的方案进入先手必败状态，使得原本的后手必败）。

时间复杂度为 O(nk)。 :::

:::success[代码]

const int N=105,K=100005;
int n,k,a[N],f[K];
inline int ask(int x)
{
    for(int i=1;i<=n;i++) if(x>=a[i]&&!f[x-a[i]]) return 1;
    return 0;
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[0]=0;
    for(int i=1;i<=k;i++) f[i]=ask(i);
    puts(f[k]?"First":"Second");
    return 0;
}

:::

P1857 质数取石子

:::info[题解] 和上一题一样，把可取集合换成质数集合即可。 :::

:::success[代码]

const int N=20005;
bool not_prime[N];
int cnt,primes[N];
void get_prime(int P=N-5)
{
    not_prime[0]=not_prime[1]=1;
    for(int i=2;i<=P;i++)
    {
        if(!not_prime[i]) primes[++cnt]=i;
        for(int j=1;j<=cnt&&i*primes[j]<=P;j++)
        {
            not_prime[i*primes[j]]=1;
            if(i%primes[j]==0) break;
        }
    }
}
int n,f[N],g[N];
inline void init()
{
    memset(g,0x3f,sizeof(g));
    f[0]=g[0]=0;
    for(int x=1;x<=20000;x++)
    {
        for(int i=1;i<=cnt;i++)
            if(x>=primes[i]&&!f[x-primes[i]])
            {
                f[x]=1;
                g[x]=min(g[x],g[x-primes[i]]+1);
            }
        if(!f[x])
        {
            g[x]=0;
            for(int i=1;i<=cnt;i++)
                if(x>=primes[i]&&f[x-primes[i]])
                    g[x]=max(g[x],g[x-primes[i]]+1);
        }
    }
}
int main()
{
    get_prime(),init();
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        if(!f[x]) puts("-1");
        else print(g[x]),putchar('\n');
    }
    return 0;
}

:::

P4576 [CQOI2013] 棋盘游戏

:::info[题解] 设 f_{x,y,r_1,c_1,r_2,c_2} 表示当前执白棋（x=0）或黑棋（x=1），走了 y 步，白棋和黑棋分别到达 \left(r_1,c_1\right) 和 \left(r_2,c_2\right)，的最小步数。n\le 20 可以记忆化搜索。

不难发现，当且仅当白棋可以一步到达黑棋时，白棋必胜；否则，黑棋必胜。

按照题目要求，需要让黑棋尽快获胜，即步数最小；白棋拖延失败，即步数最大，模拟棋走哪里并转移即可，答案即为 f_{0,0,r_1,c_1,r_2,c_2}。 :::

:::success[代码]

const int N=21,dx[2][8]={{-1,0,1,0},{-1,-2,0,0,1,2,0,0}},dy[2][8]={{0,1,0,-1},{0,0,1,2,0,0,-1,-2}},INF=1e9;
int n,f[2][(N<<1)+N][N][N][N][N];
inline bool check(int r,int c){return r>=1&&r<=n&&c>=1&&c<=n;}
int dfs(int x,int y,int r1,int c1,int r2,int c2)
{
    if(y>3*n) return INF;
    if(f[x][y][r1][c1][r2][c2]) return f[x][y][r1][c1][r2][c2];
    if(r1==r2&&c1==c2) return (x?INF:0);
    int res;
    if(!x)
    {
        res=0;
        for(int i=0;i<4;i++) if(check(r1+dx[0][i],c1+dy[0][i]))  res=max(res,dfs(1,y+1,r1+dx[0][i],c1+dy[0][i],r2,c2));
    }
    else
    {
        res=INF;
        for(int i=0;i<8;i++) if(check(r2+dx[1][i],c2+dy[1][i])) res=min(res,dfs(0,y+1,r1,c1,r2+dx[1][i],c2+dy[1][i]));
    }
    return f[x][y][r1][c1][r2][c2]=++res;
}
int main()
{
    n=read();int r1=read(),c1=read(),r2=read(),c2=read();
    if(abs(r1-r2)+abs(c1-c2)==1) printf("WHITE 1\n");
    else printf("BLACK %d\n",dfs(0,0,r1,c1,r2,c2));
    return 0;
}

:::

P8818 [CSP-S 2022] 策略游戏

:::info[题解] 搓样例 样例怎么这么水，尝试手推。令 A_{positive},A_{negative} 分别表示 A 的正数部分、负数部分。

• 先手选择 0：

  • 无论后手取何值，答案为 0。

• 先手选择正数：

  • 当 \min B\ge0 时，先手选择 \max A_{positive}，后手选择 \min B，答案为 \max A_{positive}\cdot\min B。

  • 当 \min B<0 时，先手选择 \min A_{positive}，后手选择 \min B，答案为 \min A_{positive}\cdot\min B。

• 先手选择负数：

  • 当 \max B\ge0 时，先手选择 \max A_{negative}，后手选择 \max B，答案为 \max A_{negative}\cdot\max B。

  • 当 \max B<0 时，先手选择 \min A_{negative}，后手选择 \max B，答案为 \min A_{negative}\cdot\max B。

为了简化问题，我们将 A 中的 0 归到正数部分里，不会影响答案。

显然需要 倍增 st 表 线段树维护区间最大最小值，对 A 的正数部分、A 的负数部分、B 的整体分别维护即可。

时间复杂度为 O(q\log n)。 :::

:::success[代码]

const int N=100005,INF=2e9;
int n,m,q,a[N],b[N];
struct segment_tree
{
    int num[N],maxn[N<<2],minn[N<<2];
    inline void push_up(int x)
    {
        maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
        minn[x]=min(minn[x<<1],minn[x<<1|1]);
    }
    void build(int x,int l,int r)
    {
        if(l==r)
        {
            if(num[l]==INF) maxn[x]=-INF,minn[x]=INF;
            else maxn[x]=minn[x]=num[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        push_up(x);
    }
    int ask_max(int x,int l,int r,int tl,int tr)
    {
        if(tl<=l&&r<=tr) return maxn[x];
        int res=-INF,mid=(l+r)>>1;
        if(tl<=mid) res=max(res,ask_max(x<<1,l,mid,tl,tr));
        if(tr>mid) res=max(res,ask_max(x<<1|1,mid+1,r,tl,tr));
        return res;
    }
    int ask_min(int x,int l,int r,int tl,int tr)
    {
        if(tl<=l&&r<=tr) return minn[x];
        int res=INF,mid=(l+r)>>1;
        if(tl<=mid) res=min(res,ask_min(x<<1,l,mid,tl,tr));
        if(tr>mid) res=min(res,ask_min(x<<1|1,mid+1,r,tl,tr));
        return res;
    }
}ap,an,bl;  // ap 为 A 的非负数部分，an 为 A 的负数部分，bl 为 B 的整体 
int main()
{
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        if(a[i]>=0) ap.num[i]=a[i],an.num[i]=INF;
        else an.num[i]=a[i],ap.num[i]=INF;
    }
    for(int i=1;i<=m;i++) b[i]=read(),bl.num[i]=b[i];
    ap.build(1,1,n),an.build(1,1,n),bl.build(1,1,m);
    for(int i=1;i<=q;i++)
    {
        int la=read(),ra=read(),lb=read(),rb=read();
        int ap_max=ap.ask_max(1,1,n,la,ra),
            ap_min=ap.ask_min(1,1,n,la,ra),
            an_max=an.ask_max(1,1,n,la,ra),
            an_min=an.ask_min(1,1,n,la,ra);
        ll ans=-1ll*INF*INF;
        if(ap_min!=INF)
        {
            int bl_min=bl.ask_min(1,1,m,lb,rb);
            if(bl_min>=0) ans=max(ans,1ll*ap_max*bl_min);
            else ans=max(ans,1ll*ap_min*bl_min);
        }
        if(an_min!=INF)
        {
            int bl_max=bl.ask_max(1,1,m,lb,rb);
            if(bl_max>=0) ans=max(ans,1ll*an_max*bl_max);
            else ans=max(ans,1ll*an_min*bl_max);
        }
        print(ans),putchar('\n');
    }
    return 0;
}

:::

某师大附中国庆集训 day1-2. 取石子

:::info[原题及题解] 由于没有原题，这里给出原题：

有三堆石子，数量分别为 x,y,z\left(0\le x,y,z\le300\right)。两个人轮流取石子，每人每次可以选择若干堆石子，从中取出相同数量的石子扔掉（可以取完，不能不取），没石子可取的人输掉游戏。假设双方都非常聪明，请问先手是否必胜。

由于 x,y,z 范围很小，设 f_{i,j,k}=0/1 三堆石子的个数分别为 i,j,k 时，先手必败（f=0）或者先手必胜（f=1）。

枚举 S=1\sim8，即二进制下的 001\sim111，第 p 位的 1/0 表示第 p 堆石子选或不选，然后枚举取出的石子数 d。

发现这样做的时间复杂度堪忧，O(2^w n^4)，这里 w=3,n=300，显然不能通过这道题。

考虑优化。首先，钦定 i\le j\le k，那么 d 的范围就是 1\sim 300-i。那么在转移的时候，由 i,j,k 加至 x,y,z 后，设 p=\min\lbrace x,y,z\rbrace,q=\max\lbrace x,y,z\rbrace，需要向 f_{p,x+y+z-p-q,q} 转移。

最终的时间复杂度会除以一个很大的常数，足以通过本题。 :::

:::success[代码]

const int N=302;
int f[N][N][N];
inline void init()
{
    for(int i=0;i<=300;i++)
        for(int j=i;j<=300;j++)
            for(int k=j;k<=300;k++)
                if(!f[i][j][k])
                    for(int d=1;d<=300-i;d++)
                        for(int S=1;S<8;S++)
                        {
                            int x=i,y=j,z=k;
                            if(S>>2&1) x+=d;
                            if(S>>1&1)
                            {
                                y+=d;
                                if(y>300) continue;
                            }
                            if(S&1)
                            {
                                z+=d;
                                if(z>300) continue;
                            }
                            int p=min({x,y,z}),q=max({x,y,z});
                            f[p][x+y+z-p-q][q]=1;
                        }
}
int main()
{
    init();
    for(int T=read();T;T--)
    {
        vector<int> a;
        for(int i=1;i<=3;i++) a.push_back(read());
        sort(a.begin(),a.end());
        puts(f[a[0]][a[1]][a[2]]?"Yes":"No");
    }
    return 0;
}

:::

P2964 [USACO09NOV] A Coin Game S

:::info[题解] 设 s_{i,j}=\sum\limits_{k=i}^j a_k 表示区间 \left[i,j\right] 的 a 值之和，f_{i,j} 表示剩余 i\sim n，当前选择 j 个的先手最大价值。因为这次取完后，剩余 i+j\sim n，轮到后手，因此枚举后手下一步取的数量 k，由于 k 既要不大于 2\cdot j，又不能多于剩余的石子数 n-\left(i+j\right)+1，因此 k 的范围是 1\sim\min\left(2\cdot j,n-i-j+1\right)。

为了保证 f_{i+j,k} 有值，考虑从 n 到 1 倒序枚举 i，再从 1 到 n-i+1 正序枚举 j，答案为 \max\left(f_{1,1},f_{1,2}\right)，时间复杂度来到 O(n^3)。

考虑优化，维护 g_{i,j}=\max\limits_{k=1}^j\left(f_{i,k}\right)，则 f_{i,j}=s_n-s_{i-1}-g_{i+j,\min\left(2\cdot j,n-\left(i+j\right)+1\right)},g_{i,j}=\max\left(g_{i,j-1},f_{i,j}\right)，显然 f_{i,j} 不需要数组，只用临时变量即可，答案为 g_{1,2}。

时间复杂度为 O(n^2)。 :::

:::success[代码]

const int N=2005;
int n,f,a[N],s[N],g[N][N];
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
    for(int i=n;i;i--)
        for(int j=1;j<=n-i+1;j++)
        {
            f=s[n]-s[i-1]-g[i+j][min(j<<1,n-i-j+1)];
            g[i][j]=max(g[i][j-1],f);
        }
    print(g[1][2]);
    return 0;
}

:::

相信看到这里，你已经对博弈有初步的了解了，接下来我们进入博弈的常考题：Nim 游戏。

2. Nim 游戏

2.1 基础 Nim 游戏

规则：有 n 堆石子，数量分别为 a_1,a_2,\dots,a_n。两个人轮流取石子，每人每次可以从任意一堆石子里取出任意多个石子扔掉（可以取完，不能不取），没石子可取的人输掉游戏。假设双方都非常聪明，请问先手是否必胜。

结论：当且仅当 {\large\oplus}_{i=1}^n {a_i}=0 时，先手必败；否则先手必胜。

证明：设任意时刻的石子数异或和为 s。下文的“位”，表示某正整数在二进制下的“位”。

有以下定理：

:::info[定理一证明] 已知 s 此时为零。设先手选择一个非零数 a_i 使其减少正整数 x 至非负数，其它 a 值不变。

方法一：整体法。令 s_i 表示除 a_i 外的 a 值的异或和，即 s_i=a_1\oplus{a_2}\oplus\dots\oplus{a_{i-1}}\oplus{a_{i+1}}\oplus\dots\oplus{a_n}，则 s_i\oplus{a_i}=s=0，即 s_i=a_i。令 a_i'=a_i-x 表示新的 a_i，则 s_i\ne a_i'，故 s_i\oplus{a_i'}\ne0，即新的 s'=s_i\oplus{a_i'}\ne 0。

方法二：拆位法。由于 a_i 至少存在一位发生变化（否则，任何一位都不发生变化，a_i 就没有变化，这与“使 a_i 减少”矛盾），故设 a_i 的第 k 位发生变化（可能存在多个 k），则 s 的第 k 位必然发生变化，故新的 s 必然不为零。

由于以上基于任意 x 而非存在 x，故先手必然会使 s 变为非零数。 :::

:::info[定理二证明] 已知 s 此时非零。这里详细讲解拆位法。

设 s 为 1 的位集合为 K=\lbrace k_1,k_2,\dots,k_m\rbrace，不妨令 K 严格递增，则 s 为 1 的最高位为 k_1。

在所有第 k_1 位为 1 的 a 里，先手任选其中一个 a_i，使其第 k_1,k_2,\dots,k_m 位全部取反，其余位不变，得到 a_i'。

由于 a_i 的第 k_1 位必然为 1，故 a_i' 的第 k_1 位必然为 0，而在高于 k_1 位处，a_i 与 a_i' 相同，故 a_i'<a_i。

因此，必然存在一个正整数 x，使得先手令 a_i 减少 x 后，第 k_1,k_2,\dots,k_m 位全部发生变化，其余位不发生变化。

对于任意 k\in K，在所有 a 里，有奇数个 a 的第 k 位为 1，当 a_i 的第 k 位发生变化时，第 k 位为 1 的 a 的数量将变为偶数，因此 s 的第 k 位将变为 0；对于任意 k\not\in K，在所有 a 里，有偶数个 a 的第 k 位为 1，当 a_i 的第 k 位不发生变化时，第 k 位为 0 的 a 的数量仍保持偶数，因此 s 的第 k 位将保持 0。

由于以上基于存在 x 而非任意 x，故先手必然可以使 s 变为零。 :::

现在对局部局面分析。下文的“状态一”表示当前 s=0 的状态，“状态二”表示当前 s\ne0 的状态。

• 当前处于状态一。先手一定使 s 变为非零数，进入状态二。

• 当前处于状态二。先手可以使 s 变为零，进入状态一；可以使 s 保持非零数，保持状态二。

现在对整体局面分析。

• 当初始处于状态一时，假设后手优先进入状态一。先手一定进入状态二，后手选择进入状态一。那么先手只能继续进入状态二，后手继续选择进入状态一……由于游戏获胜当且仅当本次取完后的局面为 a_1=a_2=\cdots=a_n=0，处于状态一，而后手可以通过上述操作控制自己永远保持进入状态一，同时控制先手永远保持进入状态二而不进入状态一，故先手必败。

• 当初始处于状态二时，同理可得，先手控制自己永远保持进入状态一，同时控制后手永远保持进入状态二而不进入状态一，故先手必胜。

得证：当且仅当 {\large\oplus}_{i=1}^n {a_i}=0 时，先手必败；否则先手必胜。

P2197 【模板】Nim 游戏

:::info[题解] 模板题，不再赘述。 :::

:::success[代码]

const int N=10005;
int n,a[N];
inline void solve()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=a[i-1]^read();
    puts(a[n]?"Yes":"No");
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}

:::

「一本通 6.7 练习 2」巧克力棒

:::info[原题及题解] 由于没有原题，这里给出原题：

盒子里有 n\left(1\le n\le 14\right) 根巧克力棒，长度分别为 l_1,l_2,\dots,l_n\left(1\le l_i\le10^9\right)。小 A 和小 B 轮流操作：从盒子里取出若干根巧克力棒（如果取而不吃，盒子中必须存在至少一根，且至少取一根，可以取完），或者将一根取出的巧克力棒吃掉正整数长度（如果吃而不取，必须存在一根已取出、未被吃完的巧克力棒，且只能吃一根，可以吃完），无法操作的人输掉游戏。假设双方都非常聪明，小 A 先手，请问小 A 是否必胜，必胜输出 NO，必败输出 YES。10 组数据。

不难发现：

• 初始时，当盒子里存在若干根巧克力棒的长度异或和为零时：

  • 小 A 必然可以从盒子里取出最多的若干根巧克力棒，使其长度异或和为零。

  • 轮到小 B，根据基础 Nim 游戏的结论，小 B 不取新的巧克力棒时必输，因此小 B 只能取若干新的巧克力棒。

  • 由于剩余的巧克力棒中，不可能取出若干巧克力棒，使其长度异或和为零（否则小 A 可以把它们取出，这与最多的若干根巧克力棒矛盾），因此轮到小 A 时，巧克力棒的总异或和不为零，仍然是先手也就是小 A 必胜。

• 否则，即盒子里不存在若干根巧克力棒的长度异或和为零时：

  • 轮到小 B 时，巧克力棒的总异或和不为零，先手也就是小 B 必胜，小 A 必败。

现在只要判断盒子里是否存在若干根巧克力棒的长度异或和为零即可。这可以暴力枚举巧克力棒选择方案，时间复杂度为 O(2^n n)。 :::

:::success[代码]

int n,flag,maxS,a[15];
inline void solve()
{
    n=read(),flag=0,maxS=(1<<n);
    for(int i=0;i<n;i++) a[i]=read();
    for(int S=1;S<maxS;S++)
    {
        int XOR=0;
        for(int i=0;i<n;i++) if((S>>i)&1) XOR^=a[i];
        if(!XOR)
        {
            flag=1;
            break;
        }
    }
    puts(flag?"NO":"YES");
}
int main()
{
    for(int T=10;T;T--) solve();
    return 0;
}

:::

2.2 Bachet 游戏

规则：有 n 堆石子，数量分别为 a_1,a_2,\dots,a_n。两个人轮流取石子，每人每次可以从任意一堆石子里取出不多于 k 个石子扔掉（可以取完，不能不取），没石子可取的人输掉游戏。假设双方都非常聪明，请问先手是否必胜。

结论：令 b_i=a_i\bmod\left(k+1\right)，当且仅当 {\large\oplus}_{i=1}^n {b_i}=0 时，先手必败；否则先手必胜。

证明：对于一个石子数超过 k 的石子堆，先手扔掉其中 1\sim k 个石子，后手必然可以扔掉其中 1\sim k 个石子，使得两人扔掉的石子数之和为 k+1，由于又回到了先手，因此相当于直接在这一堆石子中抹除了 k+1 枚石子。

因此，对于所有石子数超过 k 的石子堆，都令其对 k+1 取模，不会对结果产生任何影响。

最终，所有石子数都不多于 k，这个限制最多取 k+1 个石子也就没用了，转换成基础 Nim 游戏。

得证：当且仅当 {\large\oplus}_{i=1}^n {b_i}=0 时，先手必败；否则先手必胜。

「一本通 6.7 例 1」取石子游戏 1

:::info[原题及题解] 由于没有原题，这里给出原题：

有一堆石子，数量为 n\left(1\le n\le 10^5\right)，两个人轮流取石子，每人每次可以从任意一堆石子里取出不多于 k\left(1\le k\le n\right) 个石子扔掉（可以取完，不能不取），没石子可取的人输掉游戏。假设双方都非常聪明，请问先手是必胜（输出 1）还是必败（输出 2）。

根据之前的结论，显然，当且仅当 n\bmod\left(k+1\right)=0 时，先手必败（先手取若干个，后手取相应数量个，使得双方共取 k+1 个，最终后手取完，先手必败）；否则，先手必胜。 :::

:::success[代码]

int main()
{
    int n=read(),k=read();
    if(n%(k+1)) puts("1");
    else puts("2");
    return 0;
}

:::

AT_arc168_b [ARC168B] Arbitrary Nim

:::info[题解]

• 当原异或和非零时，只要 k 足够大，就一定先手必胜，此时输出 -1。

• 当原异或和为零时，不难发现对于两堆数量相同的石子 i,j，先手在第 i 堆里取多少，后手同样可以在第 j 堆里取这么多，最终将两堆取完，回到先手，等价于直接抹除这两堆石子。因此，我们把石子数相同的石子堆两两抵消掉。同时，这对异或和没有影响，所以当前总异或和 s=0。

  • 如果不剩余石子堆，那么先手必败，输出 0。

  • 否则，设剩余的石子堆中最大的石子数为 g，若 k\ge g，相当于没有限制，仍为先手必败，因此 k<g。同时，k=g-1 是合法的，因为只要后手取了最大石子堆的石子，必然是取不完的，此时先手一定可以将其取完，相当于直接抹除最大石子堆。此时，剩余的石子堆总异或和 s'\ne 0，也就转换为对其余石子数少于 g 的石子堆进行基础 Nim 游戏，此时先手必胜。显然，g-1 就是最大的可取的 k，输出 g-1。 :::

:::success[代码]

int n,XOR;
set<int> s;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        XOR^=x;
        if(s.find(x)==s.end()) s.insert(x);
        else s.erase(x);
    }
    if(XOR) puts("-1");
    else
    {
        if(s.empty()) puts("0");
        else print((*s.rbegin())-1),putchar('\n');
    }
    return 0;
}

:::

2.3 阶梯 Nim 游戏

规则：从左到右依次有 n 堆石子，数量分别为 a_1,a_2,\dots,a_n。两个人轮流取石子，每人每次可以从任意一堆石子里取出任意多个石子移至其左边的石子堆中，或者从第一堆石子里取出任意多个石子扔掉（可以取完，不能不取），没石子可取的人输掉游戏。假设双方都非常聪明，请问先手是否必胜。

结论：阶梯 Nim 游戏与只看奇数堆的基础 Nim 游戏等价，当且仅当 a_1\oplus{a_3}\oplus{a_5}\oplus\dots=0 时，先手必败；否则先手必胜。

证明：正面推理较为困难，考虑从反面逆推，即证明不关注处于偶数堆的石子是正确的。

对局部局面分析：

• 先手将奇数堆的部分石子移至偶数堆。这等价于基础 Nim 游戏的“将取出的石子扔掉”操作。

• 先手将偶数堆的部分石子移至奇数堆，后手可以选择将该奇数堆的该部分石子移至下一个偶数堆（以及将第一堆的该部分石子扔掉），再次轮到先手。这等价于基础 Nim 游戏没有进行任何操作。

对整体局面分析，完全如上。因此，不关注处于偶数堆的石子是正确的。

得证：阶梯 Nim 游戏与只看奇数堆的基础 Nim 游戏等价，当且仅当 a_1\oplus{a_3}\oplus{a_5}\oplus\dots=0 时，先手必败；否则先手必胜。

P3480 [POI 2009] KAM-Pebbles

:::info[题解] 设 c_i=a_i-a_{i-1}，其中 c_1=a_1。不难发现，当 a_i 减少 x 时，有且仅有 c_i 减少 x，c_{i+1} 增加 x，这等价于从 c_i 中取 x 移至 c_{i+1}，即反向的阶梯 Nim 游戏。然后就是模板了。 :::

:::success[代码]

const int N=1005;
int n,XOR,a[N],c[N];
inline void solve()
{
    n=read(),XOR=0;
    for(int i=1;i<=n;i++) a[i]=read(),c[i]=a[i]-a[i-1];
    for(int i=n;i>=1;i-=2) XOR^=c[i];  // 注意反向 
    puts(XOR?"TAK":"NIE");
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}

:::

3. 图博弈

这类题没有什么固定模板，但解法相似，通常会有直接的图或将题面转化为图（图论建模），并将图中的节点分为“必胜点”和“必败点”，分别表示从该点出发的先手必胜或必败。

然后，根据题目的条件，不断向前继或后继扩展新的点，得到所有点的状态。

P6560 [SBCOI2020] 时光的流逝

:::info[题解] 根据题意，设置“必胜点”、“必败点”，以及既不是“必胜点”也不是“必败点”的“不定点”。

不难发现：

• 所有出度为零的点一定是“必败点”（题意），同时钦定终点是“必败点”（因为起点与终点不相同，所以如果先手从终点出发，必然是后手在上次移动后到达了终点，因此后手必胜，先手必败）。

• 只要某个点能够一步到达“必败点”，那么这个点就是“必胜点”（因为先手从该点一步到达“必败点”后，轮到后手，此时对于后手是必败的局面，故先手必胜）。

• 如果某个点能够一步到达的所有点都是“必胜点”，那么这个点就是“必败点”（因为先手如何走都会到达一个“必胜点”，轮到后手，此时后手是必胜的局面，故先手必败）。

由于枚举一个点能够一步到达的所有点是 O(n^2) 的，会超时，所以考虑建反图。

整体思路：跑类似拓扑序的东西。

初始时，所有入度为零的点和终点是“必败点”，将其全部放入队列。

然后，每次取出队首 x，枚举其儿子 y，当 y 还未确定“必胜点”或“必败点”时，令 y 入度减 1，如果 x 是“必败点”，则 y 是“必胜点”，并将 y 放入队列；否则，如果 y 入度为零，说明所有能够一步到达 y 的点都已确定是“必胜点”，则 y 是必败点，并将 y 放入队列；否则，不管它了。

最终，既不是“必胜点”，也不是“必败点”的点，就是“不定点”。

当起点是“必胜点”时，输出 1，“必败点”输出 -1，“不定点”输出 0。

这样，单次跑一遍是 O(m) 的（因为要把全图遍历一遍，且不会受环的影响），对于每次询问 s 和 t 都要跑一遍，总时间复杂度为 O(qm)，而且不一定跑满，勉强通过本题。

代码中，f_x=1/0/-1 表示该点是“必胜点”、“不定点”、“必败点”。 :::

:::success[代码]

const int N=100005,M=500005;
int n,m,Q,du[N],ls[N],f[N];
int tot,ver[M<<1],nxt[M<<1],head[N];
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
int main()
{
    n=read(),m=read(),Q=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        du[x]++,add(y,x);
    }
    while(Q--)
    {
        int s=read(),t=read();
        queue<int> q;
        for(int i=1;i<=n;i++)
        {
            ls[i]=du[i];
            if(!du[i]||i==t) f[i]=-1,q.push(i);
            else f[i]=0;
        }
        while(!q.empty())
        {
            int x=q.front();q.pop();
            if(x==s) break;  // 剪枝 
            for(int i=head[x];i;i=nxt[i])
            {
                int y=ver[i];
                if(f[y]) continue;
                ls[y]--;
                if(f[x]==-1) f[y]=1,q.push(y);
                else if(!ls[y]) f[y]=-1,q.push(y);
            }
        }
        if(f[s]<0) putchar('-');
        if(f[s]) putchar('1');
        else putchar('0');
        putchar('\n');
    }
    return 0;
}

:::

AT_agc010_f [AGC010F] Tree Game

:::info[题解] 首先，不难发现，当前处于任何一个点 x，先手都可以把接下来的局面控制在以 x 为根的子树里（先手永远移动到子树里除 x 以外的点）。因此，对于每个点，考虑以其为根的子树，必然可以考虑全面。

枚举每个 i 作为根，设置“必胜点”和“必败点”，表示只在以该点为根的子树内移动时，位于该点，先手必胜或必败。

对于当前点 x，枚举其直接子节点 y，若存在 y 是必败点，那么先手就可以从 x 移动到 y，使得后手位于 y 必败，逼迫后手只能从 y 回到 x。

因此，x 和 y 的石子数都减少 1。当 a_x>a_y 时，y 的石子比 x 先减到零，由于后手一直在 y 处取石子，最终是后手没有石子可取，先手必胜（注意，a_x=a_y 并不导致先手必胜，因为是 x 的石子数先减少，最终也是 x 的石子数先减到零）。

因此，只要存在直接子节点 y 是必败点且 a_x>a_y，那么 x 就是必胜点；否则，x 就是必败点。同时，为了便于上传，钦定叶子节点都是必败点。

于是 dfs 搜索，得到每个点是“必胜点”还是“必败点”，根 i 为“必胜点”时，输出 i。 :::

:::success[代码]

const int N=3005,M=3005;
int n,a[N],f[N];
int tot,ver[M<<1],nxt[M<<1],head[N];
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
void dfs(int x,int fa)
{
    f[x]=0;
    for(int i=head[x];i;i=nxt[i])
    {
        if(ver[i]==fa) continue;
        int y=ver[i];
        dfs(y,x);
        if(!f[y]&&a[x]>a[y]) f[x]=1;
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) f[j]=0;
        dfs(i,0);
        if(f[i]) print(i),putchar(' ');
    }
    return 0;
}

:::

AT_agc002_e [AGC002E] Candy Piles

:::info[题解] 首先，答案满足无序性，故可以将原 a 数组从大到小排序。 对于 a=\lbrace8,5,4,1,4,3\rbrace，画出其排序后的柱状图：

那么，每次删除最大值，或者令所有正数减 1，即为删除最左列，或者删除最底行。

因此，题意转换为：从 \left(1,1\right) 出发，每人每次向右（删除最左列）或向上（删除最低行）移动一次。当位于 \left(x,y\right) 时，有效网格仅为 \left(x,y\right) 及其右上方的点（含右方和上方）。

每个点连向其右方和上方的点，如同有向图，考虑图博弈。

设置“必胜点”和“必败点”。不难发现，每一个极大矩形的右上角一定是必败点（因为它不能再向上或向右走了）。所谓“极大矩形”，指不存在一个更大的矩形包含该矩形。

那么不难发现，规律如下（顺次判断）：

• 如果右方和上方为空，则该点为“必败点”。

• 如果上方为空，则该点与右方的点相反。

• 如果右方为空，则该点与上方的点相反。

• 如果右方和上方都是“必胜点”，则该点是“必败点”。

• 如果右方和上方中存在“必败点”，则该点是“必胜点”。

下面用字符 1 表示“必胜点”，字符 0 表示“必败点”，那么上述规律即为：

• 对于有两个合法前进方向的点，右、上方都为 1，该点为 0；否则，该点为 1。

• 对于只有一个合法前进方向的点，该点与该方向上的相邻点相反。

• 对于没有合法前进方向的点，该点为 0。

则上述柱状图即为：

注意到，对于存在右上方点的任意一点，都与其右上方的点相同。

证明：设当前处于 \left(x,y\right)。

• 当该点为 1 时，在 \left(x+1,y\right) 和 \left(x,y+1\right) 中必然存在一个 0，因此 \left(x+1,y+1\right) 必然为 1。

• 当该点为 0 时，\left(x+1,y\right) 和 \left(x,y+1\right) 必然都为 1。接下来考虑反证法。

  • 假设 \left(x+1,y+1\right) 为 1，则 \left(x+2,y\right) 和 \left(x,y+2\right) 必然都为 0，因此 \left(x+2,y+1\right) 和 \left(x+1,y+2\right) 必然都为 1，这就导致 \left(x+1,y+1\right) 为 0，这与假设矛盾，故假设不成立。

  • 因此，\left(x+1,y+1\right) 必然为 0。

  • 如果不存在 \left(x+2,y\right) 等点，同样容易证明 \left(x+1,y+1\right) 必然为 0。

得证：对于存在右上方点的任意一点，都与其右上方的点相同。

由于我们只关注 \left(1,1\right) 的值，即对角线 y=x 上的值，因此只需要找到满足 a_i\ge x 的最大的 i，然后从 \left(i,i\right) 出发，要么一路向右（如果右边有值的话），要么一路向上（如果上边有值的话）。 :::

:::success[代码]

int n,a[100005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;i++)
    {
        if(a[i+1]<i+1)
        {
            int j=0;
            while(a[i+j+1]==i) j++;
            // 一路向右 || 一路向上 
            if((j&1)||((a[i]-i)&1)) puts("First");
            else puts("Second");
            break;
        }
    }
    return 0;
}

:::

AT_abc278_f [ABC278F] Shiritori

:::info[题解] 以下全部基于 0-based，便于二进制描述位。

第一反应是图论建模，枚举所有字符串 s_i 及 s_j，当 s_i 的最后一个字符与 s_j 的第一个字符相同时，i 连向 j。

得到简单有向图后，由于 n\le 16，考虑状压 dp。

设 f_{S,i} 表示当前剩余未选整数（待选整数）的集合为 S，当前必须选择 i，先手必败（f=0）或者先手必胜（f=1）。其中，S 二进制下的第 k 位为 1 表示 k 待选。

枚举下一次的状态为 S，枚举 S 二进制下为 0 的所有位 i，钦定这一次选择 i，则这一次的状态为 f_{S+2^i,i}。枚举 i 连向的 j，钦定下一次必须选择 j，则下一次的状态为 f_{S,j}。只要存在 f_{S,j}=1，那么先手在 S+2^i 状态下选择了 i 进入 S 状态后，后手必然可以选择 j，使得自己必胜，于是先手必败，f_{S+2^i,i}=0；如果对于所有 f_{S,j} 都等于 0，那么先手选择了 i 后，后手无论如何都会必败，于是先手必胜，f_{S+2^i,i}=1。 :::

:::success[代码]

const int N=17;
int n,len[N];
char s[N][11];
vector<int> son[N];
int f[(1<<N)+5][N],vis[N];
int main()
{
    n=read();
    for(int i=0;i<n;i++) scanf("%s",s[i]),len[i]=strlen(s[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j&&s[i][len[i]-1]==s[j][0])
                son[i].push_back(j);
    for(int S=0;S<(1<<n);S++)
        for(int i=0;i<n;i++)
        {
            f[S^(1<<i)][i]=1;
            if(!(S>>i&1))
                for(auto j:son[i])
                    if((S>>j&1)&&f[S][j])
                        f[S^(1<<i)][i]=0;
        }
    int ans=0;
    for(int i=0;i<n;i++) ans|=f[(1<<n)-1][i];
    puts(ans?"First":"Second");
    return 0;
}

:::

AT_abc209_e [ABC209E] Shiritori

:::info[题解] 还是图论建模。称字符串的前三个字符构成的字符串为前缀，后三个字符为后缀。将三个字符的字符串作为一个点，考虑对于每个字符串，让前缀向后缀连边，得到一个有向图。

为了避免麻烦，用数字表示一个字符串，可以哈希，也可以用 unordered_map。以下数字节点代表其对应的字符串。

由于选择一个字符串后，接下来的局面只与后缀有关，即后缀相同的字符串所面临的局面相同。因此，设 f_{i}=0/1/2 表示当前选择以 i 为后缀的字符串时，平局（f=0），或者先手必胜（f=1），或者先手必败（f=2）。

那么，先手选择以 i 为后缀的字符串后，后手必须选择以 i 为前缀的字符串，可以视为先手处于 i 节点上，后手走到 i 连向的一个点 j。

转移就有了，若 i 连向的 j 中，存在 f_j=1，那么后手必然会选择以 i 为前缀，以 j 为后缀的字符串，使得自己必胜，所以先手必败，f_i=2；若对于所有 j，都有 f_j=2，后手无论怎么选择都会必败，所以先手必胜，f_i=1；否则，对于所有 j，不存在 f_j=1 且存在 f_j=0，后手为了不必败，必然会选择 f_j=0 的局面，即平局，此时 f_j=0。

然后就和题目“P6560 时光的流逝”一样了，考虑建反图跑拓扑排序，时间复杂度为 O(n)。如果用 map，会多带一个 \log n，不过都能过。 :::

:::success[代码]

const int N=200005,M=52*52*52+5;
const string ans[3]={"Draw","Takahashi","Aoki"};
int n,len,tot;
string s,l[N],r[N];
int du[M],f[M];
unordered_map<string,int> id;
vector<int> father[M];
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s,len=s.size();
        for(int j=0;j<3;j++) l[i]+=s[j];
        for(int j=len-3;j<len;j++) r[i]+=s[j];
        if(!id[l[i]]) id[l[i]]=++tot;
        if(!id[r[i]]) id[r[i]]=++tot;
        father[id[r[i]]].push_back(id[l[i]]);
        du[id[l[i]]]++;
    }
    for(int i=1;i<=tot;i++) if(!du[i]) q.push(i),f[i]=1;
    while(!q.empty())
    {
        int y=q.front();q.pop();
        for(auto x:father[y])
        {
            if(f[x]) continue;
            if(f[y]==1) f[x]=2,q.push(x);
            else if(!--du[x]) f[x]=1,q.push(x);
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[f[id[r[i]]]]<<'\n';
    return 0;
}

:::

P9169 [省选联考 2023] 过河卒

:::info[题解] 令 a,b,c 分别表示黑棋，红棋一号，红棋二号，其位置为 ax,ay,bx,by,cx,cy，由于 n,m\le10，因此设 g_{ax,ay,bx,by,cx,cy,0/1}=0/1 表示当前状态为黑棋位于 \left(ax,ay\right)，红棋一号位于 \left(bx,by\right)，红棋二号位于 \left(cx,cy\right)，且轮到红方或者黑方时，先手必败（g=0）或者先手必胜（g=1）。显然，最多只存在 2\times 10^6 种状态。

那么这个状态合法，当且仅当 a,b,c 都位于网格内的非障碍位置，且 b,c 不重合。

把状态当做点，根据 g 值，设置“必胜点”和“必败点”，分别表示一个点是先手必胜还是先手必败。

把原题面的一部分搬过来：

在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）：

• 黑棋子位于第一行。此时黑方胜。

• 黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。

• 当前玩家不能进行任何合法操作。此时对方胜。

那么有以下五条规则：

• 如果 ax=1，那么 g_{ax,ay,bx,by,cx,cy,0}=0,g_{ax,ay,bx,by,cx,cy,1}=1（当前状态满足结束条件一，黑方胜，故红方先手必败，黑方先手必胜）。

• 如果 a,b 重合或 a,c 重合，那么 g_{ax,ay,bx,by,cx,cy,0}=g_{ax,ay,bx,by,cx,cy,1}=0（当前状态满足结束条件二，对方胜，故先手必败）。

• 如果某个点不能一步到达任何点，那么该点就是“必败点”（当前状态满足条件三，对方胜，故先手必败）。

• 只要某个点能够一步到达“必败点”，那么这个点就是“必胜点”（因为先手从该点一步到达“必败点”后，轮到后手，此时对于后手是必败的局面，故先手必胜）。

• 如果某个点能够一步到达的所有点都是“必胜点”，那么这个点就是“必败点”（因为先手如何走都会到达一个“必胜点”，轮到后手，此时后手是必胜的局面，故先手必败）。

咦？竟然和题目“P6560 时光的流逝”惊人地相似（其实后两条是直接粘过来的）！所以建反图，然后跑 bfs 就行了。

那么直接根据起始状态的 g 值即可判断是红方必胜还是黑方必胜了。

现在考虑步数。设 f_{ax,ay,bx,by,cx,cy,0/1} 表示当前状态直到结束，所需要的步数。显然，前三条规则都是直接结束，故 f=0；第四条规则先手必胜，故先手必然会从 f 最小的那个“必败点”转移过来；第五条规则先手必败，故先手必然会从 f 最大的那个“必胜点”转移过来。只需要再设置一个 vis 数组即可。

代码中将状态简化为数字，从零开始，使得状态 ax,ay,bx,by,cx,cy,0 和状态 ax,ay,bx,by,cx,cy,1 刚好可以通过异或 1 来得到。

以下是洛谷 95 分代码，卡卡常并使用神秘 C++98 就过了。 :::

:::success[代码]

const int N=15,M=2000005,dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int n,m;
char s[N][N];
struct node
{
    int x,y;
}a,b,c;  // 黑棋，红棋一号，红棋二号 
inline bool check(int ax,int ay,int bx,int by,int cx,int cy)
{
    if(ax<1||ax>n||ay<1||ay>m) return false;
    if(bx<1||bx>n||by<1||by>m) return false;
    if(cx<1||cx>n||cy<1||cy>m) return false;
    if(s[ax][ay]=='#'||s[bx][by]=='#'||s[cx][cy]=='#') return false;
    if(bx==cx&&by==cy) return false;
    return true;
}
int cnt,id[N][N][N][N][N][N][2];
int tot,du[M],ver[M*12],nxt[M*12],head[M];
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
int st,vis[M],g[M],f[M];
// g=1/0 表示先手必胜或者必败，f 表示移动步数 
inline void bfs()
{
    queue<int> q;
    for(int i=0;i<cnt;i++) if(vis[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(x==st) return ;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i];
            if(!vis[y])
            {
                du[y]--;
                if(!g[x]) vis[y]=1,g[y]=1,f[y]=f[x]+1,q.push(y);  // 从最小的必败点转移过来，由于 vis[y]=1，故 f[y] 只会被第一个必败点更新。同时由于使用队列，第一个必败点一定是 f 最小的必败点 
                else if(!du[y]) vis[y]=1,g[y]=0,f[y]=f[x]+1,q.push(y);  // 从最大的必胜点转移过来，由于直到 du[i]=0 才更新f[y]，故 f[y] 只会被最后一个必胜点更新。同时由于使用队列，最后一个必败点一定是 f 最大的必败点 
            }
        }
    }
}
inline void myclear()
{
    a=b=c=node{0,0};
    for(int i=0;i<cnt;i++) du[i]=head[i]=vis[i]=g[i]=f[i]=0;
    cnt=tot=0;
}
inline void solve()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='X') a=node{i,j};
            if(s[i][j]=='O')
            {
                if(!b.x&&!b.y) b=node{i,j};
                else c=node{i,j};
            }
        }
    }
    for(int ax=1;ax<=n;ax++) for(int ay=1;ay<=m;ay++)
        for(int bx=1;bx<=n;bx++) for(int by=1;by<=m;by++)
            for(int cx=1;cx<=n;cx++) for(int cy=1;cy<=m;cy++)
                if(check(ax,ay,bx,by,cx,cy))
                {
                    id[ax][ay][bx][by][cx][cy][0]=cnt++;
                    id[ax][ay][bx][by][cx][cy][1]=cnt++;
                }
    for(int ax=1;ax<=n;ax++) for(int ay=1;ay<=m;ay++)
        for(int bx=1;bx<=n;bx++) for(int by=1;by<=m;by++)
            for(int cx=1;cx<=n;cx++) for(int cy=1;cy<=m;cy++)
                if(check(ax,ay,bx,by,cx,cy))
                {
                    int now=id[ax][ay][bx][by][cx][cy][0];  // now^1=id[ax][ay][bx][by][cx][cy][1] 
                    for(int t=0;t<3;t++)
                    {
                        int nax=ax+dx[t],nay=ay+dy[t];
                        if(check(nax,nay,bx,by,cx,cy))
                        {
                            du[now^1]++;
                            add(id[nax][nay][bx][by][cx][cy][0],now^1);
                        }
                    }
                    for(int t=0;t<4;t++)
                    {
                        int nbx=bx+dx[t],nby=by+dy[t];
                        if(check(ax,ay,nbx,nby,cx,cy))
                        {
                            du[now]++;
                            add(id[ax][ay][nbx][nby][cx][cy][1],now);
                        }
                        int ncx=cx+dx[t],ncy=cy+dy[t];
                        if(check(ax,ay,bx,by,ncx,ncy))
                        {
                            du[now]++;
                            add(id[ax][ay][bx][by][ncx][ncy][1],now);
                        }
                    }
                    if(ax==1)
                    {
                        vis[now]=vis[now^1]=1;
                        g[now]=0,g[now^1]=1;
                        f[now]=f[now^1]=0;
                    }
                    else if((ax==bx&&ay==by)||(ax==cx&&ay==cy))
                    {
                        vis[now]=vis[now^1]=1;
                        g[now]=g[now^1]=0;
                        f[now]=f[now^1]=0;
                    }
                    else
                    {
                        if(!du[now]) vis[now]=1,g[now]=f[now]=0;
                        if(!du[now^1]) vis[now^1]=1,g[now^1]=f[now^1]=0;
                    }
                }
    st=id[a.x][a.y][b.x][b.y][c.x][c.y][0];
    bfs();
    if(!vis[st]) puts("Tie");
    else
    {
        if(g[st]==1) printf("Red ");
        else printf("Black ");
        print(f[st]),putchar('\n');
    }
    myclear();
}
int main()
{
    for(int id=read(),T=read();T;T--) solve();
    return 0;
}

4. SG 函数

SG 函数仅适用于公平游戏。设公平游戏状态为 X，定义其 SG 函数值为：

其中，x\in X 表示状态 x 可以由 X 一步转移。\operatorname{mex}\lbrace M\rbrace=\min\left(m\in \mathbb{N}\ \operatorname{and}\ m\not\in M\right) 表示不属于集合 M 的最小自然数。特别的，\operatorname{mex}\lbrace \varnothing\rbrace=0。

同时，由于公平游戏的状态是另一个公平游戏，故对于公平游戏 G_1,G_2,\dots,G_n，存在其总 SG 函数为：

当且仅当 SG(X)=0 时，状态 X 为先手必败；否则，状态 X 为先手必胜。

「一本通 6.7 例 3」移棋子游戏

:::info[原题及题解] 由于没有原题，这里给出原题：

给定一个有 n\left(1\le n\le2000\right) 个点、m\left(1\le m\le 6000\right) 条边的有向无环图，图中有 k\left(1\le k\le n\right) 个已知节点上有棋子，两名玩家轮流移动棋子：选择任意一颗棋子，将其沿一条有向边移动到另一个点。无法移动的人输掉游戏。假设双方都非常聪明，请问先手是必胜（输出 win）还是必败（输出 lose）。

显然，这是一个公平游戏。原游戏可以将所有棋子拆分成 k 个互不相关的游戏，那么原游戏的 SG 函数即为这 k 个游戏的 SG 函数的异或和。

现在考虑只有一个已知棋子的 SG 函数，这就是很经典了，对于点 x，枚举子节点 y，则 SG_x=\operatorname{mex}\lbrace SG_y\rbrace。

按照拓扑序，O(n^2) 暴力求解，当且仅当原游戏的 SG 值为零时，先手必败；否则，先手必胜。 :::

:::success[代码]

const int N=2005,M=6005;
int n,m,k,du[N];
struct EDGE
{
    int tot,ver[M],nxt[M],head[N];
    inline void add_edge(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
}a,b;
inline void add(int x,int y){a.add_edge(x,y),b.add_edge(y,x);}
queue<int> q;
int SG,sg[N];
bool vis[N];
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        du[x]++,add(x,y);
    }
    for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=a.head[x];i;i=a.nxt[i])
        {
            int y=a.ver[i];
            vis[sg[y]]=true;
        }
        for(int i=0;;i++)
            if(!vis[i])
            {
                sg[x]=i;
                break;
            }
        for(int i=a.head[x];i;i=a.nxt[i])
        {
            int y=a.ver[i];
            vis[sg[y]]=false;
        }
        for(int i=b.head[x];i;i=b.nxt[i])
        {
            int f=b.ver[i];
            if(!--du[f]) q.push(f);
        }
    }
    for(int i=1;i<=k;i++) SG^=sg[read()];
    puts(SG?"win":"lose");
    return 0;
}

:::

「一本通 6.7 练习 1」取石子游戏

:::info[原题及题解] 由于没有原题，这里给出原题：

有 n 堆石子，数量分别为 a_1,a_2,\dots,a_n。有 m 种取石子的合法个数，其集合为 b=\lbrace b_1,b_2,\dots,b_m\rbrace，两个人轮流取石子，每人每次可以从任意一堆石子里取出 k\left(k\in b\right) 个石子扔掉（可以取完，不能不取），没石子可取的人输掉游戏。假设双方都非常聪明，请问先手是必胜（输出 YES，并输出字典序最小的（第一步选择的石子堆编号，相应取走的石子数）的值）还是必败（输出 NO）。1\le n,m,b_i\le 10,1\le a_i\le 10^3。

显然，这是一个公平游戏。对于每个 a_i，都可以得到它的 SG 函数 sg_{a_i}，而原游戏可以根据 a_i 拆分成 n 个互不相关的游戏，那么原游戏的 SG 函数即为这 n 个游戏的 SG 函数的异或和。

于是考虑 O(m\times\max\limits_{i=1}^n a_i) 求出所有 a_i 的 SG 函数，然后得到总 SG 函数 SG={\large\oplus}_{i=1}^nsg_{a_i}，当且仅当 SG=0 时，先手必败；否则先手必胜。

显然，对于一堆石子数为 i 的石子堆，其 SG 函数为：sg_i=\operatorname{mex}\lbrace sg_{i-b_j}\rbrace。

现在考虑先手必胜时，第一步如何进行。

不是？数据范围都这么小了，还不直接暴力吗？枚举第一步选择的石子堆编号，以及取走的石子数，判断取走后的局面是否属于先手必败。若属于，由于第一步取走后轮到后手，后手必败，故先手必胜，其为合法。这里的时间复杂度为 O(n^2 m)。

时间复杂度达到 O(m\times\max\limits_{i=1}^n a_i+n^2 m)，不会超时。 :::

:::success[代码]

const int N=15,M=1005;
int n,m,maxa,a[N],b[N];
bool vis[M];
int SG,sg[M],ls[N];
inline bool check(int x,int y)
{
    for(int i=1;i<=n;i++) ls[i]=a[i];
    ls[x]-=y;
    SG=0;
    for(int i=1;i<=n;i++) SG^=sg[ls[i]];
    return (SG?true:false);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),maxa=max(maxa,a[i]);
    m=read();
    for(int i=1;i<=m;i++) b[i]=read();
    sg[0]=0;
    for(int i=1;i<=maxa;i++)
    {
        memset(vis,false,sizeof(vis));
        for(int j=1;j<=m&&i-b[j]>=0;j++) vis[sg[i-b[j]]]=true;
        for(int j=0;;j++)
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
    }
    for(int i=1;i<=n;i++) SG^=sg[a[i]];
    if(!SG) puts("NO");
    else
    {
        puts("YES");
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(!check(i,b[j]))
                {
                    print(i),putchar(' '),print(b[j]);
                    return 0;
                }
    }
    return 0;
}

:::

AT_abc206_f [ABC206F] Interval Game 2

:::info[题解] 显然，这是一个公平游戏。设半开区间 \left[l,r\right) 的 SG 函数为 SG_{l,r}。对于每个题中所给的处于 \left[l,r\right) 的半开区间 \left[l_i,r_i\right)，选择它会将原区间分成两个独立的部分 \left[l,l_i\right) 和 \left[r_i,r\right)。根据定义，有：

直接 O(T n^3) 求 SG 函数，当且仅当 SG_{1,\max\left(r_i\right)}=0 时，先手必败；否则，先手必胜。 :::

:::success[代码]

const int N=105;
int n,maxn,f[N][N];
bool vis[N];
struct node
{
    int l,r;
}o[N];
inline void solve()
{
    n=read(),maxn=0;
    for(int i=1;i<=n;i++) o[i]=node{read(),read()},maxn=max(maxn,o[i].r);
    sort(o+1,o+n+1,[&](node a,node b){return a.l==b.l?a.r<b.r:a.l<b.l;});
    for(int len=1;len<=maxn;len++)
    {
        for(int l=1,r=l+len;r<=maxn;l++,r++)
        {
            memset(vis,0,sizeof(vis));
            for(int k=1;k<=n;k++) if(o[k].l>=l&&o[k].r<=r) vis[f[l][o[k].l]^f[o[k].r][r]]=1;
            for(int k=0;;k++) if(!vis[k]){f[l][r]=k;break;}
        }
    }
    puts(f[1][maxn]?"Alice":"Bob");
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}

:::

AT_arc151_c [ARC151C] 01 Game

:::info[题解] 显然，这是一个公平游戏。原游戏可以根据 x_i 拆分成 m+1 个互不相关的游戏，那么原游戏的 SG 函数即为这 m+1 个游戏的 SG 函数的异或和。

令 SG_{0/1/2/3}\left(len\right) 分别表示区间长度为 len 时，下列四种情况的 SG 函数：

• 没有左右边界：SG_1\left(len\right)=len\bmod2。

• 只有一个边界：SG_2\left(len\right)=len。

• 有两个边界且两个边界的数相同：SG_3\left(len\right)=1。

• 有两个边界且两个边界的数不同：SG_4\left(len\right)=0。

朱波只会列公式并打表，证明方面详见这些大佬们的题解。

当且仅当最终的 SG 函数为 0 时，先手必败，输出 Aoki；否则，先手必胜，输出 Takahashi。 :::

:::success[代码]

const int N=200005;
int n,m,sg,x[N],y[N];
int main()
{
    n=read(),m=read();
    if(!m)
    {
        if(n&1) puts("Takahashi");
        else puts("Aoki");
    }
    else
    {
        x[0]=0,x[m+1]=n+1;
        for(int i=1;i<=m;i++) x[i]=read(),y[i]=read();
        for(int i=0;i<=m;i++)
        {
            int len=x[i+1]-x[i]-1;
            if(i==0||i==m) sg^=len;
            else if(y[i]==y[i+1]) sg^=1;
        }
        if(!sg) puts("Aoki");
        else puts("Takahashi");
    }
    return 0;
}

:::

5. 博弈类 dp

这里不是像“博弈入门”一样的简单 dp，而是需要一定的思维难度写出 dp 转移式，有时还需要用各种各样的算法实现，或者数据结构优化。这里依次给出记忆化搜索、单调队列优化、树状数组优化、区间 dp 的题目。

「一本通 6.7 练习 3」取石子

:::info[原题及题解] 由于没有原题，这里给出原题：

有 n 堆石子，数量分别为 a_1,a_2,\dots,a_n。两个人轮流操作：从任意一堆石子里取出一个石子扔掉（如果取，可以取完，不能不取），或者合并任意两堆石子（如果合并，至少有两堆石子）。无法操作的人输掉游戏。假设双方都非常聪明，请问先手是必胜（输出 YES）还是必败（输出 NO）。1\le n\le 50,1\le a_i\le 10^3。

根据题目，不难发现，可执行操作次数是很重要的，于是可以把所有的石子堆分成两类：

• 单堆：只有一个石子，其可执行操作仅一次：要么与别的堆合并，要么取走石子，彻底消失。

• 多堆：有至少两个石子，其可执行操作有多次：既可以与别的堆合并，也可以取走一个石子。

设 f_{i,j}=1/0 表示场上有 i 个单堆，多堆的可执行操作总次数为 j 时，先手必胜（f=1）或者必败（f=0）。

那么有以下情况（每一种情况都不能满足前面的情况）：

• 当 i\le0\ \operatorname{and}\ j\le0 时，此时先手必败（因为上一步为后手，后手必胜），f_{i,j}=0。

• 当 i\le0 时，不存在单堆，只能对多堆进行操作，谁执行最后一次操作谁就赢。因此，当 j 为奇数时，f_{i,j}=1；否则，f_{i,j}=0。

• 当 j=1 时，则只有一次取石子操作，只存在一个“多堆”且它只有一个石子（如果有多个多堆，至少可以增加一次合并操作；如果有至少两个石子，至少可以增加一次取石子操作）。但这不是一个真正的多堆，而是一个单堆，因此 f_{i,j}=f_{i+1,0}。

• 进行四种可能的操作：

  • 取走一个单堆的石子。当 i>0 时，存在单堆，可以进行该操作，此时单堆减少一，多堆可执行操作总次数不变。若 f_{i-1,j}=0，则先手必然进行该操作，使得后手必败，故 f_{i,j}=1。

  • 取走一个多堆的石子，或者将两个多堆合并。当 j>0 时，存在多堆（不用考虑是否存在至少两个，因为这两种操作本质一样，即使只有一个多堆也可以进行前者），可以进行该操作，此时单堆不变，多堆可执行操作总次数减少一。若 f_{i,j-1}=0，同理 f_{i,j}=1。

  • 将一个单堆与一个多堆合并。当 i>0\ \operatorname{and}\ j>0 时，存在单堆和多堆，可以进行该操作，此时单堆减少一，多堆增加一个石子，可执行操作总次数增加一。若 f_{i-1,j+1}=0，则 f_{i,j}=1。

  • 将两个单堆合并。当 i>1 时，存在至少两个单堆，可以进行该操作，此时单堆数量减少二，多堆可执行操作总次数增加二（可以取走两次），若原本 j>0，则多堆可执行操作总次数再增加一（可以合并一次）。若 f_{i-2,j+2+\left[j>0\right]}=0，同理 f_{i,j}=1。

考虑记忆化搜索，时间复杂度为 O(n^2 m)。 :::

:::success[代码]

const int N=51,M=1001;
int f[N][N*M];
int dfs(int i,int j)
{
    if(i<=0&&j<=0) return 0;
    if(f[i][j]!=-1) return f[i][j];
    if(i<=0) return f[i][j]=(j&1);  // 仅多堆 
    if(j==1) return f[i][j]=dfs(i+1,0);  // 仅单堆 
    if(i>0&&!dfs(i-1,j)) return f[i][j]=1;  // 取单堆 
    if(j>0&&!dfs(i,j-1)) return f[i][j]=1;  // 取多堆，或者合并多堆 
    if(i>0&&j>0&&!dfs(i-1,j+1)) return f[i][j]=1;  // 单堆合并到多堆 
    if(i>1&&!dfs(i-2,j+2+(j>0))) return f[i][j]=1;  // 合并单堆 
    return f[i][j]=0;
}
int n,cnt1,cnt2,a[N];
inline void solve()
{
    n=read(),cnt1=cnt2=0;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        if(a[i]==1) cnt1++;
        else cnt2+=a[i]+1;  // 附带一个合并操作 
    }
    if(cnt2) cnt2--;  // 有 x 个多堆时，合并操作只有 x-1 个 
    puts(dfs(cnt1,cnt2)?"YES":"NO");
}
int main()
{
    memset(f,-1,sizeof(f));
    for(int T=read();T;T--) solve();
    return 0;
}

:::

AT_abc303_g [ABC303G] Bags Game

:::info[题解] 定义一段区间 \left[i,j\right] 的价值为：先手收益减去后手收益的最大值。设 f_{i,j} 表示区间 \left[i,j\right] 的价值。

设 s_i=\sum\limits_{j=1}^{i} x_j 表示前 i 个 x 的前缀和。

题目中的三种操作，其实是以下四种操作（令 len=j-i+1 表示区间 \left[i,j\right] 的长度）：

• 选择并取走最左端的一个袋子。此时，先手获得 x_i 的收益，轮到后手时即为 f_{i+1,j}，该区间对于后手的价值，等于负的对于先手的价值，因此 f_{i,j}=x_i-f_{i+1,j}。

• 选择并取走最右端的一个袋子。同理 f_{i,j}=x_j-f_{i,j-1}。

• 花费 A 的代价，重复以下动作 \min\left(B,len\right) 次：选择最左端或最右端的袋子并拿走它。这等价于拿走最左边的若干个连续袋子，和最右边的若干个连续袋子，中间剩下一段连续的袋子。中间剩下的区间长度为 len'=len-\min\left(B,len\right)=\max\left(0,len-B\right)。枚举剩余区间左端点为 k，则右端点为 k+len'-1。此时，先手获得左区间加右区间的收益，即总区间减剩余区间的收益，即 s_j-s_{i-1}-\left(s_{k+len'-1}-s_{k-1}\right)，花费 A 的代价，轮到后手时即为 f_{k,k+len'-1}，该区间对于后手的价值，等于负的对于先手的价值，因此：

  len'=\max\left(0,len-B\right),f_{i,j}=\max\left(s_j-s_{i-1}-\left(s_{k+len'-1}-s_{k-1}\right)-A-f_{k,k+len'-1}\right)

• 花费 C 的代价，重复以下动作 \min\left(D,len\right) 次：选择最左端或最右端的袋子并拿走它。同操作三：

  len'=\max\left(0,len-D\right),f_{i,j}=\max\left(s_j-s_{i-1}-\left(s_{k+len'-1}-s_{k-1}\right)-C-f_{k,k+len'-1}\right)

前两种操作可以 O(n^2) 实现，后两种操作暴力实现的时间复杂度为 O(n^3)，考虑优化。以下只考虑操作三，因为操作四等价。

注意 \max 和 \min 的转化，还是很容易理解的，因为加上一个负的最大值，等于减去正的最小值。

发现需要动态维护 s_{k+len'-1}-s_{k-1}+f_{k,k+len'-1} 的最小值，这里使用单调队列优化。

具体来说，枚举外区间的长度 len，得到内区间的长度 len'，当 len'=0 时，暴力枚举所有长度为 len 的区间左端点 i 并更新 f，时间复杂度为 O(n^2)；当 len'\ne0 时，枚举所有长度为 len' 的区间左端点 k 并更新单调队列，被更新的外区间即为 \left[(k+len'-1)-len+1,k+len'-1\right]。这样，时间复杂度优化到 O(n^2)。

代码中 len_ 表示内区间长度 len'。 :::

:::success[代码]

typedef long long ll;
const int N=3005;
int n,A,B,C,D,x[N];
ll s[N],f[N][N];
struct Deque  // 手写双端队列 
{
    int head,tail,num[N];
    inline void init(){head=1,tail=0;}
    inline bool empty(){return head>tail;}
    inline int front(){return num[head];}
    inline void pop_front(){head++;}
    inline int back(){return num[tail];}
    inline void pop_back(){tail--;}
    inline void push_back(int x){num[++tail]=x;}
}q;
inline ll get(int k,int len_){return s[k+len_-1]-s[k-1]+f[k][k+len_-1];}
inline void monotonic(int cost,int t,int len)  // 单调队列优化 
{
    int len_=max(0,len-t);
    if(!len_) for(int i=1,j=i+len-1;j<=n;i++,j++) f[i][j]=max(f[i][j],s[j]-s[i-1]-cost);
    else
    {
        q.init();
        for(int k=1,i=(k+len_-1)-len+1,j=k+len_-1;j<=n;k++,i++,j++)
        {
            while(!q.empty()&&get(k,len_)<=get(q.back(),len_)) q.pop_back();
            q.push_back(k);
            while(!q.empty()&&q.front()<i) q.pop_front();
            if(i>=1&&j<=n) f[i][j]=max(f[i][j],s[j]-s[i-1]-cost-get(q.front(),len_));
        }
    }
}
int main()
{
    n=read(),A=read(),B=read(),C=read(),D=read();
    for(int i=1;i<=n;i++) x[i]=read(),s[i]=s[i-1]+x[i];
    for(int len=1;len<=n;len++)
    {
        for(int i=1,j=i+len-1;j<=n;i++,j++) f[i][j]=max(x[i]-f[i+1][j],x[j]-f[i][j-1]);
        monotonic(A,B,len),monotonic(C,D,len);
    }
    print(f[1][n]);
    return 0;
}

:::

AT_abc342_f [ABC342F] Black Jack

:::info[题解] 发现 x 和 y 是相互独立的，于是先考虑 x。设 f_i 表示当前 x=i 的最大获胜概率。显然，f_i 只从两种情况转移过来：继续掷骰和结束掷骰。

对于继续掷骰，掷出点数等概率为 1\sim d，因此 f_i=\frac{\sum\limits_{j=i+1}^{i+d} f_j}{d}，显然可以从后往前枚举 i，动态维护后 d 个 f 之和；对于结束掷骰，令以 x=i 结束的最大获胜概率为 solve_i，问题即为如何求 solve_i。

对于 solve_i，因为 x,n 的值是已知的，游戏获胜条件为 y>n 或 y<x，所以需要考虑 y。设 g_i 表示庄家掷出 i 的概率，那么 g_0=1。从小到大枚举 i，对于当前的 i，显然 g_i 会对 g_{i+1}\sim g_{i+d} 均产生 \frac{g_i}{d} 的贡献。区间修改，单点查询，可以用树状数组维护。

那么，y>n 的总概率即为 1-\sum\limits_{i=1}^{n}g_i，y<x 的概率即为 \sum\limits_{i=1}^{x-1}g_i。显然，可以前缀和优化。

那么，solve_i=1-\sum\limits_{i=1}^{n}g_i+\sum\limits_{i=1}^{x-1}g_i，因此求得 f_i。最终答案即为 f_0。

注意，由于求 f_i 需要 f_{i+d}，而 i+d 的范围最大会达到 4\times 10^5，因此注意数组大小和枚举上界。 :::

:::success[代码]

const int N=400005;
int n,l,d;
double sum,f[N],g[N];
struct BIT
{
    double c[N];
    inline void add(int x,double v){for(;x<=400000;x+=(x&(-x))) c[x]+=v;}
    inline double ask(int x){double res=0;for(;x;x-=(x&(-x))) res+=c[x];return res;}
}tr;
inline double solve(int i)
{
    if(i>n) return 0.0;  // i>n 时，以 x=i 结束必输 
    double res=1.0-g[n];
    if(i) res+=g[i-1];
    return res;
}
int main()
{
    n=read(),l=read(),d=read();
    // g[0]=1.0，对 g[1~d] 产生 1.0/d 的贡献，差分即为令 g[1]+=1.0/d,g[d+1]-=1.0/d 
    tr.add(1,1.0/d),tr.add(d+1,-1.0/d);
    for(int i=1;i<=400000;i++)
    {
        g[i]=tr.ask(i);
        if(i<l)
        {
            tr.add(i+1,g[i]/d),tr.add(i+d+1,-g[i]/d);
            g[i]=0.0;  // 注意，当 i<l 时，庄家是不能停下的，因此 g[i] 应为 0 
        }
    }
    for(int i=1;i<=400000;i++) g[i]+=g[i-1];  // 前缀和优化 
    for(int i=400000;i>=0;i--)
    {
        if(i>n) f[i]=0.0;  // x>n 输 
        else f[i]=max(sum/d,solve(i));
        sum+=f[i];
        if(i+d<=400000) sum-=f[i+d];  // 动态维护后 d 个 f 之和 
    }
    printf("%.15lf",f[0]);
    return 0;
}

:::

P2599 [ZJOI2009] 取石子游戏

:::info[题解] 好题！ZJOI 还是太牛了。

设 l_{i,j} 表示区间 \left[i,j\right] 的左边（i-1 处）加入 l_{i,j} 时，先手必败；r_{i,j} 表示区间 \left[i,j\right] 的右边（j+1 处）加入 r_{i,j} 时，先手必败。

有以下结论：

• 当 a_{i-1}\ne l_{i,j} 时，区间 \left[i-1,j\right] 的结果是先手必胜；当 a_{j+1}\ne r_{i,j} 时，区间 \left[i,j+1\right] 的结果是先手必胜。

证明：

首先，容易证明 l_{i,j},r_{i,j} 是有值的，只用证明它们只有一个值即可。考虑 l_{i,j}，假设存在多个 l_{i,j}，最小的为 L，那么对于所有大于 L 的 l_{i,j}，先手都可以把它减少到 L，使得后手必败，先手必胜，这与 l_{i,j} 的定义相矛盾。因此，l_{i,j} 有且仅有一个值，r_{i,j} 同理。定理一得证。

同上，当 a_{i-1}>l_{i,j} 时，先手可以把它减少到 l_{i,j}，使得后手必败，先手必胜；当 a_{i-1}<l_{i,j} 时，因为 l_{i,j} 先手必败，所以它的所有后继（把 l_{i,j} 减少到非负数）都是先手必胜。定理二得证。

显然，l_{i,i}=r_{i,i}=a_i，因为对于区间 \left[i,i\right]=\lbrace a_i\rbrace，在其左边或右边加入 a_i，都会变成在 \lbrace a_i,a_i\rbrace 上进行基础 Nim 游戏，由于 a_i\oplus{a_i}=0，故先手必败。

然后进行转移，还是考虑 l_{i,j}。令 L=l_{i,j-1},R=r_{i,j-1},x=a_j。那么区间 \left[i-1,j\right] 即为：

那么有以下情况（每一种情况都不能满足前面的情况）：

• 当 x=R 时，区间 \left[i,j\right] 先手必败，只要 l_{i,j}=0（相当于不添加），那么还是先手必败。

• 当 x<R\ \operatorname{and}\ x<L 时，l_{i,j}=x。此时，先手不论取 i-1 处还是 j 处，不论取多少，后手都取另一堆的相同数量，最终必然会变成：后手操作前，区间 \left[i,j-1\right] 保持原样，i-1 处和 j 处有一个是零，一个不大于原值 x。由于“不大于原值”的值必然小于 L 和 R，因此后手必胜，先手必败。这同样可以理解为，x 和 l_{i,j} 减至零的最大可执行次数都是 x，并且减的过程中不会遇到 x=R 或 l_{i,j}=L 的情况（这会在下面具体讲到），因此双方的最大可执行次数相同，最终必然会变成：后手操作前，一方是零，一方是不等于对应的 L 或 R 的值，故后手必胜，先手必败。

• 当 R<x\le L 时，l_{i,j}=x-1。此时，x 减至零的最大可执行次数为 x，l_{i,j} 减至零的最大可执行次数为 x-1。但是，由于 x>R，故 x 在减的过程中会遇到 x=R 的情况。如果一方操作后出现了 x=R，那么另一方将 l_{i,j} 一次性减成零，前者就必败了。因此，双方都不会将 x 减成 R 或 l_{i,j} 减成 L，于是 x 减至零的最大可执行次数减少一，变为 x-1，与 l_{i,j} 相同，同理，先手必败。

• 当 L\le x<R 时，l_{i,j}=x+1。同理，x 减至零的最大可执行次数为 x，l_{i,j} 减至零要跳过 L，最大可执行次数为 x，先手必败。

• 当 x>L\ \operatorname{and}\ x>R 时，l_{i,j}=x。同理，x 减至零要跳过 R，最大可执行次数为 x-1，l_{i,j} 减至零要跳过 L，最大可执行次数为 x-1，先手必败。

那么 r_{i,j} 同理求得。最终，当且仅当 a_1=l_{2,n} 时，先手必败；否则，先手必胜。 :::

:::success[代码]

const int N=1005;
int n,a[N],l[N][N],r[N][N];
inline void solve()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        l[i][i]=r[i][i]=a[i];
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=1,j=i+len-1;j<=n;i++,j++)
        {
            int L=l[i][j-1],R=r[i][j-1],x=a[j];
            if(x==R) l[i][j]=0;
            else if(x<L&&x<R) l[i][j]=x;
            else if(R<x&&x<=L) l[i][j]=x-1;
            else if(L<=x&&x<R) l[i][j]=x+1;
            else l[i][j]=x;
            L=l[i+1][j],R=r[i+1][j],x=a[i];
            if(x==R) r[i][j]=0;
            else if(x<L&&x<R) r[i][j]=x;
            else if(R<x&&x<=L) r[i][j]=x+1;
            else if(L<=x&&x<R) r[i][j]=x-1;
            else r[i][j]=x;
        }
    }
    if(a[1]==l[2][n]) puts("0");
    else puts("1");
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}

:::

6. 博弈思维题

纯纯的人类智慧题！特点是：思维堪比 ad-hoc，代码堪比 a+b。

异或游戏

:::info[原题及题解] 由于没有原题，这里给出原题：

有 n 张卡片，价值分别为 a_1,a_2,\dots,a_n。两个人轮流拿卡片，每人每次可以从拿走一张未被拿走过的卡片，直到没有卡片可取。双方的得分为各自拿走卡片的价值异或和，得分大者获胜。假设双方都非常聪明，请问是先手必胜（输出 Mitsuha）、先手必败（输出 Taki）还是平局（输出 Draw）。T 组数据，T\le20,1\le\sum n\le 2\times10^5,1\le a_i\le10^9。

下文的“位”，表示某正整数在二进制下的“位”。

称先手为小 A，后手为小 B。设 s={\large\oplus}_{i=1}^n {a_i} 表示所有 a 的异或和。令最终小 A 的得分为 X，小 B 的得分为 Y，则 X\oplus{Y}=s。

• 当 s=0 时，有 X\oplus{Y}=0，因此 X=Y。所以，不论取卡片的过程如何，两者最终得分都一样大，必然平局。

• 当 s\ne0 时，设 s 的最高位为第 k 位，则对于所有高于 k 的位置，s 这一位为 0，即 X 和 Y 的这一位相同，无法比较大小；对于第 k 位，s 这一位为 1，即 X 和 Y 的这一位一个是 0，一个是 1，能够比较大小，是 1 的一方获胜。于是可以抛开其他位，只考虑第 k 位，将所有 a 的值赋为 0/1，显然有奇数个 a 为 1。问题转变为：在若干个 0/1 卡片中，两人轮流拿走卡片，得分为拿走的卡片值异或和，是 1 的一方获胜。设有 cnt 个 a 的值为 1，cnt 为奇数，则有 n-cnt 个 a 的值为 0。

  • 当 cnt\bmod4=1 时：

  • 当 n-cnt 为偶数时，n 为奇数。这种局面称为“有 4 的倍数加 1 个 1，偶数个 0”。

    • 此时，小 A 取 1 后，不论小 B 取什么，小 A 都取相同的数。

    • 那么，每四个 1 分给小 A、小 B 各两个，异或值不变；每两个 0 分给小 A、小 B 各一个，异或值不变，取卡片顺序不变。

    • 因此，小 A 必然多一个 1，异或和为 1，小 A 获胜。

  • 当 n-cnt 为奇数时，n 为偶数。这种局面称为“有 4 的倍数加 1 个 1，奇数个 0”。

    • 此时，假设小 A 先取了 1。

    • 若小 B 取 0，此时进入到“有 4 的倍数个 1，偶数个 0”的局面，显然小 A 可以控制局面，平分给双方，因此异或和不变，小 B 必败，因此小 B 只能取 1。

    • 假设小 A 再取 1。若小 B 取 0，此时进入到“有 4 的倍数加 2 个 1，偶数个 0”的局面，显然小 A 再取 1，进入到“有 4 的倍数加 1 个 1，偶数个 0”的局面（即上一种情况），轮到小 B，不论小 B 取什么，小 A 都取相同的数，最终必然剩下一个 1 给小 B（其余数在异或时抵消），由于小 A 已取三个 1，小 B 已取一个 1，加上这个 1 后异或和为 0，小 B 必败，因此小 B 只能再取 1。

    • 综上所述，只要小 A 先取 1，小 B 就只能取 1，小 A 再取 1，小 B 仍然只能取 1。这样，每四个 1 均分给小 A，小 B，使得两人异或和不变。

    • 最终会剩下一个 1 和奇数个 0，小 A 取走 1，小 A 获胜。

  • 综上所述，此时先手必胜。

  • 当 cnt\bmod4=3 时：

  • 当 n-cnt 为偶数时，n 为奇数。这种局面称为“有 4 的倍数加 3 个 1，偶数个 0”。

    • 此时，不论小 A 取什么，小 B 都取相同的数。

    • 那么，每四个 1 分给小 A、小 B 各两个，异或值不变；每两个 0 分给小 A、小 B 各一个，异或值不变，取卡片顺序不变。

    • 因此，最终剩下三个 1，小 A 拿两个，异或和为 0，小 B 拿一个，异或和为 1，小 B 获胜。

  • 当 n-cnt 为奇数时，n 为偶数。这种局面称为“有 4 的倍数加 3 个 1，奇数个 0”。

    • 此时，假设小 A 先取了 0。于是，进入到“有 4 的倍数加 3 个 1，偶数个 0”的局面（即上一种情况）。

    • 不论小 B 取什么，小 A 都取相同的数，根据证明，剩下的三个 1，小 B 拿两个，小 A 拿一个，小 A 获胜。

  • 综上所述，当 n 为奇数时，先手必败；否则，先手必胜。 :::

:::success[代码]

int n,s,a[200005];
int main()
{
    for(int T=read();T;T--)
    {
        n=read(),s=0;
        for(int i=1;i<=n;i++) a[i]=read(),s^=a[i];
        if(!s) puts("Draw");
        else
        {
            int num=0,cnt=0;
            while(s) num++,s>>=1;
            // 此时 num 为 s 的位数，最高位应为 num-1 
            for(int i=1;i<=n;i++) if((a[i]>>(num-1))&1) cnt++;
            if(cnt%4==1) puts("Mitsuha");
            else
            {
                if(n&1) puts("Taki");
                else puts("Mitsuha");
            }
        }
    }
    return 0;
}

:::

AT_arc148_d [ARC148D] mod M Game

:::info[题解] 不难发现，最终一定是 Alice 删除倒数第二个数，Bob 删除最后一个数。因此，设 Alice 删除倒数第二个数之前，删除的数之和为 x，Bob 删除最后一个数之前，删除的数之和为 y，最后剩下的两个数分别为 a,b。

那么，当且仅当 x+a\equiv y+b\pmod m 且 y+a\equiv x+b\pmod m 时，Alice 无论怎样选择都必败，故 Bob 必胜；否则 Alice 必胜。

两式相加：x+y+2\cdot a\equiv x+y+2\cdot b\pmod m\Rightarrow 2\cdot a\equiv 2\cdot b\pmod m。

由于 a,b<m，因此 2\cdot a,2\cdot b<2\cdot m，故 2\cdot a\equiv 2\cdot b\pmod m 只会有三种情况（它们互不相交）：

考虑 Bob 必胜的情况，不难发现，当且仅当这 2\cdot n 个数全部可以找到另一个数，使得它们之间满足以上三种条件之一，则 Bob 必胜；否则 Alice 必胜。因此，我们把以上三个条件推广到所有数。