博弈论模板

Bash–两人从一堆a个石子里面轮流取石子，每次最多去b个，取到最后一个石子获胜

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int a, b,flag;
		scanf("%d%d", &a, &b);
		if (a % (b + 1) == 0)flag = 2;
		else flag = 1;
		if (flag == 1)printf("A\n");
		else printf("B\n");
	}
}

Nim–两人从n堆石子中任选一堆取石子，不得不取，可以把一堆直接去玩，拿到最后一颗石子得人获胜

int main() {
	int n;
	int stone, tag=0;
	scanf("%d", &n);
	while (n--) {
		
		scanf("%d", &stone);
		tag ^= stone;
	}
	// tag为0则为后⼿手赢，否则为先⼿手赢 
	if (tag == 0)printf("B\n");
	else printf("A\n");
}

威佐夫博弈–有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜

int main() {
	int n;
	int stone, tag=0;
	scanf("%d", &n);
	while (n--) {
		int a, b;
		scanf("%d%d", &a,&b);
		if (a < b)swap(a, b);
		int flag = (a - b)*(sqrt(5) + 1) / 2;  //黄金分割线
		//  如果flag == b，则为后⼿手赢，否则先⼿手赢（奇异局）
		if (flag == b)printf("B\n");
		else printf("A\n");
	}
}

SG打表

//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];     
void getSG(int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(hash,0,sizeof(hash));
        for(j=1;f[j]<=i;j++)
            hash[sg[i-f[j]]]=1;
        for(j=0;j<=n;j++)    //求mes{}中未出现的最小的非负整数
        {
            if(hash[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
    }
}

SG-DFS打表

int s[110],sg[10010],n;
int SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return sg[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));
    for(i=0;i<n;i++)
    {
        if(x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            e=i;
            break;
        }
    return sg[x]=e;
}

一般DFS只在打表解决不了的情况下用，首选打表预处理。