• 欢迎光临~

[博弈论专题] AcWing 891 Nim游戏

开发技术 开发技术 2022-07-23 次浏览

看了很多的博客,终于对Nim游戏中的异或操作有些认识。。。

首先对于Nim游戏,需要明确两点,一点是如果剩下全是0,则是必败态。一点是如果有两个完全相同的状态,则它们合起来的状态是一个必胜态,即后手能完全模仿先手在对称的堆中进行操作。这就可以通过异或来操作

对于本题最简单的Nim游戏,只要最后的异或和为0就一定是必败态,因为我们看每一位上1的个数都是偶数位,因此我们只要对某个数中的1进行操作了,后手就能作出操作使所有数的异或和再次变成0,使先手总是保持必败的状态。

因此在本题中,只要异或和不为0就是必胜态,只要异或和为0就是必败态。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 int n,ans,t;
 4 int main(){
 5     int i,j;ans=0;
 6     scanf("%d",&t);
 7     while (t--){
 8         scanf("%d",&n);
 9         ans^=n;
10     }
11     if (ans) printf("Yesn");
12     else printf("Non");
13     return 0;
14 }

 

程序员灯塔
转载请注明原文链接:[博弈论专题] AcWing 891 Nim游戏
喜欢 (0)