博弈问题之三种基础博弈小结
博弈论：
·博弈论（Game Theory），亦名“对策论”、“赛局理论”，属应用数学的一个分支， 博弈论已经成为经济学的标准分析工具之一。目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。 博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。
一、基础博弈：
（一）巴什博弈：
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。
例题：
HDU2149 Public Sale
题意中文我就不多说了，自己看。这是一个典型的巴什博弈，只要m%(n+1)==0就是后手赢。难点在于先手赢的情况是要输出所有可能的第一次出价情况。需要判断n是否大于等于m，如果n>=m则m~n的所有数都是符合情况的，而m>n时，第一次取的是m除以(n+1)的余数，因为只有让后手者保持(n+1)的倍数才能先手必胜。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<set>#include<vector>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i<b;++i)#define N 1000000007using namespace std;inline void RD(int &ret){ char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); }}inline void OT(int a){ if(a>=10) { OT(a/10); } putchar(a%10+'0');}int main(){ int t,n,a[10001],s,i; RD(t); while(t--) { RD(n); s=0; FOR(1,n,i) { RD(a[i]); } if(n%2==1) { a[++n]=0; } sort(a+1,a+n+1); for(i=n; i>=1; i-=2) { s^=(a[i]-a[i-1]-1); } if(s!=0) { printf("Georgia will win\n"); } else { printf("Bob will win\n"); } } return 0;}