emmmmm，是因为在一次训练赛中看到了一道题， 然后就去学了一遍单独发出来把
在nim博弈的定义和证明上算法进阶讲的还是挺详细的， 上道题
洛谷P5675 [GZOI2017]取石子游戏
根据以上定义， 当Alice取完石子后的异或值不为0， 那么一定是一种必败的情况， 假如所取第一堆的数量为\(a_i\)， 而其他的石子的异或值大≥\(a_i\), 那么无论Alice怎么取， 都不会使异或值为0， 我们再看数据范围， 每堆石子的数量最多是200， 不超过\(2^8\), 那么我们可以枚举出第一堆所取哪一堆和其他堆石子的状态，设f[i][j]表示，前第i堆石子的状态是j的方案数，吗当然， 要求n遍， 以为要枚举每一堆作为第一堆， 这样， 这道题就完美解决了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, ans = 0, a[210], f[210][260];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) {
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int j = 1; j <= n; ++j) {
for (int k = 0; k < 256; ++k) {
if (i == j) f[j][k] = f[j - 1][k];
else f[j][k] = (f[j - 1][k] + f[j - 1][k ^ a[j]]) % mod;
}
}
for (int j = a[i]; j < 256; ++j)
ans = (ans + f[n][j]) % mod;
}
cout << ans << endl;
return 0;
}
我们继续看另一类博弈论游戏：
接下来我们引进SG函数
所以， 我们如果看到博弈论游戏， 可以先算出终止情况并赋值为0， 然后一步步的求出SG函数， 判断异或值， 注意的是一种情况的SG函数是根据所有子情况来算出的， 并且一定要看出等效的情况， 有时候abc和def其实是一样的， 这样会很节省时间
上训练赛的题
K. Alice and Bob-2
首先全为0的话肯定是必败的情况， 不为0的情况下我们就根据这两个条件暴力的去取数， 当然也必须要记忆化(PS: 在全为0的情况下， 我忘了return SG[x] = 0, 会T， 加上这句话后跑的飞快， 并且每次递归的时候记得排序， 因为是一种等效的情况， 否则会很浪费时间)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int t, n;
char ch[50];
map < vector < int > , int > SG;
inline bool check(vector < int > x) {
for (int i = 0; i <= 25; ++i)
if (x[i]) return false;
return true;
}
inline int Find(vector < int > x) {
if (SG.find(x) != SG.end()) return SG[x];
if (check(x)) return SG[x] = 0;
vector < int > a;
for (int i = 0; i <= 25; ++i) {
if (x[i]) {
vector < int > vec = x;
--vec[i];
sort(vec.begin(), vec.end());
a.push_back(Find(vec));
}
}
for (int i = 0; i <= 25; ++i) {
for (int j = 0; j <= 25; ++j) {
if (i == j) continue;
if (x[i] && x[j]) {
vector < int > vec = x;
--vec[i], --vec[j];
sort(vec.begin(), vec.end());
a.push_back(Find(vec));
}
}
}
sort(a.begin(), a.end());
for (int i = 0; ; ++i) {
bool flag = false;
for (int j = 0; j < a.size(); ++j) {
if (i == a[j]) {
flag = true;
break;
} else if (a[j] > i) break;
}
if (!flag) return SG[x] = i;
}
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
int ans = 0;
while (n--) {
vector < int > v;
for (int i = 0; i <= 25; ++i) v.push_back(0);
scanf("%s", ch + 1);
int len = strlen(ch + 1);
for (int i = 1; i <= len; ++i) ++v[ch[i] - 'a'];
sort(v.begin(), v.end());
ans ^= Find(v);
}
if (ans > 0) puts("Alice");
else puts("Bob");
}
return 0;
}