博弈論是很有意思的數(shù)學(xué)問(wèn)題爷耀，如果能夠懂其道理，短短幾行代碼就能將其本質(zhì)表示出來(lái)蜡娶。
目前我的感受就是：在一場(chǎng)博弈之中借浊，從結(jié)果向前推，會(huì)出現(xiàn)一個(gè)必?cái)B(tài)强饮，我們需要做的就是推測(cè)是先手還是后手能讓對(duì)方變成必?cái)B(tài)。
一、巴什博奕（Bash Game）
有一堆n個(gè)物品梧疲，A、B兩人輪流從中仍俗肌（1~m）個(gè)物品幌氮，最后取光者獲勝。
逆向思考胁澳，當(dāng)對(duì)手面對(duì)（m+1）這種情況時(shí)该互，無(wú)論如何不能獲勝【一定是m+1】，所以只要你能想辦法讓對(duì)手面對(duì)k（m+1）這種情況即可韭畸，即當(dāng)你面對(duì)（k（m+1）+r）時(shí)取走r宇智，易證r<m.
如果開(kāi)局n=k（m+1），那么先手必輸胰丁。
如果開(kāi)局n=k（m+1）+r随橘，那么先手必贏。
//A為先手
//N為總數(shù)锦庸，K為最多取的個(gè)數(shù)机蔗，輸出勝者
#include <cstdio>
int main()
{
int n;
int N,K;
scanf("%d", &n);
while(n--)
{
scanf("%d %d",&N,&K);
if(N%(K+1)) printf("A\n");
else printf("B\n");
}
return 0;
}
這是最簡(jiǎn)單的博弈問(wèn)題，我們可以思考一下如果將題目改為最后取的人失敗甘萧，同時(shí)我們將題目中的取東西的上下限改為更加普遍的（p~q）萝嘁。
在此，找了一道HDU-2897的題幔嗦。
//有n個(gè)物品酿愧，一次最少取p個(gè)，最多q個(gè)
//問(wèn)先手是否必贏
#include <stdio.h>
int main()
{
int n,p,q;
while(scanf("%d %d %d",&n,&p,&q)==3)
{
if(n%(p+q)==0) printf("WIN\n");
else if(n%(p+q)<=p) printf("LOST\n");
else printf("WIN\n");
}
}
當(dāng)n%（p+q）==0時(shí)邀泉，先手只需要拿q個(gè)即可必贏嬉挡。（當(dāng)后手取i個(gè)時(shí)，只需要保證一輪【后-先】取走之和為p+q）
當(dāng)n%（p+q）=k<=p時(shí)汇恤，先手拿i個(gè)庞钢，后手只需要拿（p+q-i）個(gè)，就能讓最后剩k個(gè)因谎，即先手必輸基括，即后手必贏。
當(dāng)n%（p+q）=k>=p【n=k*(p+q)+p+r】時(shí)财岔，先手去p個(gè)后风皿，與上種情況剛好相反河爹，先手必贏，即后手必輸桐款。
（將其轉(zhuǎn)換的套路掌握咸这，就可有任意變換）
二、威佐夫博弈（Wythoff Game）
有兩堆各若干的物品兩人輪流從中其中一堆取至少一件物品魔眨，至多不限媳维，或從兩堆中同時(shí)取相同件物品，規(guī)定最后取完者勝利遏暴。
結(jié)論：若兩堆物品的初始值為（x侄刽，y），且x<y,則另z=y-x朋凉；
記w=(int)[((sqrt(5)+1)/2)*z]; //變化方式
若w=x州丹，則先手必?cái)。駝t先手必勝侥啤〉卑龋·
（奇異局）
當(dāng)（0，0）時(shí)盖灸，先手必?cái)。?】
當(dāng)（1磺芭，2）時(shí)赁炎，先手必?cái)。?】
當(dāng)（3钾腺，5）時(shí)徙垫，先手必?cái)。?】
當(dāng)（4放棒，7）時(shí)姻报，先手必?cái)。?】
當(dāng)（6间螟，10）時(shí)吴旋，先手必?cái)。?】
當(dāng)（8厢破，13）時(shí)荣瑟，先手必?cái)。?】
當(dāng)（9摩泪，15）時(shí)笆焰，先手必?cái)。?】
當(dāng)（11见坑，18）時(shí)嚷掠，先手必?cái)∧蠹欤?】
......
#include <cstdio>
#include <cmath>
int main()
{
long long n1,n2,n,temp;
scanf("%lld",&n);
while(n--)
{
scanf("%lld %lld",&n1,&n2);
if(n1>n2)
{
temp=n1;
n1=n2;
n2=temp;
}
temp=(n2-n1)*(1+sqrt(5))/2;
if(temp==n1) printf("B\n");
else printf("A\n");
}
return 0;
}
提示：1.618=（sqrt（5）+1）/ 2。
勝者只需要將非奇異局變?yōu)槠娈惥旨纯伞?/p>
三不皆、尼姆博弈（Nimm Game）
有任意堆物品贯城，每堆物品的個(gè)數(shù)是任意的，雙方輪流從中取物品粟焊，每一次只能從一堆物品中取部分或全部物品冤狡，最少取一件，取到最后一件物品的人獲勝项棠。
結(jié)論：將每堆物品全部異或起來(lái)悲雳，如果得到的值為0，先手必?cái)∠阕罚駝t先手必勝合瓢。
個(gè)人認(rèn)為可以通過(guò)逆向判斷，直接判斷奇偶數(shù)（用異或）透典。
# include<stdio.h>
int main()
{
int N,n,ans=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&N);
ans=ans^N;
}
if(ans) printf("A");
else printf("B");
return 0;
}
四晴楔、斐波那契博弈
有一堆n個(gè)物品，兩個(gè)人輪流取物品峭咒，先手最少取一個(gè)税弃，至多無(wú)上限，但不能把物品取完凑队，之后每次取的物品數(shù)量不能超過(guò)上一次取的物品數(shù)的兩倍且至少為一件则果，取走最后一件物品的人獲勝。
結(jié)論：先手勝當(dāng)且僅當(dāng)n不是斐波那契數(shù)（需要存儲(chǔ)斐波那契數(shù)）漩氨。
//HDU2516 此時(shí)涵蓋了所有int數(shù)（西壮？？）
#include <stdio.h>
int ans[55];
int main()
{
int n;
ans[0]=1;
ans[1]=1;
for(int i=2;i<55;i++)
{
ans[i]=ans[i-1]+ans[i-2];
}
while(scanf("%d",&n)==1 && n)
{
int flag=0;
for(int i=0;i<55;i++)
{
if(ans[i]==n)
{
flag=1;
break;
}
}
if(flag) printf("Second win\n");
else printf("First win\n");
}
}
