【题目来源】https://www.acwing.com/problem/content/894/【题目描述】现在有一个 n 级台阶的楼梯每级台阶上都有若干个石子其中第 i 级台阶上有 ai 个石子(i≥1)。两位玩家轮流操作每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中不能不拿。已经拿到地面上的石子不能再拿最后无法进行操作的人视为失败。问如果两人都采用最优策略先手是否必胜。【输入格式】第一行包含整数 n。第二行包含 n 个整数其中第 i 个整数表示第 i 级台阶上的石子数 ai。【输出格式】如果先手方必胜则输出 Yes。否则输出 No。【输入样例】32 1 3【输出样例】Yes【数据范围】1≤n≤10^51≤ai≤10^9【算法分析】● Nim 博弈定理对于任意的 {a1, a2, a3, …, an}若 Sa1⊕a2⊕a3⊕⋯⊕an 的值不等于 0先手必胜记为 N-position先手必胜态。若 Sa1⊕a2⊕a3⊕⋯⊕an 的值等于 0先手必败记为 P-position先手必败态。● 台阶 NimStaircase Nim设有编号为 0,1,2,…,n 的台阶其中 0 号为地面。每个台阶上放有若干枚石子。两名玩家轮流操作。每次操作任选一个台阶 ii≥1将该台阶上任意数量的石子移动到台阶 i−1 上。将最后一枚石子移到 0 号地面的玩家获胜。●设台阶 Nim 中奇数台阶上的石子数为 a1, a3, a5, …。且令 Sa1⊕a3⊕a5⊕…若 S≠0则当前局面为先手必胜态N-position。若 S0则当前局面为先手必败态P-position。证明任何一步只能把石子从台阶 i 移到 i−1。分两种情况讨论情况 A操作发生在偶数台阶 i从偶数台阶 i 移石子至奇数台阶 i−1会使该奇数台阶石子数增加看似改变 S。但后手可立即将这些石子从 i−1奇数台阶继续移至 i−2偶数台阶使所有奇数台阶的石子数复原S 保持不变。这意味着偶数台阶上的任何操作都可以被后手抵消不影响最终胜负。情况 B操作发生在奇数台阶 i从奇数台阶 i 移石子至偶数台阶 i−1等价于在经典 Nim 游戏中从对应堆里移除若干石子。因为移入偶数台阶的石子会进入可被抵消的区域不再对胜负产生实质影响。因此只有奇数台阶石子数的变化才真正决定局面走向。综上台阶 Nim 等价于仅以奇数台阶为石子堆的经典 Nim 游戏。● 异或运算的基本性质https://blog.csdn.net/hnjzsyjyj/article/details/154304346异或运算XOR具有以下重要性质交换律a ^ b b ^ a结合律a ^ (b ^ c) (a ^ b) ^ c自反性a ^ a 0零元素a ^ 0 a可逆性如果 a ^ b c那么 a c ^ b【算法代码】#include bits/stdc.h using namespace std; int main() { int n,t0; cinn; for(int i1; in; i) { int x; cinx; if(i1) t^x; } if(t0) coutNo\n; else coutYes\n; return 0; } /* in: 3 2 1 3 out: Yes */【参考文献】https://www.acwing.com/solution/content/13187/https://blog.csdn.net/hnjzsyjyj/article/details/154304346https://www.acwing.com/file_system/file/content/whole/index/content/12084580/https://blog.csdn.net/hnjzsyjyj/article/details/158704426https://blog.csdn.net/hnjzsyjyj/article/details/154310120