关于NIM问题的看法:
游戏规则有以下三条:
1、一共有n堆物品
2、两个人轮流取其中一堆物品的k数量(不能为0)
3、最后取完的获胜
首先最后的状态必然是 全为0
用异或的思想 ^表示异或
最后必然是 0^0^0^0……0^0 = 0;
对于任意时刻的状态分析,都可以为
a1^a2^a3^a4……an-1^an
记上列式子为p
设除了ai外的其他数字异或和为 q
如果 p = 0
那么进行任何操作都会对p造成影响,从而导致p不等于0,由于异或的规则,我们可以得到 ai^q = 0,ai = q,那么改变任何一个数的话,ai != q, 所以ai’ ^ p的结果必然不是0
相对的,如果 p != 0,那么只要改变其中一个数字,那么我们只要把ai变成了q就可以解决这个问题。
如何把ai 变成q,我们可以知道位运算都是在自己的位置上进行运算,不影响其他位置,那么我们可以把最大值设为ai,则可以得到相对应的q
如果p = 0 的情况下,对手任意行为,都会破坏掉p = 0的情况, 我们只要进行p!=0时候的操作,即可使得p=0,所以谁先到达p=0的情况,谁就获胜(也就是如果一开始p!=0,先手获胜)
C++ 代码
#include <iostream>
using namespace std;
int main(){
int n,ret=0,a;
cin >> n;
while(n--){
cin >> a;
ret = ret^a;
}
if(ret) cout << "Yes";
else cout << "No";
}