UVA10165

Windy_YY · 2022-04-10 11:01:35 · 题解

upd 2024/05/16：已经通过的题解添加了 Nim 游戏必胜/必败状态的证明。

Nim 游戏模板题。

可以使用 SG 定理来求解这个题目。其中有定义 sg[i] = \operatorname{mex}(sg[i-1], sg[i-2], sg[i-3], \cdots, sg[0])，\operatorname{mex} 运算为下面传递的所有的参数中最小的没有出现过的自然数。然后如果每一堆的石子的数量的 sg 值异或起来 \neq 0，那么先手必胜，否则后手必胜。

发现 sg[i] = i。所以只要将输入的每一堆的石子的数量异或起来，判断一下这个值是不是 0 即可。

为什么 sg[i]=i？考虑回归 SG 定理中 sg 值的定义。

\text{mex} 运算的定义

SG 定理和 SG 函数的定义

如果一个状态 x 可以转移到 a_1,a_2,a_3,\cdots,a_k 这些状态，那这个状态的值就是 \operatorname{mex}\{a_1,a_2,a_3,\cdots,a_k\}，其中终止状态的 SG 值为 0。

如果一个状态的 SG 值为 0 就是必败状态，否则就是必胜状态。

我们发现对于一个状态 x，她可以分别转移到 0,1,2,\ldots,x-1 的状态。为什么不能转移到 x？很显然，x 状态取掉至少一个石子之后肯定石子数量 <x。因此 sg_x=\operatorname{mex}\{0,1,2,\ldots,x-1\}=x。于是得证。

为什么必胜状态是这样的？证明：

首先必败状态是 0,0,0,\ldots,0，显然异或和为 0\oplus 0\oplus \ldots\oplus 0=0。

若此时异或状态不为 0，则当前走的一方一定可以通过一些操作让当前的异或状态为 0。同时若当前异或状态为 0 且至少有一个不是 0，则根据异或的自反律 x\oplus x=0，必然有至少两个不为 0 的位置，当前方操作一次之后必然使得当前的异或和不为 0。因此得证。

所以说，对于每一组数据，只需要将所有输入的值异或起来，若答案为 0 则后手必胜，否则先手必胜。完。时间复杂度为 O(n)。

记得是多组数据。

#include <stdio.h>
int main() {
    int n;
    while (scanf ("%d", &n) && n) {
        int xr = 0;
        for (int i = 1; i <= n; i ++) {
            int x;
            scanf ("%d", &x);
            xr ^= x;
        }
        if (xr)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}