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\n"):printf("Yes\n");
}
return 0;
}
临时还没有做太多题目,以后做多了慢慢补吧
估计没几个人能一眼秒吧233
题解