寒假延期补题 博弈论
参考自ac-data的文章
博弈论类问题的三大特点；
- 博弈模型为两人轮流决策的非合作博弈。
即两人轮流进行决策，并且两人都使用最优策略来获取胜利。
- 博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负。
- 公平博弈。即两人进行决策所遵循的规则相同。
常见类型详解：
巴什博弈
1、问题模型：只有一堆n个物品，两个人轮流从这堆物品中取物，
规定每次至少取一个，最多取m个，最后取光者得胜。
2、解决思路：当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，
后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是
n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)*r+s，
（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，
那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，
那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
3、变形：条件不变，改为最后取光的人输。
结论：当（n-1）%（m+1）==0时后手胜利。
4、题目练习：HDU 2188 2149 1846
if(n%(m+1))
printf("Grass\n");
else
printf("Rabbit\n");
o r
printf(n%(m+1)?"Grass\n":"Rabbit\n");
晚点补，先想想马拉车。。。难受
2. 威佐夫博奕
3. Fibonacci博弈
4. 尼姆博弈
5. 公平组合博弈（Impartial Combinatori Games）
作者：摩尔斯
