【题解】洛谷 P2599 [ZJOI2009] 取石子游戏

wsyhb · 2022-02-07 14:34:11 · 题解

前言

本文将在yybyyb 的题解的基础上对证明进行一些必要的补充。

旨在修正一些瑕疵 & 方便读者理解。

复读一遍：

神仙题.jpg。ZJOI 是真的神仙。
发现 SG 函数等东西完全找不到规律，无奈只能翻题解。

话说洛谷 Markdown 的缩进好丑啊……

正文

状态的定义

设 L(i,j) 表示在 [i,j] 区间的左侧放上一堆数量为 L(i,j) 的石子后，先手必败。（L(i,j) 可以为 0）
即：(L(i,j),a_i,a_{i+1},\cdots,a_j) 为必败局面。

同理对右侧定义 R(i,j)。

1. 假设不存在满足定义的 $L(i,j)$，则对于任意非负整数 $x$，$(x,a_i,a_{i+1},\cdots,a_j)$ （记为 $A(x)$ 局面）为必胜局面。 由于 $A(x)$ 为必胜局面，故从 $A(x)$ 局面一步可达某个必败局面。 若拿最左边一堆，则不可能变成必败局面，因为这样得到的局面仍形如 $A$。（注意包括此行在内的接下来几行默认 $x \neq 0$） 于是设 $A(x)$ 一步可达的（某个）必败局面为 $(x,a_i,a_{i+1},\cdots,a_{j-1},y)$，显然有 $0 \le y < a_j$。 **由于 $x$ 有无限个，但 $y$ 只有 $a_j$ 种——根据抽屉原理，必存在 $x_1,x_2(x_1 \neq x_2),y$ 满足 $(x_1,a_i,a_{i+1},\cdots,a_{j-1},y)$ 和 $(x_2,a_i,a_{i+1},\cdots,a_{j-1},y)$ 都是必败局面。**但这两个必败局面之间实际一步可达，故矛盾，进而原命题成立。
2. 假设 $L(i,j)$ 不唯一，则存在非负整数 $x_1,x_2(x_1 \neq x_2)$， $(x_1,a_i,a_{i+1},\cdots,a_{j-1},a_j)$ 和 $(x_2,a_i,a_{i+1},\cdots,a_{j-1},a_j)$ 均为必败局面。而这两个必败局面之间实际一步可达，故矛盾，进而原命题成立。

有了唯一性，我们可以自然地得出一个有用的结论：

对于任意非负整数 x \neq L(i,j)，(x,a_i,a_{i+1},\cdots,a_j) 为必胜局面。

注：下文所说的“根据 L(\cdots) 或 R(\cdots) 的定义”即指 L(i,j) 的定义 & 这个结论。

状态的转移（求解）

边界情况：L(i,i)=a_i。（对于两堆相同的石子，后手一定可以进行和先手对称的操作）

• - 结论：$L(i,j)=x$。 - **证明**： 即证 $(x,a_i,a_{i+1},\cdots,a_{j-1},x)$ 为必败局面。 由于最左边和最右边的两堆石子数量相同，后手可进行和先手对称的操作，直到自己在某一时刻获得形如 $(y,a_i,a_{i+1},\cdots,a_{j-1})$ 或 $(a_i,a_{i+1},\cdots,a_{j-1},y)$ 的局面。 由于 $0<y \le x<\min\{L,R\}$，结合 $L(i,j-1)$ 和 $R(i,j-1)$ 的定义知这个局面必胜，即后手必胜，证毕。 - 注意上述证明的前提是 $x \neq 0$，因此**后续证明若使用 Case 2，必须满足 $x \neq 0$（具体见后文）**。 - $x \geq L$，即 $L \leq x < R$（**Case 3**） - 结论：$L(i,j)=x+1$。 - **证明**： 1. 若先手拿最左边一堆，设拿了以后还剩 $z$ 个石子。 ​ 若 $z>L$，则后手将最右堆拿成 $z-1$ 个石子（注意 $z-1 \ge L>0$），就能回到 Case 3 本身，递归证明即可。 ​ 若 $z=L$，则后手将最右堆拿完，根据 $L(i,j-1)$ 定义知此时局面必败。 ​ 若 $0<z<L$，则后手将最右堆拿成 $z$ 个石子，由 Case 2 知此时是必败局面。 ​ 若 $z=0$，此时最右堆石子数 $k$ 满足 $L \le k<R$，结合 $R(i,j-1)$ 定义知局面必胜。（照应 Case 2 黑体内容） 2. 若先手拿最右边一堆，设拿了以后还剩 $z$ 个石子。 ​ 若 $z \ge L$，则后手将最左堆拿成 $z+1$ 个石子，递归证明即可。 ​ 若 $0<z<L$，则后手将最左堆拿成 $z$ 个石子，由 Case 2 知此时是必败局面。 ​ 若 $z=0$，则后手将最左堆拿成 $L$ 个石子，由 $L(i,j-1)$ 定义知此时局面必败。

