一、理论知识
-
(mex)函数定义
对于集合(S),(mex(S)=mex({x1,x2…}))表示(S)中没有出现的最小非负整数。
例如:(S={0,1,2,4}),那么(Mex(S)=3)。
-
(sg)函数定义
(sg(n)=mex({sg(i_1),sg(i_2),sg(i_3)...}))。 (n)为结点;(i_1,i_2,i_3)…是(n)的后继结点。 -
规定
(sg(G)=sg(head))。 (G)是一个有向图,(head)是(G)的头结点。 -
结论
(sg(G1)) ^ (sg(G2)) ^ (sg(G3)) ^ (…) ^ (sg(Gn))为(n)个有向图的异或和,对于(n)个有向图游戏,这个异或和就是它的答案。
二、实例解析
(SG)函数是解决博弈论问题的一把利器。
三、(SG)函数复用的原因
四、完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 10010;
int n, k;
int s[N]; //一共几种取法,比如一次取2个或5个。
int f[M]; //SG函数的值
int res;
//记忆化搜索来做,保证每个状态只被算一次
int sg(int x) {
//记忆化搜索
if (f[x] != -1) return f[x];
//当前状态下,可以到的所有状态
unordered_set<int> S;
//遍历每一个可能的数字
for (int i = 0; i < k; i++)
if (x >= s[i]) S.insert(sg(x - s[i]));
//找出集合中不存在的这个自然数
for (int i = 0;; i++)
if (!S.count(i))
return f[x] = i;
}
int main() {
//优化输入
ios::sync_with_stdio(false);
//初始化数组值为-1
memset(f, -1, sizeof f);
cin >> k; //表示数字集合 S 中数字的个数
for (int i = 0; i < k; i++) cin >> s[i];
cin >> n;//一共几堆
//n堆石子,每堆石子都取SG值,然后异或在一起
for (int i = 0; i < n; i++) {
int x;
cin >> x; //每堆里多少个
res ^= sg(x);
}
if (res) puts("Yes"); //如果不是零,必胜
else puts("No"); //如果是零,必败
return 0;
}