巴什博奕（Bash Game）：
A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。
其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，看谁先报到25了，进而变为20,15,10,5，当到5的时候，不管A怎么报数，最后一个数肯定是B报的，可以看出，作为后手的B在个游戏中是不会输的。
那么如果我们要报n个数，每次最少报一个，最多报m个，我们可以找到这么一个整数k和r，使n=k*（m+1）+r，代入上面的例子我们就可以知道，如果r=0，那么先手必败；否则，先手必胜。
巴什博奕：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜。
1 #include <iostream> 2 using namespace std; 3 int main(){ 4 int n,m; 5 while(cin>>n>>m) 6 if(n%(m+1)==0) cout<<"后手必胜"<<endl; 7 else cout<<"先手必胜"<<endl; 8 return 0; 9 }
------------------------------------------------------------------
威佐夫博弈（Wythoff Game）：
有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
直接说结论了，若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；
若w=x，则先手必败，否则先手必胜。
1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 using namespace std; 5 int main(){ 6 int n1,n2,temp; 7 while(cin>>n1>>n2){ 8 if(n1>n2) swap(n1,n2); 9 temp=floor((n2-n1)*(1+sqrt(5.0))/2.0); 10 if(temp==n1) cout<<"后手必胜"<<endl; 11 else cout<<"先手必胜"<<endl; 12 } 13 return 0; 14 }
------------------------------------------------------------------
尼姆博弈（Nimm Game）：
尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
结论就是：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。
1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 using namespace std; 5 int main(){ 6 int n,ans,temp; 7 while(cin>>n){ 8 temp=0; 9 for(int i=0;i<n;i++){ 10 cin>>ans; 11 temp^=ans; 12 } 13 if(temp==0) cout<<"后手必胜"<<endl; 14 else cout<<"先手必胜"<<endl; 15 } 16 return 0; 17 }
------------------------------------------------------------------
斐波那契博弈：
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 using namespace std; 5 const int N = 55; 6 int f[N]; 7 void Init() { 8 f[0] = f[1] = 1; 9 for(int i=2;i<N;i++) 10 f[i] = f[i-1] + f[i-2]; 11 } 12 int main() { 13 Init(); 14 int n; 15 while(cin>>n) { 16 if(n == 0) break; 17 bool flag = 0; 18 for(int i=0;i<N;i++) { 19 if(f[i] == n) { 20 flag = 1; 21 break; 22 } 23 } 24 if(flag) puts("Second win"); 25 else puts("First win"); 26 } 27 return 0; 28 }
------------------------------------------------------------------
Nim博弈sg函数
Get sg函数模板：
1 const int maxn = 1e5+10; 2 bool vis[maxn]; 3 int g[maxn]; 4 int f[maxn];//灵活运用 5 void init(){ 6 memset(g, 0, sizeof(g)); 7 for(int i = 1; i < maxn; ++i){ 8 memset(vis, false, sizeof(vis)); 9 for(int j = 1; f[j] <= i; ++j){ 10 vis[g[i-f[j]]] = true; 11 } 12 for(int j = 0; ; ++j){ 13 if(!vis[j]){ 14 g[i] = j; 15 break; 16 } 17 } 18 } 19 }
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
http://codeforces.com/contest/15/problem/C
Nim博弈延申
1 #include <iostream> 2 using namespace std; 3 #define ll long long 4 int main(){ 5 int n; 6 ll x, y, sum = 0; 7 scanf("%d", &n); 8 while(n--){ 9 scanf("%lld%lld", &x, &y); 10 if(x&1){ 11 sum ^= x; 12 x ++, y--; 13 } 14 while(y%4){ 15 sum ^= (x+y-1); 16 y --; 17 } 18 } 19 printf("%s ", sum ? "tolik" : "bolik"); 20 return 0; 21 }
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=33&problem=3060
sg函数打表找规律
打表：
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 const int maxn = 100; 5 #define ll long long 6 bool vis[maxn]; 7 int a[maxn]; 8 int main(){ 9 a[1] = 0; 10 for(int i = 2; i <= 30; ++i){ 11 memset(vis, false, sizeof(vis)); 12 for(int j = 1; j*2 <= i; ++j) vis[a[i-j]] = true; 13 for(int j = 0; ; ++j) if(!vis[j]){ 14 a[i] = j; 15 break; 16 } 17 printf("%d ", a[i]); 18 } 19 return 0; 20 }
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 const int maxn = 100; 5 #define ll long long 6 ll get(ll x){ 7 return x&1 ? get(x/2) : x/2; 8 } 9 int main(){ 10 int t, n; 11 ll x, sum; 12 scanf("%d", &t); 13 while(t--){ 14 sum = 0; 15 scanf("%d", &n); 16 for(int i = 0; i < n; ++i){ 17 scanf("%lld", &x); 18 sum ^= get(x); 19 } 20 printf("%s ", sum ? "YES" : "NO"); 21 } 22 return 0; 23 }
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
http://acm.hdu.edu.cn/showproblem.php?pid=1536
sg函数裸题
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 const int maxn = 1e4+10; 5 int s[maxn], g[maxn], m, x, xx, t; 6 bool vis[maxn]; 7 void init(){ 8 int i, j; 9 memset(g, false, sizeof(g)); 10 for(i = 1; i < maxn; ++i){ 11 memset(vis, false, sizeof(vis)); 12 for(j = 0; j < t; ++j){ 13 if(i-s[j] >= 0) vis[g[i-s[j]]] = true; 14 } 15 for(j = 0; ; ++j){ 16 if(!vis[j]){ 17 g[i] = j; 18 break; 19 } 20 } 21 } 22 } 23 int main(){ 24 while(~scanf("%d", &t) && t){ 25 for(int i = 0; i < t; ++i){ 26 scanf("%d", s+i); 27 } 28 init(); 29 scanf("%d", &m); 30 for(int i = 0; i < m; ++i){ 31 scanf("%d", &x); 32 int sum = 0; 33 while(x--){ 34 scanf("%d", &xx); 35 sum ^= g[xx]; 36 } 37 printf("%c", sum ? 'W' : 'L'); 38 } 39 printf(" "); 40 } 41 return 0; 42 }
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
http://qscoj.cn/problem/76/
找规律，，，先手想要必胜的话只能是一直取并且全部取完（否则必败）直到碰到零
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 int a[50]; 5 int main(){ 6 int n, x; 7 while(~scanf("%d", &n)){ 8 for(int i = 0; i < n; ++i){ 9 scanf("%d", a+i); 10 } 11 int r = 0, l = n-1, num = 0, num2 = 0; 12 while(a[r]) num ++, r ++; 13 while(a[l]) num2 ++, l --; 14 if(num&1 || num2&1) printf("YES "); 15 else printf("NO "); 16 } 17 return 0; 18 }
只有不断学习才能进步！