1、（一）巴什博奕（Bash Game）：只有一堆n個(gè)物品，兩個(gè)人輪流從這堆物品中取物，規(guī)定每次至少取一個(gè)，最多取m個(gè)。最后取光者得勝。 顯然，如果n=m+1，那么由于一次最多只能取m個(gè)，所以，無(wú)論先取者拿走多少個(gè)，后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：如果n=（m+1）r+s，（r為任意自然數(shù)，sm),那么先取者要拿走s個(gè)物品，如果后取者拿走k（m)個(gè)，那么先取者再拿走m+1-k個(gè)，結(jié)果剩下（m+1）（r-1）個(gè)，以后保持這樣的取法，那么先取者肯定獲勝?？傊?，要保持給對(duì)手留下（m+1）的倍數(shù)，就能最后獲勝。 這個(gè)游戲還可以有一種變相的玩法：兩個(gè)人輪流報(bào)數(shù)，每次至

2、少報(bào)一個(gè)，最多報(bào)十個(gè)，誰(shuí)能報(bào)到100者勝。取石子（一）時(shí)間限制：3000ms | 內(nèi)存限制：65535KB難度：2描述一天，TT在寢室閑著無(wú)聊，和同寢的人玩起了取石子游戲，而由于條件有限，他/她們是用旺仔小饅頭當(dāng)作石子。游戲的規(guī)則是這樣的。設(shè)有一堆石子，數(shù)量為N（1=N=1000000），兩個(gè)人輪番取出其中的若干個(gè)，每次最多取M個(gè)（1=M=1000000），最先把石子取完者勝利。我們知道，TT和他/她的室友都十分的聰明，那么如果是TT先取，他/她會(huì)取得游戲的勝利么？輸入第一行是一個(gè)正整數(shù)n表示有n組測(cè)試數(shù)據(jù)輸入有不到1000組數(shù)據(jù)，每組數(shù)據(jù)一行，有兩個(gè)數(shù)N和M,之間用空格分隔。輸出對(duì)于每組數(shù)據(jù)

3、，輸出一行。如果先取的TT可以贏得游戲，則輸出“Win”，否則輸出“Lose”（引號(hào)不用輸出）樣例輸入21000 11 100樣例輸出LoseWin最優(yōu)解：#includeusing namespace std;int main()int k;long m,n;cink;while(k-)cinnm;if(n%(m+1)=0)coutLoseendl;elsecoutWinendl; 巴什博弈變形：有兩種解，依實(shí)際情況而定：取石子（七）時(shí)間限制：1000ms | 內(nèi)存限制：65535KB難度：1描述Yougth和Hrdv玩一個(gè)游戲，拿出n個(gè)石子擺成一圈，Yougth和Hrdv分別從其中取石子，

4、誰(shuí)先取完者勝，每次可以從中取一個(gè)或者相鄰兩個(gè)，Hrdv先取，輸出勝利著的名字。輸入輸入包括多組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)一個(gè)n，數(shù)據(jù)保證int范圍內(nèi)。輸出輸出勝利者的名字。樣例輸入23樣例輸出HrdvYougth解一：#includeint n;int main() while(scanf(%d,&n) printf(n=3?Yougthn:Hrdvn); return 0;解二：3的倍數(shù)的是Yougth嬴#includeusing namespace std;int main()int a;while(cina)if(a%3!=0)coutHrdvendl;else coutYougthendl

5、;return 0; 尼姆博弈基本思想： 兩人從n堆物品中取任意個(gè)，先取完者勝。 即將n堆物品的數(shù)量異或，得到的值如果為0，則先手?jǐn)?，反之先手勝?如果要求先手在勝的條件下，到奇異局勢(shì)的方法數(shù)，則判斷異或的值與每一堆原值異或后（結(jié)果應(yīng)該表示該堆沒(méi)有參加異或時(shí)的異或值）與原值比較大小，如果小于，則方法數(shù)加一。且對(duì)應(yīng)的方法后，該堆的數(shù)目應(yīng)變?yōu)楫惢虻闹蹬c每一堆原值異或的值。取石子（二）時(shí)間限制：3000ms | 內(nèi)存限制：65535KB難度：5描述小王喜歡與同事玩一些小游戲，今天他們選擇了玩取石子。游戲規(guī)則如下：共有N堆石子，已知每堆中石子的數(shù)量，并且規(guī)定好每堆石子最多可以取的石子數(shù)（最少取1顆）。

