解题思路
这道题是Nim游戏的变形,突破口就是分奇偶次移动,那么对于在偶数位的台阶,要想移动到地面,一定要移动偶数次,那么假如说现在只剩下偶数位上有石子,这时候谁是先手谁必败,对于后手的操作,只需将先手操作的石子数再向下移动 @[]一个台阶即可。那么这是时候只考虑奇数位上的石子即可,这就转化成了Nim游戏。
Nim 游戏:对于先手来说只需要构建出所有石子数的异或值为0即可,最特殊的就是将所有石子的数量控制在相同数量,这时候异或值就是0,并且这种局面无论先手怎么操作,后手只需要在对应的位置上进行同样的操作即可,这就是所谓的镜像操作。
对于博弈论这种题目:主要看思想,可以从以下几个方面入手:
1. 可以考虑奇偶,优先考虑;
2. 找出镜像操作是怎么操作的;
3. 找出什么时候是必败状态;
4. 对应找出必胜态;
5. 判断先手处于什么状态即可。
这种题的代码不会复杂
AC代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int res = 0;
for(int i = 1;i <= n;i++) {
int t;
cin>>t;
if(i%2) res ^= t;
}
if(res) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}