ACM博弈论

前段时间一直在看博弈方面的题，特此总结一下，随着知识积累，我会进一步的补充完整这篇文章

一、巴什博弈

问题描述：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

分析：同余定理：n=K*(m+1)+r;先取者拿走r个，那么后者无论拿(1~m)多少个，设为Q个，先者只要拿的数目P使得Q+P=m+1，先手必赢。

二、威佐夫博弈

问题描述： 有两堆各若干物品，两个人轮流从任意一堆中至少取出一个或者从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜。

结论：黄金分割比，首先求出两堆物品的差值，若差值乘黄金分割比等于最小值则后手赢，否则先手赢。

三、尼姆博弈

问题描述： 有n堆物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜。

结论：将n堆物品数量全部异或后结果为0则必败，否则必胜。

四、SG定理（Sprague-Grundy定理）

当问题比较复杂时，我们可以利用SG函数来寻找规律。下面列举一些比较有意义的题目：

例题1：HDU1848

参考答案：

#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "sstream"
#include "algorithm"
#include "map"

using namespace std;
const int maxn = 1010;
int P[maxn] = {};
int SG[maxn] = {0};
int F[maxn] = {0,1,1};
int VS[maxn] = { 0 };
int main()
{
	int a,b,c;
	for (int i = 3; i < 100; ++i)F[i] = F[i - 1] + F[i - 2];
	for (int i = 1; i < maxn; ++i){
		memset(VS,0,sizeof(VS));
		for (int j = 1; i-F[j] >=0; ++j){
			VS[SG[i - F[j]]] = true;
		}
		for (int j = 0; j < maxn; ++j){
			if (!VS[j]){ SG[i] = j; break; }
		}
	}
	while (scanf("%d%d%d", &a, &b, &c) == 3 && (a*a + b*b + c*c)){
		if (SG[a] ^ SG[b] ^ SG[c]) printf("Fibo\n");
		else printf("Nacci\n");
	}
	return 0;
}