做网站php中国企业网官方网站
台阶型Nim游戏
题目
https://www.acwing.com/problem/content/894/
现在，有一个 n n n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i i i 级台阶上有 a i a_i ai 个石子( i ≥ 1 i \ge 1 i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n n n。
第二行包含 n n n 个整数，其中第 i i i 个整数表示第 i i i 级台阶上的石子数 a i a_i ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105,
1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109
输入样例：
3
2 1 3
输出样例：
Yes
思路
将奇数位置上面的数看成是Nim游戏即可，
必胜状态 a 1 ∧ a 3 . . . ∧ a n ! = 0 a_1 \land a_3 ...\land a_n!=0 a1∧a3...∧an!=0
代码
#include <bits/stdc++.h>#define int long long
using namespace std;signed main() {
#ifndef ONLINE_JUDGEfreopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#endifint n, res = 0, x;cin >> n;for (int i = 1; i <= n; ++i) {cin >> x;if (i & 1) res ^= x;}cout << (res ? "Yes" : "No") << endl;return 0;
}