[洛谷刷题12]

可以先学习一下Nim游戏

P2197 【模板】Nim 游戏

https://www.luogu.com.cn/problem/P2197

题目描述

甲，乙两个人玩 nim 取石子游戏。

nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

输入格式

本题有多组测试数据。

第一行一个整数 $T$ （$T\le 10$），表示有 $T$ 组数据

接下来每两行是一组数据，第一行一个整数 $n$，表示有 $n$ 堆石子，$n\le 10^4$。

第二行有 $n$ 个数，表示每一堆石子的数量.

输出格式

共 $T$ 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

2
2
1 1
2
1 0

输出 #1

No
Yes

解题思路

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

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

定理1：

• 若 $a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n=0$，则先手必败。
• 若 $a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n\ne 0$，则先手必胜。

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

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

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

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

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

AC Code

#include <bits/stdc++.h>
using namespace std;void solve(){int n;cin >> n;int res = 0;for(int i=1;i<=n;i++){int x;cin >> x;res ^= x;}if(res){cout << "Yes\n";}else{cout << "No\n";}
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin >> t;while(t--){solve();}return 0;
}

P3480 [POI 2009] KAM-Pebbles

https://www.luogu.com.cn/problem/P3480

题目描述

有 $N$ 堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。

输入格式

多组输入，第一行一个整数 $u$ 代表数据组数（$1\le u\le 10$）

接下来共 $2u$ 行，每两行代表一组数据：

第一行只有一个整数 $n$（$1\le n\le 1000$），表示石子堆数；

第二行有 $n$ 个整数用空格隔开，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆的石子个数，保证 $a_1\le a_2\le a_3\le \cdots \le a_n$。

对于每组数据，保证石子总数不超过 $10000$。

输出格式

输出 $u$ 行，如果第 $i$ 组数据先手必胜，输出 TAK，否则输出 NIE。

输入输出样例 #1

输入 #1

2
2
2 2
3
1 2 4

输出 #1

NIE
TAK

解题思路

设 $a[i]$ 表示第 $i$ 堆石子的个数，$c[i]$ 表示 $a[i]-a[i-1]$，则我们每堆可以拿的石子数即为 $c[i]$。当我们在第 $i$ 堆拿了 $x$ 个时，$c[i]$ 变成了 $c[i]-x$，$c[i+1]$ 变成了 $c[i+1]+x$，相当于我们把第 $i$ 堆中可拿的石子转移到了 $i+1$ 堆，由此我们可以把此题转化为一道反着的阶梯 Nim 游戏。

下面简单讲解一下阶梯 Nim，如果不懂的话可以去网上搜一下。

阶梯 Nim 是指，有 $n$ 堆石子，每次我们可以从第 $i$ 堆的石子中拿走一部分放到第 $i-1$ 堆中，或者把第 $1$ 堆中的石子拿走一部分，无法操作的人算输。先说结论：阶梯 Nim 的游戏结果与只看奇数堆的石子数的普通 Nim 结果相同。

假设我先手，那么我可以按照必胜策略把奇数堆中的石子转移到偶数堆，当对方拿的时候我们分情况讨论：

• 对方拿奇数堆中的石子到偶数堆，相当于进行对于奇数堆的普通 Nim，我们继续按照必胜策略拿奇数堆中的石子；
• 对方把偶数堆的石子拿到奇数堆，则我们可以把这部分石子继续向下拿，对于奇数堆相当于局势没有变动。

以上，我们简单证明了阶梯 Nim 与奇数堆普通 Nim 的等价。

AC Code

#include <bits/stdc++.h>
using namespace std;void solve(){int n;cin >> n;vector<int> a(n+1,0);int res = 0;for(int i=1;i<=n;i++){cin >> a[i];int diff = a[i]-a[i-1];if((n-i)%2==0){res ^= diff;}}if(res){cout << "TAK\n";}else{cout << "NIE\n";}
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int u;cin >> u;while(u--){solve();}return 0;
}