6、兩個(gè)人輪流取子，每次只能選擇N堆石子中的一堆，取一定數(shù)量的石子(最少取一個(gè)），并且取的石子數(shù)量不能多于該堆石子規(guī)定好的最多取子數(shù)，等哪個(gè)人無(wú)法取子時(shí)就表示此人輸?shù)袅擞螒颉＜僭O(shè)每次都是小王先取石子，并且游戲雙方都絕對(duì)聰明，現(xiàn)在給你石子的堆數(shù)、每堆石子的數(shù)量和每堆石子規(guī)定的單次取子上限，請(qǐng)判斷出小王能否獲勝。輸入第一行是一個(gè)整數(shù)T表示測(cè)試數(shù)據(jù)的組數(shù)(T100)每組測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)N(1N100),表示共有N堆石子，隨后的N行每行表示一堆石子，這N行中每行有兩個(gè)數(shù)整數(shù)m,n表示該堆石子共有m個(gè)石子，該堆石子每次最多取n個(gè)。(0=m,n=231)輸出對(duì)于每組測(cè)試數(shù)據(jù)，輸出Win表示小王可以獲

7、勝，輸出Lose表示小王必然會(huì)敗。樣例輸入211000 121 11 1樣例輸出LoseLose 提示注意下面一組測(cè)試數(shù)據(jù)21 12 2正確的結(jié)果應(yīng)該是Win因?yàn)樾⊥鯐?huì)先從第二堆石子中取一個(gè)石子，使?fàn)顟B(tài)變?yōu)? 11 2這種狀態(tài)下，無(wú)論對(duì)方怎么取，小王都能獲勝。最優(yōu)解#includeint main()int T; scanf(%d,&T);while(T-)int m,n,g,sum=0;scanf(%d,&g);while(g-)scanf(%d%d,&m,&n);sum = m % (n + 1);puts(sum?Win:Lose); 一般解：#include using namespa

8、ce std;#include bool HandleEachCase();int main()int iCaseCount;ciniCaseCount;while(iCaseCount-)if(HandleEachCase()coutWinendl;elsecoutLoseiCount;for(int i= 0; imn;m%= (n+1);magic= m;return magic != 0;取石子（六）時(shí)間限制：1000ms | 內(nèi)存限制：65535KB難度：3描述最近TopCoder的PIAOYI和HRDV很無(wú)聊，于是就想了一個(gè)游戲，游戲是這樣的：有n堆石子,兩個(gè)人輪流從其中某一堆中任

9、意取走一定的石子,最后不能取的為輸家，注意：每次只能從一堆取任意個(gè)，可以取完這堆，但不能不取。假設(shè)PIAOYI先取石子，請(qǐng)你幫他判斷他是否能贏（假設(shè)他們?nèi)〉倪^(guò)程中不發(fā)生失誤,他們足夠聰明）。輸入第一行輸入n，代表有n組測(cè)試數(shù)據(jù)(n=10000)以下每組測(cè)試數(shù)據(jù)包含兩行：第一行：包含一個(gè)整數(shù)m，代表本組測(cè)試數(shù)據(jù)有m（m=1000）堆石子；：第二行：包含m個(gè)整數(shù)Ai(Ai=100)，分別代表第i堆石子的數(shù)量。輸出若PIAOYI贏輸出“PIAOYI”，否則輸出“HRDV”注意每組結(jié)果占一行。樣例輸入321 133 8 1125 10最優(yōu)解：#include#includeusing namespac

