HDU

Description

vjudge（传送门）

Solution

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) 那么当前回合的人必败，反之必胜。

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

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

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

这里我用的打表法求 (SG)，具体看代码吧。

Code

#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;
}

End