AcWing 893. 集合-Nim游戏
本题链接：AcWing 893. 集合-Nim游戏
本博客提供本题截图：
本题分析
1.Mex运算:
设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;
2.SG函数
在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····
yk的SG函数值构成的集合在执行mex运算的结果,即:
SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
AC代码
#include <cstring> #include <iostream> #include <algorithm> #include <unordered_set> using namespace std; const int N = 110, M = 10010; int n, m; int s[N], f[M]; int sg(int x) { if (f[x] != -1) return f[x]; //记忆化搜索，因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可 unordered_set<int> S; //注意，因为是在函数内部定义的set，所以每次递归中的S是不一样的 for (int i = 0; i < m; i ++ ) { int sum = s[i]; if (x >= sum) S.insert(sg(x - sum)); //先遍历至终点，然后倒推求sg } for (int i = 0; ; i ++ ) if (!S.count(i)) return f[x] = i; } int main() { cin >> m; for (int i = 0; i < m; i ++ ) cin >> s[i]; cin >> n; memset(f, -1, sizeof f); 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; }
AcWing 894. 拆分-Nim游戏
本题链接：AcWing 894. 拆分-Nim游戏
本博客提供本题截图：
本题分析
本题相比于上一题，为一个情况拆分成了多个的小情况，根据sg函数，我们需要存储的状态为sg(i) ^ sg(j)
AC代码
#include <cstring> #include <iostream> #include <algorithm> #include <unordered_set> using namespace std; const int N = 110; int n; int f[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() { cin >> n; memset(f, -1, sizeof f); int res = 0; while (n -- ) { int x; cin >> x; res ^= sg(x); } if (res) puts("Yes"); else puts("No"); return 0; }
三、时间复杂度
关于博弈论各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