10、e std;void in(int &a)char ch;while(ch=getchar()9);for(a=0;ch=0&ch=9;ch=getchar() a=a*10+ch-0;int main()int T;in(T);while(T-)int n;in(n);int ans=0;for(int i=0;i!=n;+i)int b;in(b);ans=b;if(ans) puts(PIAOYI);else puts(HRDV);return 0; 取石子（三）時(shí)間限制：1000ms | 內(nèi)存限制：1000KB難度：6描述小王喜歡與同事玩一些小游戲，今天他們選擇了玩取石子。游戲規(guī)則如下

11、：共有N堆石子，已知每堆中石子的數(shù)量，兩個(gè)人輪流取子，每次只能選擇N堆石子中的一堆，取一定數(shù)量的石子（最少取一個(gè)），取過(guò)子之后，還可以將該堆石子中剩下的任意多個(gè)石子中隨意選取幾個(gè)放到其它的任意一堆或幾堆上。等哪個(gè)人無(wú)法取子時(shí)就表示此人輸?shù)袅擞螒?。注意，一堆石子沒(méi)有子之后，就不能再往此處放石子了。假設(shè)每次都是小王先取石子，并且游戲雙方都絕對(duì)聰明，現(xiàn)在給你石子的堆數(shù)、每堆石子的數(shù)量，請(qǐng)判斷出小王能否獲勝。例如：如果最開(kāi)始有4堆石子，石子個(gè)數(shù)分別為3 1 4 2，而小王想決定要先拿走第三堆石子中的兩個(gè)石子（石子堆狀態(tài)變?yōu)? 1 2 2），然后他可以使石子堆達(dá)到的狀態(tài)有以下幾種：3 1 2 2（不再移

12、動(dòng)石子）4 1 1 2（移動(dòng)到第一堆一個(gè)）3 2 1 2（移動(dòng)到第二堆一個(gè)）3 1 1 3（移動(dòng)到第四堆一個(gè)）5 1 0 2（全部移動(dòng)到第一堆）3 3 0 2（全部移動(dòng)到第二堆）3 1 0 4（全部移動(dòng)到最后）輸入可能有多組測(cè)試數(shù)據(jù)(測(cè)試數(shù)據(jù)組數(shù)不超過(guò)1000)每組測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)，表示N(1=N=10)第二行是N個(gè)整數(shù)分別表示該堆石子中石子的數(shù)量。（每堆石子數(shù)目不超過(guò)100）當(dāng)輸入的N為0時(shí)，表示輸入結(jié)束輸出對(duì)于每組測(cè)試數(shù)據(jù)，輸出Win表示小王可以獲勝，輸出Lose表示小王必然會(huì)敗。樣例輸入32 1 321 10樣例輸出WinLose一般解：#include #include #i

13、nclude using namespace std;bool HandleEachCase();int main()while(HandleEachCase()/empty whilebool HandleEachCase()int iCount;int count101;memset(count, 0, sizeof(count);ciniCount;if(!iCount)return false;int iStone;for(int i= 0; iiStone;+countiStone;int magic = 0;for(int i= 0; i 101 & !magic; +i)magi

14、c+= counti&1;if(magic)coutWinendl;elsecoutLoseendl;return true;分析:顯然,如果石頭是能夠兩兩配對(duì),每一對(duì)的數(shù)目相同,比如:2,3,2,4可以配對(duì)成(2,2),(4,4) ,這樣的話就是先拿的輸,因?yàn)楹竽玫目梢允棺约耗猛旰笕匀荒軌蚴沟脙蓛膳鋵?duì),且每一對(duì)的數(shù)目相同.剛剛開(kāi)始的時(shí)候,如果已經(jīng)兩兩配對(duì)了,那么先拿的輸了,否則,選拿的可以把最大的動(dòng)一下手腳,使剩下的兩兩配對(duì),且每一對(duì)的數(shù)目相同.最優(yōu)解：#include#includeusing namespace std;bool ok(int stone)for(int i=0;i!=1

15、10;i+)if(stonei&1) return true;return false;int main()int stone110;int n,m;while(cinn & n)memset(stone,0,sizeof(stone);while(n-)cinm;stonem+;cout(ok(stone)?Win:Lose) ak-1 ，而 bk= ak + k ak-1 + k-1 = bk-1 ak-1 。所以性質(zhì)1。成立。 2。任意操作都可將奇異局勢(shì)變?yōu)榉瞧娈惥謩?shì)。 事實(shí)上，若只改變奇異局勢(shì)（ak，bk）的某一個(gè)分量，那么另一個(gè)分量不可能在其他奇異局勢(shì)中，所以必然是非奇異局勢(shì)。如果使

