巴什博弈（hdu 1846，2147，2149，2188）
一堆石子有n个，两个人轮流取1~m个。不能拿的时候就输了，问先手与后手谁必败？
分析：
n<=m：先手直接取光，先手胜；
n=m+1：先手取x个，则后手可取m+1-x个，后手必胜；
结论:对于n=(m+1)*s+r(r<=m)：①r==0时，后手必胜，②r！=0时，先手必胜。
1 bool bash(int n,int m) 2 { 3 if(n%(m+1)) return 1; 4 return 0; 5 }
斐波那契博弈(hdu 2516)
两个顶尖聪明的人在玩游戏，有一堆石子，先手第一次可以拿任意多个但不能全拿走也不能不拿，之后每个人最少拿一个，最多拿前一个人两倍那么多个，谁取到最后一个谁就能获胜，请问先手后手谁必胜？
结论：当n不为斐波那契数时，则先手胜。
eg：fib【i】:1,2,3,5,8,13,21,34,55,89
齐肯多夫定理:任一正整数可以分为若干个不连续的fib数之和。
83 位于55~89 ->83=55(√)+28->28=21(√)+7->7=5(√)+2(√) 先手先取2个石子，那后手只能取1-4个，则5个中的最后一个一定是由先手取走的...那最后取走55的最后一个的一定是先手。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int fib[50]; 4 int main() 5 { 6 fib[0]=1,fib[1]=2; 7 for(int i=2;i<50;i++) 8 { 9 fib[i]=fib[i-1]+fib[i-2]; 10 } 11 int n; 12 while(cin>>n) 13 { 14 if(n==0)break; 15 bool flag=0; 16 for(int i=0;i<50;i++) 17 { 18 if(n==fib[i]){flag=1;puts("Second win");break;} 19 if(fib[i]>n)break; 20 } 21 if(!flag) puts("First win"); 22 } 23 }
威佐夫博弈(poj1067)
2堆石子，每人每次可以拿走任意一堆中任意数量的石子或在两堆石子中拿走相同数量的石子，不能拿的人输，请问先手与后手谁必胜？
结论：不满足公式则先手胜。
有石子数量a,b;公式：int(abs(b-a)*(sqrt(5.0)+1)/2)==min(a,b)
1 #include<iostream> 2 #include<stdio.h> 3 #include<cmath> 4 using namespace std; 5 int main() 6 { 7 int a,b; 8 while(cin>>a>>b) 9 { 10 if(a>b)swap(a,b); 11 double x=(sqrt(5.0)+1)/2; 12 int c=int((b-a)*x); 13 if(c!=a) puts ("1"); 14 else puts("0"); 15 } 16 }
nim博弈（hdu1850 cf-gym102302G）
n堆石子，每人每次可以拿走任意一堆中的任意多个石子但不能不取，不能拿的人输，请问先手与后手谁必胜？
结论：异或值不为0，先手胜。
1 //一旦左边有则不能清空，所以a没有限制，而b、c分别拿出一个石子即可，因为总共拿了两颗为偶数，所以不影响结果 2 #include<iostream> 3 #include<stdio.h> 4 using namespace std; 5 #define int long long 6 signed main() 7 { 8 int m,a,b,c; 9 cin>>m>>a>>b>>c; 10 m++; 11 a%=m; 12 b=(b-1)%m; 13 c=(c-1)%m; 14 if((a^b^c)!=0) puts("Tomaz"); 15 else puts("Danftito"); 16 }
原文：https://www.cnblogs.com/Calculus9/p/12304698.html
