博弈论真是一个神奇的东西，感觉和博弈论厉害的人玩游戏绝对会输. 这个博客讲的很好很全面
此类问题一般有如下特点：
1、博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利。
2、博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负。
3、公平博弈。即两人进行决策所遵循的规则相同。
（一般看到这类题就可以想到用博弈论了）
巴什博弈 : 分开讲的
1 : 巴什博弈 (对应一些题目: HDU 1846 2188 2149 2897 POJ 2368)
1、问题模型：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。 2、结论 : 当n%(m+1)==0，先手必输，否则先手必赢. 因为 : 当n%(m+1)==0,时，先手取i个，后手去m+1-i(这样是合法得，因为先手不能拿完，但是至少拿1)，这样一个回合就可以凑出m+1个， 而n%(m+1)==0，所以n/(m+1)回合 , 后手就能取到最后一个 . 当n%(m+1)=k,k>0,则先手去k个，此时石子回到n%(m+1)==0时， 先手和后手于上一种情况则交换拿的顺序（即在n%(m+1)==0情况下，“后手”先拿，所以"后手必输"）即实际的先手必胜 . 3、变形：条件不变，改为最后取光的人输。 结论：当（n-1）%（m+1）==0时后手胜利 （结论倒是和上面那个一样,只是公式变了）.模板题HDU 2897 AC代码(稍微多动动头就知道了)
/*若当前石子共有n %（p+q）==0 个，则A必胜，必胜策略为：A第一次取q个 , 以后每次若B取K个，A取（p+q-k）个，如此下去最后必剩下p个给B，所以A必胜。 若n %（p+q）== k 个（1<= k <= p）B必胜,必胜策略为：每次取石子活动中，若A取k个 , 则B取（p+q-k）个，那么最后剩下k个给A，此时 k <= p，所以A只能一次取完，B胜 . 若n %（p + q）== k 个 (p<k<=q) A 必胜 ，必胜策略为：A第一次取 t （1< k – t <= p）个, 以后每次B取k个，则A取（p+q-k）个，那么最后留下1 < k – t <= p给B，则A胜*/ #include<iostream> #include<cstdio> using namespace std; int main() { int n,p,q; while(scanf("%d %d %d",&n,&p,&q)!=EOF){ if(n%(p+q)==0) cout << "WIN" << endl; else if((n%(p+q))<=p) cout << "LOST" << endl; else cout << "WIN" << endl; } }2：尼姆博弈
1、问题模型：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜 2、解决思路：用（a，b，c）表示某种局势，显证（0，0，0）是第一种奇异局势，无论谁面对奇异局势，都 必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0） 搞定这个问题需要把必败态的规律找出：(a,b,c)是必败态等价于a^b^c=0(^表示异或运算） 证明:(1)任何p(a,b,c)=0的局面出发的任意局面(a,b,c’);一定有p(a,b,c’)不等于0。否则可以得到c=c’。 （2）任何p(a,b,c)不等于0的局面都可以走向 p(a,b,c)=0的局面 (3）对于 (4,9,13) 这个容易验证是奇异局势 4 = 0 4 0 1 9 = 8 0 0 1 13 = 8 4 0 1 其中有两个8，两个4，两个1，非零项成对出现，这就是尼姆和为 零的本质。别人要是拿掉13里的8或 者1，那你就拿掉对应的9 中的那个8或者1；别人要是拿掉13里的4，你就拿掉4里的4； 别人如果拿掉 13里的3，就把10作分解，然后想办法满 足非零项成对即可 3、推广一：如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只 要将 c 变为 a^b,即可,因为有如下的运算结果: a^b^(a^b)=(a^a)^(b^b)=0^0=0。要将c 变为a^b，只从 c中减 去 c-(a^b) 4、推广二：当石子堆数为n堆时，则推广为当对每堆的数目进行亦或之后值为零是必败态模板题（提示：推广二） AC Code
#include<cstdio> int main() { int n; while(~scanf("%d",&n)){ int t,k; scanf("%d",&t); for(int i=1;i<n;i++){ scanf("%d",&k); t^=k; } if(!t) printf("Lose\n"); else printf("Win\n"); } }SG博弈: 学习博客一 学习博客二 百度百科超好的讲解 Kuangbin博弈专题训练