16、（ak，bk）的兩個(gè)分量同時(shí)減少，則由于其差不變，且不可能是其他奇異局勢(shì)的差，因此也是非奇異局勢(shì)。 3。采用適當(dāng)?shù)姆椒?，可以將非奇異局?shì)變?yōu)槠娈惥謩?shì)。 假設(shè)面對(duì)的局勢(shì)是（a,b），若 b = a，則同時(shí)從兩堆中取走 a 個(gè)物體，就變?yōu)榱似娈惥謩?shì)（0，0）；如果a = ak ，b bk，那么，取走b - bk個(gè)物體，即變?yōu)槠娈惥謩?shì)；如果 a = ak ， b ak ，b= ak + k,則從第一堆中拿走多余的數(shù)量a - ak 即可；如果a ak ，b= ak + k,分兩種情況，第一種，a=aj （j k）,從第二堆里面拿走 b - bj 即可；第二種，a=bj （j k）,從第二堆里面拿走 b

17、 - aj 即可。 從如上性質(zhì)可知，兩個(gè)人如果都采用正確操作，那么面對(duì)非奇異局勢(shì)，先拿者必勝；反之，則后拿者取勝。 那么任給一個(gè)局勢(shì)（a，b），怎樣判斷它是不是奇異局勢(shì)呢？我們有如下公式： ak =k（1+5）/2，bk= ak + k （k=0，1，2，.,n 方括號(hào)表示取整函數(shù))奇妙的是其中出現(xiàn)了黃金分割數(shù)（1+5）/2 = 1。618.,因此,由ak，bk組成的矩形近似為黃金矩形，由于2/（1+5）=（5-1）/2，可以先求出j=a（5-1）/2，若a=j（1+5）/2，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+ j + 1，若都不

18、是，那么就不是奇異局勢(shì)。然后再按照上述法則進(jìn)行，一定會(huì)遇到奇異局勢(shì)。取石子 (四）時(shí)間限制：1000ms | 內(nèi)存限制：65535KB難度：4描述有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者。輸入輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個(gè)非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000,000。輸出輸出對(duì)應(yīng)也有

19、若干行，每行包含一個(gè)數(shù)字1或0，如果最后你是勝者，則為1，反之，則為0。樣例輸入2 18 44 7樣例輸出010最優(yōu)解：#include #include using namespace std; int main() int m,n;while(cinmn)if (m n)int temp;temp = m;m = n;n =temp;int k = n - m;int data = floor(k*(1.0+sqrt(5.0)/2.0);if (data = m)cout0endl;elsecout1endl; Wythoff Game時(shí)間限制：1000ms | 內(nèi)存限制：65535KB難

20、度：1描述最近ZKC同學(xué)在學(xué)博弈，學(xué)到了一個(gè)偉大的博弈問(wèn)題-威佐夫博弈。相信大家都學(xué)過(guò)了吧？沒(méi)學(xué)過(guò)？沒(méi)問(wèn)題。我將要為你講述一下這個(gè)偉大的博弈問(wèn)題。有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法：一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者。我們今天要做的是求前n個(gè)必?cái)B(tài)。什么是必?cái)B(tài)？比如我們把（a，b）稱為一種狀態(tài)，a，b分別為兩堆石子中所剩的數(shù)目。如果a=0，b=0，我們說(shuō)該種狀態(tài)為必?cái)B(tài)，因?yàn)槲也荒茉龠M(jìn)行游戲，即使是可以進(jìn)行，那也是必?cái)〉?，你知道，游戲的我們都是非常聰明的。?,0）

