原题链接
Nim游戏
设n堆石子的个数分别为:$[a_1,a_2,a_3,...,a_n]$,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
结论
若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \neq 0 $ 则先手必胜
若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $ 则先手必败
证明
- 当所有石子个数都为0时:$ 0 \oplus 0 \oplus 0 ... \oplus 0 = 0$
- 当n堆石子的个数分别为:$[a_1,a_2,a_3,...,a_n]$时
2.1 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = x \neq 0 $
下证存在一种方法,可以使得$ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $
假设二进制表示下x的最高位1是第k位,那么在$[a_1,a_2,a_3,...,a_n]$中一定存在一个$a_i$在二进制表示下的第k位也为1
因此有: $a_i \oplus x < a_i$ 此时我们从第i堆石子中拿走$a_i - (a_i \oplus x) 个石子$
第i堆石子还剩下: $a_i - [a_i - (a_i \oplus x)] = a_i \oplus x$个石子
此时 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_i ... \oplus a_n \oplus x = x \oplus x = 0 $
由此可得在2.1情况下,我们可以通过在第i堆石子中拿取$a_i - (a_i \oplus x) 个石子$就可以使得每堆石子的异或值变为0
2.2 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $ $(1)$
下面采用反证法证明无论我们如何操作,异或值都无法保持为0,只能大于0。
假设我们通过某种操作之后,$a_i$变成了$b_i (b_i < a_i )$
并且 $ a_1 \oplus a_2 \oplus a_3 \oplus b_i \oplus ... \oplus a_n = 0 $ $(2)$
此时(1)式 $\oplus$ (2)式 = $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \oplus a_1 \oplus a_2 \oplus a_3 \oplus b_i \oplus ... \oplus a_n = a_i \oplus b_i = 0$
得到$ a_i \oplus b_i = 0 即 a_i = b_i$ $(3)$
又因为$ b_i < a_i $ $(4)$
(3)试与(4)式矛盾,说明无论我们如何操作,异或值都无法保持为0,只能大于0
3.下证
若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \neq 0 $ 则先手必胜
若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $ 则先手必败
3.1 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n \neq 0 $,先手选手通过某种操作直接将异或值变为0,而后手选手无论如何操作都无法将异或值保持为0,所以下一轮先手选手开始操作的时候异或值还是不为0,因此先手选手得到的状态永远都大于0,不可能是$ 0 \oplus 0 \oplus 0 ... \oplus 0 = 0$,所以此时先手必胜
3.2 若 $ a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_n = 0 $,先手选手无论如何操作都无法把状态保持为0,后手选手得到的状态永远不为0,所以$ 0 \oplus 0 \oplus 0 ... \oplus 0 = 0$一定会被先手选手遇到,所以此时先手必败
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,res = 0;
cin>>n;
while(n--)
{
int x;
cin>>x;
res ^= x;
}
if(res) puts("Yes");
else puts("No");
return 0;
}
想想你的文章写的特别好https://www.ea55.com/
看的我热血沸腾啊https://www.237fa.com/