台阶型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游戏即可，文章来源：https://www.toymoban.com/news/detail-620833.html
必胜状态 a 1 ∧ a 3 . . . ∧ a n ! = 0 a_1 \land a_3 ...\land a_n!=0 a1∧a3...∧an!=0文章来源地址https://www.toymoban.com/news/detail-620833.html
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int 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;
}
到了这里，关于台阶型Nim游戏博弈论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![博弈论-策略式博弈矩阵、扩展式博弈树 习题 [HBU]](https://imgs.yssmx.com/Uploads/2024/02/774600-1.png)