21、（1,2）（3,5）.都是必?cái)B(tài)，我們今天要做的就是求前n個(gè)必?cái)B(tài)。不會(huì)？好吧！我再告訴你：假設(shè)第n個(gè)必?cái)B(tài)為（a，b）a為前n-1個(gè)必?cái)B(tài)中沒(méi)有出現(xiàn)的最小自然數(shù)，b=a+n。這下大家應(yīng)該明白了吧。好吧，我們的任務(wù)就的要前n個(gè)必?cái)B(tài)。規(guī)定第0個(gè)必?cái)B(tài)為（0,0）。輸入多組數(shù)據(jù)。輸入為一個(gè)數(shù)n（0=n=100000）。輸出按照要求求出前n個(gè)必?cái)B(tài)。輸出格式看下面樣例。樣例輸入31樣例輸出(0,0)(1,2)(3,5)(4,7)(0,0)(1,2)提示注意：每種情況中間沒(méi)有空格#include#includetypedef struct Nodeint a,b;N;N res100001;void

22、 init()res0.a=0;res0.b=0;for(int i=1;i100001;i+)resi.a=(1+sqrt(5)*i/2;resi.b=resi.a+i;int main()int n;init();while(scanf(%d,&n)!=EOF)for(int i=0;i=n;i+)printf(%d,%d),resi.a,resi.b);printf(n);return 0; 本人自己寫(xiě)的代碼：#includeint main()int n,k,b,a100001,i,m=0;a0=0;while(scanf(%d,&n)if(n=m)for(k=0;k=n;k+)pri

23、ntf(%d,%d),ak,ak+k);elseprintf(%d,%d),a0,a0);for(k=1;k=0;i-)if(b=(ai+i)b+;else if(b(ai+i)break;ak=b;printf(%d,%d),ak,ak+k);m=n;printf(n);return 0; 取石子（八）時(shí)間限制：1000ms | 內(nèi)存限制：65535KB難度：3描述有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目，

24、如果輪到你先取，假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者。如果你勝，你第1次怎樣取子?輸入輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個(gè)非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000。a=b=0退出。輸出輸出也有若干行，如果最后你是敗者，則為0，反之，輸出1，并輸出使你勝的你第1次取石子后剩下的兩堆石子的數(shù)量x,y,x=y。如果在任意的一堆中取走石子能勝同時(shí)在兩堆中同時(shí)取走相同數(shù)量的石子也能勝，先輸出取走相同數(shù)量的石子的情況，假如取一堆的有多種情況，先輸出從石子多的一堆中取的情況，且要求輸出結(jié)果保證第二個(gè)值不小于第一個(gè)值。樣例輸入1 2 5 72 2

25、0 0樣例輸出013 53 54 710 01 2最優(yōu)解：#include#include #include #includeusing namespace std;int main() int a,b,temp,temp2,k,i; while(scanf(%d%d,&a,&b),a+b) if(ab) swap(a,b); k=b-a; temp=k*(1.0+sqrt(5.0)/2.0; if(a=temp) /奇異局勢(shì) printf(0n); else printf(1n); if(abs(temp-a)=abs(temp+k-b)&tempa) /兩堆 printf(%d %dn,t

26、emp,temp+k); if(a=0) /0 0情況，第一種奇異局勢(shì) printf(0 0n); for(i=1;ib) break; if(temp=a&temp2b) printf(%d %dn,a,temp2); else if(temp2=a&tempb) printf(%d %dn,temp,a); else if(temp2=b&tempa) printf(%d %dn,temp,b); return 0; Fibonaccis Game（斐波那契博弈）斐波那契博弈模型，大致上是這樣的：有一堆個(gè)數(shù)為 n 的石子，游戲雙方輪流取石子，滿足：1. 先手不能在第一次把所有的石子取完；2

