acwing891 nim游戏

#include<iostream>using namespace std;
const int N = 100010;int main() {int n;cin >> n;int res = 0;for (int i = 0; i < n; i++) {int x;cin >> x;res ^= x;}if (res)puts("Yes");else puts("No");return 0;
}

acwing892 台阶 nim游戏
如果是拿了偶数放到奇数上 那下一次就可以顺次把相应的拿到偶数阶上
使得奇数阶的个数保持不变

如果拿了奇数阶的 那可以拿对应的奇数阶的相同数量 总之 就是镜像的去拿
证明同上
这样就对方一定会面临0-0的局面 失败

#include<iostream>
using namespace std;int main() {int n;cin >> n;int res = 0;for (int i = 1; i <= n; i++) {int x;cin >> x;if (i % 2) {res ^= x;}}if (res)puts("Yes");else puts("No");
}

acwing893 集合 nim游戏

每个选手采取最优策略 什么是最优？
自己的思考：走到sg为0的状态 也就是将0留给对方（如果不对欢迎指正
因此 末尾的sg也一定是0 据此往前推出sg

#include <iostream>
#include <unordered_set>
#include <cstring>using namespace std;const int N = 110, M = 10010;int n, m;
int s[N], f[M];
//fx存储的是所有可能出现的sg的值
int sg(int x) {if (f[x] != -1)return f[x];//记忆化 如果当前的值已经求过那就直接返回unordered_set<int>S;//这里一定要开成局部变量 每一层进入的S是不同的s //个人理解是某个点对应的后面的有几种情况（size  然后每个情况的fx是什么 （内容for (int i = 0; i < m; i++) {if (x >= s[i])S.insert(sg(x - s[i]));//这一步可能比较难理解 建议自己debug}for (int i = 0; ; i++) {if (!S.count(i))return f[x] = i;}
}int main() {memset(f, -1, sizeof f);//初始化cin >> m;for (int i = 0; i < m; i++)cin >> s[i];cin >> n;int res = 0;for (int i = 0; i < n; i++) {int x;cin >> x;res ^= sg(x);//溯源}if (res)puts("Yes");else puts("No");return 0;
}

acwing894 拆分 nim游戏
多个独立局面的SG值，等于这些局面SG值的异或和

#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N = 110, M = 10010;
int f[N];
int n;
int sg(int x) {if (f[x] != -1)return f[x];unordered_set<int>S;for (int i = 0; i < x; i++) {for (int j= 0; j <= i; j++) {//避免重复 我们约定j比i≤S.insert(sg(i) ^ sg(j));}}for (int i = 0; ; i++) {if (!S.count(i))return f[x] = i;}
}int main() {memset(f, -1, sizeof f);cin >> n;int res = 0;for (int i = 0; i < n; i++) {int x;cin >> x;res ^= sg(x);}if (res)puts("Yes");else puts("No");return 0;
}