更好的阅读体验点这里
nim游戏
nim游戏
有两个顶尖聪明的人在玩游戏，游戏规则是这样的：
有(n)堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)，没法拿的人失败。问谁会胜利
nim游戏是巴什博奕的升级版(不懂巴什博奕的可以看这里)
它不再是简单的一个状态，因此分析起来也棘手许多
如果说巴什博奕仅仅博弈论的一个引子的话，
nim游戏就差不多算是真正的入门了
博弈分析
面对新的博弈问题，我们按照套路，从简单的情况入手
当只有一堆石子的时候，先手可以全部拿走。先手必胜
当有两堆石子且石子个数相同的时候，先手不论拿多少，后手都可以从另一堆中拿同样多的石子，先手必败，否则先手必胜
当有三堆的时候呢？
当有(n)堆的时候呢？
这样玩下去确实是很繁琐，不过前辈们总结出了一条非常厉害的规律！
定理解析
定理
对于nim游戏，前辈们发现了一条重要的规律！
当(n)堆石子的数量异或和等于(0)时，先手必胜，否则先手必败
证明
设(oplus)表示异或运算
nim游戏的必败态我们是知道的，就是当前(n)堆石子的数量都为零
设(a[i])表示第(i)堆石子的数量，那么当前局面就是
$0 oplus 0 oplus 0 oplus dots oplus 0 = 0 $
- 对于先手来说，如果当前局面是
(a_1 oplus a_2 oplus a_3 oplus dots oplus a_n = k)
那么一定存在某个(a_i)，它的二进制表示在最高位(k)上一定是(1)
我们将(a_i oplus k)，这样就变成了
(a_1 oplus a_2 oplus a_3 oplus dots oplus a_n oplus k = 0)
此时先手必胜
- 对于先手来说，如果当前局面是
(a_1 oplus a_2 oplus a_3 oplus dots oplus a_n = 0)
那么我们不可能将某一个(a_i)异或一个数字后使得
(a_1 oplus a_2 oplus a_3 oplus dots oplus a_n = 0)
此时先手必败
代码
#include<cstdio>
using namespace std;
int a[10001];
int main()
{
int Test;
scanf("%d",&Test);
while(Test--)
{
int ans=0,N;
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<=N;i++) ans=ans^a[i];
ans==0?printf("No
"):printf("Yes
");
}
return 0;
}
题目
临时还没有做太多题目，以后做多了慢慢补吧
估计没几个人能一眼秒吧233