27、. 之后每次可以取的石子數(shù)介于1到對(duì)手剛?cè)〉氖訑?shù)的2倍之間（包含1和對(duì)手剛?cè)〉氖訑?shù)的2倍）。約定取走最后一個(gè)石子的人為贏家，求必?cái)B(tài)。（轉(zhuǎn)）分析： n = 2時(shí)輸出second； n = 3時(shí)也是輸出second； n = 4時(shí)，第一個(gè)人想獲勝就必須先拿1個(gè)，這時(shí)剩余的石子數(shù)為3，此時(shí)無(wú)論第二個(gè)人如何取，第一個(gè)人都能贏，輸出first； n = 5時(shí)，first不可能獲勝，因?yàn)樗?時(shí)，second直接取掉剩下的3個(gè)就會(huì)獲勝，當(dāng)他取1時(shí)，這樣就變成了n為4的情形，所以輸出的是second； n = 6時(shí)，first只要去掉1個(gè)，就可以讓局勢(shì)變成n為5的情形，所以輸出的是first； n =

28、 7時(shí)，first取掉2個(gè)，局勢(shì)變成n為5的情形，故first贏，所以輸出的是first； n = 8時(shí)，當(dāng)first取1的時(shí)候，局勢(shì)變?yōu)?的情形，第二個(gè)人可贏，first取2的時(shí)候，局勢(shì)變成n為6得到情形，也是第二個(gè)人贏，取3的時(shí)候，second直接取掉剩下的5個(gè)，所以n = 8時(shí)，輸出的是second； 從上面的分析可以看出，n為2、3、5、8時(shí)，這些都是輸出second，即必?cái)↑c(diǎn)，仔細(xì)的人會(huì)發(fā)現(xiàn)這些滿足斐波那契數(shù)的規(guī)律，可以推斷13也是一個(gè)必?cái)↑c(diǎn)。借助“Zeckendorf定理”（齊肯多夫定理）：任何正整數(shù)可以表示為若干個(gè)不連續(xù)的Fibonacci數(shù)之和。n=12時(shí)，只要誰(shuí)能使石子剩下8

29、且此次取子沒(méi)超過(guò)3就能獲勝。因此可以把12看成8+4，把8看成一個(gè)站，等價(jià)與對(duì)4進(jìn)行氣喘操作。又如13，13=8+5，5本來(lái)就是必?cái)B(tài)，得出13也是必?cái)B(tài)。也就是說(shuō)，只要是斐波那契數(shù)，都是必?cái)↑c(diǎn)。所以我們可以利用斐波那契數(shù)的公式：fibi = fibi-1 + fibi-2，只要n是斐波那契數(shù)就輸出No。取石子(五）時(shí)間限制：1000ms | 內(nèi)存限制：65535KB難度：4描述himdd最近很想玩游戲，于是他找到acmj和他一起玩，游戲是這樣的：有一堆石子,兩個(gè)人輪流從其中取走一定的石子,取走最后所有石子的人為贏家,不過(guò)得遵循如下規(guī)則:1.第一次取不能取完,至少取1顆.2.從第二次開(kāi)始,每個(gè)

30、人取的石子數(shù)至少為1,至多為對(duì)手剛?cè)〉氖訑?shù)的兩倍。himdd事先想知道自己會(huì)不會(huì)贏，你能幫幫他嗎？（每次himdd先手）輸入有多組測(cè)試數(shù)據(jù)，每組有一個(gè)整數(shù)n(2=n264);輸出himdd會(huì)贏輸出Yes,否則輸出No;樣例輸入256樣例輸出NoNoYes一般解：#includeusing namespace std;int main() long long n,fib100; int i,flag; fib0=2; fib1=3; for(i=2;in&n) flag=0; for(i=0;i100;i+) if(fibi=n) coutNon; flag=1; break; if(flag

