SG函数

首先我们定义 \(mex{}\) 运算，计算结果为除当前集合外的最小的非负整数（即包括0）。

例如 \(mex{1, 2, 4} = 0\)，\(mex{0, 1, 2} = 3\)。

SG函数就是这个运算的值。

假设在一个 \(DAG\) 上，\(SG[x] = mex{SG[y] | y 是 x 的后继}\)。若 \(SG[x] = 0\) 那么当前回合的人必败，反之必胜。

另一个例子，在取石子游戏中，能取的个数就是我们 \(max\) 中的值。

具体详见这位大佬的博客，个人认为讲的非常清楚 博弈论（SG）

求SG函数

打表法

例题：HDU 1847

vjudge（传送门）

这道题目中最多有1000张牌，每次只能拿 2 的倍数张，我们预处理能摸的牌数 \(2^0\) ~ \(2^9\) 即可。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1010;
int n;
int s[10], sg[N * 10], vis[N * 10];		//vis就是mex中的值

void getSG(int n){
	for(int i = 1; i <= n; i++){
		memset(vis, 0, sizeof(vis));
		for(int j = 0; j <= 9 && s[j] <= i; j++)
			vis[sg[i - s[j]]] = 1;		//i-s[j]是i的后继，即上文中提到的y
		for(int j = 0; j <= 9; j++)
			if(!vis[j]){				//第一个为0的非负整数就是SG值
				sg[i] = j;
				break;
			}
	}
}

int main(){
	for(int i = 0; i <= 9; i++)		//预处理
		s[i] = (1 << i);
	getSG(1000);					//求SG
	while(scanf("%d", &n) != EOF)
		puts(sg[n] ? "Kiki" : "Cici");
	return 0;
}

dfs法

例题：HDU 1536

vjudge（传送门）

Description：

首先输入 \(K\) 表示一个集合的大小 之后输入集合 \(s\) 表示对于这对石子只能取这个集合中的元素的个数。

之后输入一个 \(m\) 表示接下来对于这个集合要进行 \(m\) 次询问。

之后 \(m\) 行 每行输入一个 \(n\) 表示有 \(n\) 个堆 每堆有 \(x\) 个石子 问这一行所表示的状态是赢还是输 如果赢输入 \(W\) 否则 \(L\)。

多组输入，直到 \(k=0\) 时结束

Solution：

对于 \(n\) 堆石子，分别处理，最后让每一堆异或起来即可，如果不为0那么必胜状态，反之为必败状态。

\(dfs\) 时 \(sg\) 初值为 -1，集合 \(s\) 要从小到大排序。

#include<iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
const int M = 1e4 + 10;
int n, m, k;
int sg[M], s[N];

int getSG(int x){
	if(sg[x] != -1) return sg[x];
	bool vis[N] = {0};
	for(int i = 1; i <= k; i++)
		if(x >= s[i])
			vis[getSG(x - s[i])] = 1;		//x的后继向x转移
	for(int i = 0; i < N; i++)
		if(!vis[i]){
			sg[x] = i;
			break;
		}
	return sg[x];
}

int main(){
	while(scanf("%d", &k) && k){
		for(int i = 1; i <= k; i++)
			scanf("%d", &s[i]);
		sort(s + 1, s + 1 + k);
		scanf("%d", &m);
		memset(sg, -1, sizeof(sg));
		while(m--){
			scanf("%d", &n);
			int ans = 0, x;
			for(int i = 1; i <= n; i++){
				scanf("%d", &x);
				ans ^= getSG(x);
			}
			if(ans) printf("W");
			else  printf("L");
		}
		printf("\n");
	}
	return 0;
}

End