P3480 题解

· · 题解

注：本篇题解为半萌新向，

知道什么是 nim 游戏的跳到第二章；

知道什么是阶梯 nim 的跳到第三章；

只是想看代码的去第四章；

一：nim 游戏

nim 游戏规则： 有 n 堆石子，数量分别为 a_1,a_2,a_3,\cdots,a_n 。 两个玩家轮流拿石子，每次从任意一堆中拿走任意数量的石子，拿到最后一个石子的玩家获胜。

如何判断胜负？对于任意的 a_1,a_2,a_3,\cdots,a_n ，nim 游戏有一个很简单的判断胜负的方法。

定理1：

若 a_1 \operatorname{xor} a_2 \operatorname{xor} a_3 \operatorname{xor} \cdots \operatorname{xor} a_n = 0，则先手必败。

若 a_1 \operatorname{xor} a_2 \operatorname{xor} a_3 \operatorname{xor} \cdots \operatorname{xor} a_n \neq 0，则先手必胜。

在 nim 游戏中进行的异或运算一般被称为 Nim-sum 运算。

下面对该定理进行简单证明：

  1. 若先手处于必胜点，则先手必然可以将局势转化为必败点。为什么？我们任选一堆石头，例如第 i 堆，石头数量为 a_i；对剩下的 n-1 堆进行异或运算，设结果为 H。若 H < k，就把第 i 堆石头减少到 H 个。因为 H \operatorname{xor} H = 0，所以这样操作以后 n 堆石头的异或等于 0。可以证明，总会存在这样的第 i 堆石头。

  2. 若先手处于必败点，则先手必然只能转移到必胜点。因为先手不论取哪堆，取多少，都会使得这一堆的二进制表达至少产生一位不同，导致异或值改变。

  3. 当所有石子取完时，显然为先手必败点（可以看作后手在上一轮取走了最后一个石子），又所有石头此时异或值为 0，证毕。

二：阶梯 nim 游戏

阶梯 nim 规则：

有 n 堆石子，数量分别为 a_1,a_2,a_3,\cdots,a_n 。 两个玩家轮流进行以下操作：

  1. 从第 i 堆石子中移动任意颗石子到第 i - 1 堆中（i \ge 2）。
  2. 从第一堆石子中移除任意颗石子。

这东西和 nim 游戏有啥关系啊？

关系就在：

定理二：

阶梯 nim 的结果与只看奇数堆的普通 nim 是一样的。

证明如下：

  1. 若对手将奇数堆的石子移至偶数堆，则相当于是在奇数堆中清除了这些石子。

  2. 若对手将偶数堆的石子移至奇数堆，则可以将这些石子从奇数堆再移回偶数堆，相当于“抵消”了这次对手的行动。

Q：为啥阶梯 nim 的结果不是与只看偶数堆的普通 nim 一样？证明起来好像只用把奇偶调换一下就可以了啊？

A：关键就在于那个“抵消”操作。若对手将第二堆中的石子挪到第一堆，就无法再将那些石子移回偶数堆了。

三：本题思路

看到这一题的特殊要求“每堆石子个数都不少于前一堆的石子个数”时，首先考虑差分。因为这个条件可以使差分中的每一项均为正。

设 c_i = a_i - a_{i - 1}，其中第一项 c_1 = a_1。

好像没什么感觉。我们拿走一些石子试试。

从第 i 堆中取走 x 颗石子，则 c_i 变为 c_i - x，c_{i + 1} 变为 c_{i + 1} + x。

和阶梯 nim 神似有木有？只不过变成从前往后拿，所以需要倒着取奇数堆。

那么……

四：代码奉上

因为上面写的很详细就不加注释了

#include <iostream>
using namespace std;

int c[1001];

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        int la = 0;
        for (int i = 1; i <= n; i++)
        {
            int z;
            cin >> z;
            c[i] = z - la;
            la = z;
        }

        int nim_sum = 0;
        for (int i = n; i > 0; i -= 2)
        {
            nim_sum ^= c[i];
        }
        nim_sum ^= 0;

        if (nim_sum == 0)
        {
            cout << "NIE" << endl;
        }
        else
        {
            cout << "TAK" << endl;
        }
    }
}