博弈论

巴什博弈

有 (n) 个石子，轮流拿，每次拿 ([1,m]) 个，不能拿的输

分两种情况讨论：

(n = k * (m + 1)), 先手拿 (x) 个，后手总是可以拿 (m + 1 - x) 个，先手必败
(n = k * (m + 1) + r), 先手拿走 (r) 个后转化成第一个局面，此时先手必胜

hdu1846

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;

int T, n, m;

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	T = read();
	while(T--){
		n = read(), m = read();
		if(n % (m + 1) == 0) printf("second
");
		else printf("first
");
	}
	return 0;
}

hdu4764

转化一下即可

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;

int T, n, m;

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	while(1){
		n = read(), m = read();
		if(n == 0 && m == 0) break;
		--n;
		if(n % (m + 1) == 0) printf("Jiang
");
		else printf("Tang
");
	}
	return 0;
}

(NIM)游戏

有 (n) 堆石子，每次必须从一堆中取任意数量石子，不能不取，取走最后一个石子的人获胜

结论：所有石子数量异或和为 (0) 则先手必败，否则先手必胜

拓展：阶梯 (nim) 游戏

有(n)个位置(1...n)，每个位置上有(a_i)个石子。有两个人轮流操作。操作步骤是：挑选(1...n)中任一一个存在石子的位置(i)，将至少(1)个石子移动至(i−1)位置（也就是最后所有石子都堆在在(0)这个位置）。谁不能操作谁输。求先手必胜还是必败。

结论：奇数位置石子数量异或和为(0)则先手必败，否则先手必胜

证明：双方都只移动奇数位置石子，相当于在玩(nim)游戏，否则必定可以移动相同数量的石子重新回到奇数位置石子数量不变的局面

poj1704

将两个棋子直接的空格看作石子，每次向左移动棋子，相当于向右移动石子，于是将最右端的空格子看作第一堆石子，就是阶梯(nim)游戏了

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long ll;

const int maxn = 1010;

int T, n;
int a[maxn], b[maxn];

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	T = read();
	while(T--){
		memset(b, 0, sizeof(b));
		int ans = 0, n;
		n = read();
		for(int i = 1 ; i <= n ; ++i) a[i] = read();
		sort(a + 1, a + 1 + n);
		for(int i = n ; i >= 1 ; --i) b[n - i + 1] = a[i] - a[i - 1] - 1;
		for(int i = 1 ; i <= n ; i += 2) ans ^= b[i];
		if(ans) printf("Georgia will win
");
		else printf("Bob will win
");
	}
	return 0;
}

SG函数

(SG(x) = mex{SG(y)|x 能到达 y})
(mex(S)) 运算表示 (S) 中未出现的最小的非负整数
一个组合游戏的所有游戏局面的 (SG) 的异或和如果为 (0),则先手必败，否则先手必胜

hdu1848

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1010;

int a, b, c;
int f[30], SG[maxn], S[maxn];

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	f[0] = 0, f[1] = 1;
	for(int i = 2 ; i <= 20 ; ++i) f[i] = f[i - 1] + f[i - 2];
	
	for(int i = 1 ; i <= 1000 ; ++i){
		memset(S, 0, sizeof(S));
		for(int j = 1 ; j <= 20 && f[j] <= i ; ++j) S[SG[i - f[j]]] = 1;
		for(int j = 0 ; j <= i ; ++j) {
			if(!S[j]) {
				SG[i] = j;
				break;
			}
		}
	}
	
	while(1){
		a = read(), b = read(), c = read();
		if(!a && !b && !c) break;
		if(SG[a] ^ SG[b] ^ SG[c]) printf("Fibo
");
		else printf("Nacci
");
	}
	return 0;
}