$\Huge\color{orchid}{点击此处获取更多干货}$
Nim游戏(阶梯版)
在阶梯上做Nim游戏,从某一级的石子中取出一部分放入下一级,其原理类似于一般的Nim游戏,但是当前所取石子的级数,会受到其奇偶性的影响而产生不同效果。造成这种结果的主要原因有两个:
1. 第1级上的石子移走后就处于地面上了,此时两位玩家均不能继续移动这些石子;
2. 按照最优方法,奇数级上的石子一定会由先手玩家移到地面,而偶数级上的石子会由后手玩家移到地面。
下面以石子序列$\{3,1,5,2,4\}$为例,分析奇数级与偶数级在移动时产生的效果:
在经典Nim游戏中,序列$\{3,5,4\}$为先手必胜的情况,因为只要先手取走第1级上的2枚石子,并且此后每次都与后手取相同数量的石子,先手就可以保证获胜。因此在本问题中,先手也只需要仿照之前的样子,将2枚石子移到地面,就可以保证获胜了。此时奇数级上的石子数异或和为0,如果后手继续从奇数级上移动石子,那么先手只要继续保持奇数级石子数异或和为0即可;如果后手从偶数级上移动石子,由于偶数级的石子不可能仅用一次移动就移到地面,因此先手只需要将后手刚刚移动过的石子继续移到偶数级上(包括地面)即可
C++ 代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
size_t x, ans = 0;
for (int i = 0; i < n; i++) {
cin >> x;
if (i % 2 == 0) ans ^= x;
}
cout << ((ans != 0) ? "Yes" : "No") << endl;
return 0;
}