31、=0) coutYesn; return 0;Nim Staircase博奕:這個(gè)問(wèn)題是尼姆博弈的拓展：游戲開(kāi)始時(shí)有許多硬幣任意分布在樓梯上，共n階樓梯從地面由下向上編號(hào)為0到n。游戲者在每次操作時(shí)可以將樓梯j(1=j=n)上的任意多但至少一個(gè)硬幣移動(dòng)到樓梯j-1上。游戲者輪流操作，將最后一枚硬幣移至地上（0號(hào)）的人獲勝。算法：將奇數(shù)樓層的狀態(tài)異或，和為0則先手必?cái)?，否則先手必勝。證明略。例題：Poj1704這道題可以把兩個(gè)棋子中間間隔的空格子個(gè)數(shù)作為一堆石子，則原題轉(zhuǎn)化為每次可以把左邊的一堆石子移到相鄰的右邊的一堆中。也就是階梯尼姆博弈，注意對(duì)輸入數(shù)據(jù)先排序，然后倒著往前數(shù)（an-an-1-

32、1為第一個(gè)），奇數(shù)個(gè)數(shù)到的就做一下xor，其中最前面的看做a1-0-1，參考程序：vart,n,b,i,j:longint;a:array0.1000of longint;beginreadln(t);repeatdec(t);readln(n);for i:=1 to n do read(ai);qsort(1,n);/快排略j:=0;b:=0;for i:=n downto 1 dobegininc(j);if odd(j) then b:=b xor (ai-ai-1-1);end;if b=0 then writeln(Bob will win) else writeln(Georgi

33、a will win);until t=0;end.SG函數(shù)模板首先定義mex(minimal excludant)運(yùn)算，這是施加于一個(gè)集合的運(yùn)算，表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。對(duì)于一個(gè)給定的有向無(wú)環(huán)圖，定義關(guān)于圖的每個(gè)頂點(diǎn)的Sprague-Grundy函數(shù)g如下：g(x)=mex g(y) | y是x的后繼 ,這里的g（x）即sgx例如：取石子問(wèn)題，有1堆n個(gè)的石子，每次只能取1，3,4個(gè)石子，先取完石子者勝利，那么各個(gè)數(shù)的SG值為多少？sg0=0，f=1,3,4,x=1時(shí)，可以取走1-f1個(gè)石子，剩余0個(gè)，mexsg0=

34、0，故sg1=1;x=2時(shí)，可以取走2-f1個(gè)石子，剩余1個(gè)，mexsg1=1，故sg2=0；x=3時(shí)，可以取走3-f1,3個(gè)石子，剩余2,0個(gè)，mexsg2,sg0=0,0，故sg3=1;x=4時(shí)，可以取走4-f1,3,4個(gè)石子，剩余3,1,0個(gè)，mexsg3,sg1,sg0=1,1,0,故sg4=2;x=5時(shí)，可以取走5-f1,3,4個(gè)石子，剩余4,2,1個(gè)，mexsg4,sg2,sg1=2,0,1,故sg5=3；以此類推.x 0 1 2 3 4 5 6 7 8.sgx 0 1 0 1 2 3 2 0 1.計(jì)算從1-n范圍內(nèi)的SG值。f(存儲(chǔ)可以走的步數(shù)，f0表示可以有多少種走法)f需要從