• x>R
  • - 结论：$L(i,j)=x-1$。 - **证明**（与 Case 3 证明同理，读者可先自己尝试证明，再进行阅读）： 1. 若先手拿最左边一堆，设拿了以后还剩 $z$ 个石子。 ​ 若 $z \geq R$，则后手将最右堆拿成 $z+1$ 个石子，就能回到 Case 4 本身，递归证明即可。 ​ 若 $0<z<R$，则后手将最右堆拿成 $z$ 个石子，由 Case 2 知此时是必败局面。 ​ 若 $z=0$，则后手将最右堆拿成 $R$ 个石子（注意 Case 4 保证了此时最右堆石子个数 $>R$），由 $R(i,j-1)$ 的定义知此时是必败局面。 2. 若先手拿最右边一堆，设拿了以后还剩 $z$ 个石子。 ​ 若 $z>R$，则后手将最左边一堆拿成 $z-1$ 个石子（注意 $z-1 \ge R >0$），递归证明即可。 ​ 若 $z=R$，则后手把最左堆拿完，根据 $R(i,j-1)$ 的定义可知得到了必败局面。 ​ 若 $0<z<R$，则后手将最左堆拿成 $z$ 个石子，由 Case 2 知此时是必败局面。 ​ 若 $z=0$，此时最左堆石子数量 $k$ 满足 $0<k<L$，结合 $L(i,j-1)$ 定义知局面必胜。
  • - 结论：$L(i,j)=x$。 - **证明**（有了前面这么多的证明作为经验，这里就稍微简略点儿）： ​ 设先手将其中一堆拿成了 $z$ 个石子。 ​ 若 $z>\max\{L,R\}$，回到 Case 5，递归证明。 ​ 若 $0<z<\min\{L,R\}$，后手把另一堆也拿成 $z$ 个石子即可转 Case 2。 ​ 若 $z=0$，将另一堆拿成 $L$ 或 $R$ 个石子即可得到必败局面。 ​ 剩余的情况是 $L \le z \le R$ 或 $R \le z \le L$。 ​ 而 Case 3 可以解决最左堆 $L+1 \le z \le R$，最右堆 $L \le z \le R-1$ 的情况（取石子以满足 Case 3 的形式，下同）； ​ 且 Case 4 可以解决最左堆 $R \le z \le L-1$，最右堆 $R+1 \le z \le L$ 的情况。 ​ 所以只需解决最左堆 $z=L$ 和最右堆 $z=R$ 的情况。 ​ 而这两种情况直接把另一堆拿完就可以得到必败局面。

综上所述：

温馨提示：请看清楚 L 取不取等，乱取等是错的！

同理可求 R(i,j)。

回到原题，先手必败当且仅当 L(2,n)=a_1，于是我们就做完啦！

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

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=1e3+5;
int a[max_n],L[max_n][max_n],R[max_n][max_n];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",a+i);
            L[i][i]=R[i][i]=a[i];
        }
        for(int len=2;len<=n;++len)
            for(int i=1;i+len-1<=n;++i)
            {
                int j=i+len-1,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+1;
                else if(x>r&&x<=l)
                    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==l)
                    R[i][j]=0;
                else if(x>=r&&x<l)
                    R[i][j]=x+1;
                else if(x>l&&x<=r)
                    R[i][j]=x-1;
                else
                    R[i][j]=x;
            }
        puts(L[2][n]==a[1]?"0":"1");
    }
    return 0;
}