35、小到大排序，這個(gè)模版f是從1開(kāi)始的。hash數(shù)組大小跟f大小差不多1.可選步數(shù)為1m的連續(xù)整數(shù)，直接取模即可，SG(x) = x % (m+1);2.可選步數(shù)為任意步，SG(x) = x; 3. 可選步數(shù)為一系列不連續(xù)的數(shù)，用GetSG()計(jì)算/f：可以取走的石子個(gè)數(shù)/sg:0n的SG函數(shù)值/hash:mexint fN,sgN,hashN; void getSG(int n) int i,j; memset(sg,0,sizeof(sg); for(i=1;i=n;i+) memset(hash,0,sizeof(hash); for(j=1;fj=i;j+) hashsgi-fj=1; f

36、or(j=0;j=n;j+) /求mes中未出現(xiàn)的最小的非負(fù)整數(shù) if(hashj=0) sgi=j; break; 下邊補(bǔ)充一點(diǎn)東西。上邊那個(gè)模版求hash時(shí)候并沒(méi)有考慮fj有效長(zhǎng)度，在某些題目中可以通過(guò)，比如這個(gè)。因?yàn)樵谇箪巢瞧鯏?shù)列時(shí)候肯定多求了一個(gè)，而就是因?yàn)檫@個(gè)會(huì)在求hash時(shí)候打破循環(huán)。其實(shí)總的來(lái)說(shuō)還是這個(gè)函數(shù)并不嚴(yán)密。因?yàn)橛械臅r(shí)候f是有有效長(zhǎng)度的，如果多出了這個(gè)長(zhǎng)度就會(huì)出現(xiàn)錯(cuò)誤，如果你的初值都是0，那么就會(huì)取到0，如果是-1，那么就會(huì)取到-1，肯定不對(duì)。比如這個(gè)題。下面這兩個(gè)模版應(yīng)該就比較嚴(yán)密了，這個(gè)里邊的f是從零開(kāi)始的。轉(zhuǎn)自：/primob

37、log/article/details/133760571、 sg打表/f：可以取走的石子個(gè)數(shù) /sg:0n的SG函數(shù)值 /hash:mex int fK,sgN,hashN; void getSG(int n) memset(sg,0,sizeof(sg); for(int i=1; i=n; i+) memset(hash,0,sizeof(hash); for(int j=0; fj=i & j k; j+) /k是f的有效長(zhǎng)度 hashsgi-fj=1; for(int j=0; ; j+) /求mes中未出現(xiàn)的最小的非負(fù)整數(shù) if(hashj=0) sgi=j; break; 2、

38、Dfs/注意 S數(shù)組要按從小到大排序 SG函數(shù)要初始化為-1 對(duì)于每個(gè)集合只需初始化1遍 /n是集合s的大小 Si是定義的特殊取法規(guī)則的數(shù)組 int sN,sgN,n; int getSG(int x) if(sgx!=-1) return sgx; bool visM; memset(vis,0,sizeof(vis); for(int i=0; i=si) visgetSG(x-si)=1; for(i=0; i+) if(!visi) sgx=i; break; return sgx; 博弈問(wèn)題之SG函數(shù)博弈小結(jié)2013-09-05 09:11:30 我來(lái)說(shuō)兩句 作者：Bright-xl

39、 收藏 我要投稿SG函數(shù)：給定一個(gè)有向無(wú)環(huán)圖和一個(gè)起始頂點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動(dòng)，無(wú)法移 動(dòng)者判負(fù)。事實(shí)上，這個(gè)游戲可以認(rèn)為是所有Impartial Combinatorial Games的抽象模型。也就是說(shuō)，任何一個(gè)ICG都可以通過(guò)把每個(gè)局面看成一個(gè)頂點(diǎn)，對(duì)每個(gè)局面和它的子局面連一條有向邊來(lái)抽象成這個(gè)“有向圖游戲”。下 面我們就在有向無(wú)環(huán)圖的頂點(diǎn)上定義Sprague-Garundy函數(shù)。首先定義mex(minimal excludant)運(yùn)算，這是施加于一個(gè)集合的運(yùn)算，表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)。例如mex0,1,2,4=3、mex2,3,5=0、me

40、x=0。在我的理解中，sg函數(shù)就是一個(gè)對(duì)有向無(wú)環(huán)圖dfs的過(guò)程，在處理nim博弈時(shí)，多個(gè)石堆可以看成多個(gè)sg函數(shù)值的異或。例題：POJ2311 Cutting Game典型的sg博弈，找后繼狀態(tài)。題意是給出一個(gè)n*m的紙片，每次剪成兩部分，誰(shuí)先剪到1*1就勝利。這就是一個(gè)找后繼的題目，每次剪成的兩部分就是前一狀態(tài)的后繼，只要將兩個(gè)部分的sg值異或起來(lái)就是前一狀態(tài)的sg值。cpp #include #include #include #include #include #include #include #include #include #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;ib;+i) #define N 1000000007 using