博弈論試題集

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

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

3、，輸出一行。如果先取的TT可以贏得游戲，則輸出“Win”，否則輸出“Lose”（引號不用輸出）樣例輸入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í)際情況而定：取石子（七）時間限制：1000ms | 內(nèi)存限制：65535KB難度：1描述Yougth和Hrdv玩一個游戲，拿出n個石子擺成一圈，Yougth和Hrdv分別從其中取石子，

4、誰先取完者勝，每次可以從中取一個或者相鄰兩個，Hrdv先取，輸出勝利著的名字。輸入輸入包括多組測試數(shù)據(jù)。每組測試數(shù)據(jù)一個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堆物品中取任意個，先取完者勝。 即將n堆物品的數(shù)量異或，得到的值如果為0，則先手?jǐn)?，反之先手勝?如果要求先手在勝的條件下，到奇異局勢的方法數(shù)，則判斷異或的值與每一堆原值異或后（結(jié)果應(yīng)該表示該堆沒有參加異或時的異或值）與原值比較大小，如果小于，則方法數(shù)加一。且對應(yīng)的方法后，該堆的數(shù)目應(yīng)變?yōu)楫惢虻闹蹬c每一堆原值異或的值。取石子（二）時間限制：3000ms | 內(nèi)存限制：65535KB難度：5描述小王喜歡與同事玩一些小游戲，今天他們選擇了玩取石子。游戲規(guī)則如下：共有N堆石子，已知每堆中石子的數(shù)量，并且規(guī)定好每堆石子最多可以取的石子數(shù)（最少取1顆）。

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

7、勝，輸出Lose表示小王必然會敗。樣例輸入211000 121 11 1樣例輸出LoseLose 提示注意下面一組測試數(shù)據(jù)21 12 2正確的結(jié)果應(yīng)該是Win因?yàn)樾⊥鯐葟牡诙咽又腥∫粋€石子，使?fàn)顟B(tài)變?yōu)? 11 2這種狀態(tài)下，無論對方怎么取，小王都能獲勝。最優(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;取石子（六）時間限制：1000ms | 內(nèi)存限制：65535KB難度：3描述最近TopCoder的PIAOYI和HRDV很無聊，于是就想了一個游戲，游戲是這樣的：有n堆石子,兩個人輪流從其中某一堆中任

9、意取走一定的石子,最后不能取的為輸家，注意：每次只能從一堆取任意個，可以取完這堆，但不能不取。假設(shè)PIAOYI先取石子，請你幫他判斷他是否能贏（假設(shè)他們?nèi)〉倪^程中不發(fā)生失誤,他們足夠聰明）。輸入第一行輸入n，代表有n組測試數(shù)據(jù)(n=10000)以下每組測試數(shù)據(jù)包含兩行：第一行：包含一個整數(shù)m，代表本組測試數(shù)據(jù)有m（m=1000）堆石子；：第二行：包含m個整數(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; 取石子（三）時間限制：1000ms | 內(nèi)存限制：1000KB難度：6描述小王喜歡與同事玩一些小游戲，今天他們選擇了玩取石子。游戲規(guī)則如下

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

12、動石子）4 1 1 2（移動到第一堆一個）3 2 1 2（移動到第二堆一個）3 1 1 3（移動到第四堆一個）5 1 0 2（全部移動到第一堆）3 3 0 2（全部移動到第二堆）3 1 0 4（全部移動到最后）輸入可能有多組測試數(shù)據(jù)(測試數(shù)據(jù)組數(shù)不超過1000)每組測試數(shù)據(jù)的第一行是一個整數(shù)，表示N(1=N=10)第二行是N個整數(shù)分別表示該堆石子中石子的數(shù)量。（每堆石子數(shù)目不超過100）當(dāng)輸入的N為0時，表示輸入結(jié)束輸出對于每組測試數(shù)據(jù)，輸出Win表示小王可以獲勝，輸出Lose表示小王必然會敗。樣例輸入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;分析:顯然,如果石頭是能夠兩兩配對,每一對的數(shù)目相同,比如:2,3,2,4可以配對成(2,2),(4,4) ,這樣的話就是先拿的輸,因?yàn)楹竽玫目梢允棺约耗猛旰笕匀荒軌蚴沟脙蓛膳鋵?且每一對的數(shù)目相同.剛剛開始的時候,如果已經(jīng)兩兩配對了,那么先拿的輸了,否則,選拿的可以把最大的動一下手腳,使剩下的兩兩配對,且每一對的數(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。任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨?事實(shí)上，若只改變奇異局勢（ak，bk）的某一個分量，那么另一個分量不可能在其他奇異局勢中，所以必然是非奇異局勢。如果使

16、（ak，bk）的兩個分量同時減少，則由于其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢。 3。采用適當(dāng)?shù)姆椒?，可以將非奇異局勢變?yōu)槠娈惥謩荨?假設(shè)面對的局勢是（a,b），若 b = a，則同時從兩堆中取走 a 個物體，就變?yōu)榱似娈惥謩荩?，0）；如果a = ak ，b bk，那么，取走b - bk個物體，即變?yōu)槠娈惥謩荩蝗绻?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ì)可知，兩個人如果都采用正確操作，那么面對非奇異局勢，先拿者必勝；反之，則后拿者取勝。 那么任給一個局勢（a，b），怎樣判斷它是不是奇異局勢呢？我們有如下公式： ak =k（1+5）/2，bk= ak + k （k=0，1，2，.,n 方括號表示取整函數(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、是，那么就不是奇異局勢。然后再按照上述法則進(jìn)行，一定會遇到奇異局勢。取石子 (四）時間限制：1000ms | 內(nèi)存限制：65535KB難度：4描述有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數(shù)量的石子。最后把石子全部取完者為勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。輸入輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000,000。輸出輸出對應(yīng)也有

19、若干行，每行包含一個數(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時間限制：1000ms | 內(nèi)存限制：65535KB難

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

21、（1,2）（3,5）.都是必敗態(tài)，我們今天要做的就是求前n個必敗態(tài)。不會？好吧！我再告訴你：假設(shè)第n個必敗態(tài)為（a，b）a為前n-1個必敗態(tài)中沒有出現(xiàn)的最小自然數(shù)，b=a+n。這下大家應(yīng)該明白了吧。好吧，我們的任務(wù)就的要前n個必敗態(tài)。規(guī)定第0個必敗態(tài)為（0,0）。輸入多組數(shù)據(jù)。輸入為一個數(shù)n（0=n=100000）。輸出按照要求求出前n個必敗態(tài)。輸出格式看下面樣例。樣例輸入31樣例輸出(0,0)(1,2)(3,5)(4,7)(0,0)(1,2)提示注意：每種情況中間沒有空格#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; 本人自己寫的代碼：#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; 取石子（八）時間限制：1000ms | 內(nèi)存限制：65535KB難度：3描述有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，

24、如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。如果你勝，你第1次怎樣取子?輸入輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000。a=b=0退出。輸出輸出也有若干行，如果最后你是敗者，則為0，反之，輸出1，并輸出使你勝的你第1次取石子后剩下的兩堆石子的數(shù)量x,y,x=y。如果在任意的一堆中取走石子能勝同時在兩堆中同時取走相同數(shù)量的石子也能勝，先輸出取走相同數(shù)量的石子的情況，假如取一堆的有多種情況，先輸出從石子多的一堆中取的情況，且要求輸出結(jié)果保證第二個值不小于第一個值。樣例輸入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) /奇異局勢 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情況，第一種奇異局勢 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（斐波那契博弈）斐波那契博弈模型，大致上是這樣的：有一堆個數(shù)為 n 的石子，游戲雙方輪流取石子，滿足：1. 先手不能在第一次把所有的石子取完；2

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

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

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

30、人取的石子數(shù)至少為1,至多為對手剛?cè)〉氖訑?shù)的兩倍。himdd事先想知道自己會不會贏，你能幫幫他嗎？（每次himdd先手）輸入有多組測試數(shù)據(jù)，每組有一個整數(shù)n(2=n264);輸出himdd會贏輸出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博奕:這個問題是尼姆博弈的拓展：游戲開始時有許多硬幣任意分布在樓梯上，共n階樓梯從地面由下向上編號為0到n。游戲者在每次操作時可以將樓梯j(1=j=n)上的任意多但至少一個硬幣移動到樓梯j-1上。游戲者輪流操作，將最后一枚硬幣移至地上（0號）的人獲勝。算法：將奇數(shù)樓層的狀態(tài)異或，和為0則先手必敗，否則先手必勝。證明略。例題：Poj1704這道題可以把兩個棋子中間間隔的空格子個數(shù)作為一堆石子，則原題轉(zhuǎn)化為每次可以把左邊的一堆石子移到相鄰的右邊的一堆中。也就是階梯尼姆博弈，注意對輸入數(shù)據(jù)先排序，然后倒著往前數(shù)（an-an-1-

32、1為第一個），奇數(shù)個數(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)算，這是施加于一個集合的運(yùn)算，表示最小的不屬于這個集合的非負(fù)整數(shù)。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。對于一個給定的有向無環(huán)圖，定義關(guān)于圖的每個頂點(diǎn)的Sprague-Grundy函數(shù)g如下：g(x)=mex g(y) | y是x的后繼 ,這里的g（x）即sgx例如：取石子問題，有1堆n個的石子，每次只能取1，3,4個石子，先取完石子者勝利，那么各個數(shù)的SG值為多少？sg0=0，f=1,3,4,x=1時，可以取走1-f1個石子，剩余0個，mexsg0=

34、0，故sg1=1;x=2時，可以取走2-f1個石子，剩余1個，mexsg1=1，故sg2=0；x=3時，可以取走3-f1,3個石子，剩余2,0個，mexsg2,sg0=0,0，故sg3=1;x=4時，可以取走4-f1,3,4個石子，剩余3,1,0個，mexsg3,sg1,sg0=1,1,0,故sg4=2;x=5時，可以取走5-f1,3,4個石子，剩余4,2,1個，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.計算從1-n范圍內(nèi)的SG值。f(存儲可以走的步數(shù)，f0表示可以有多少種走法)f需要從

35、小到大排序，這個模版f是從1開始的。hash數(shù)組大小跟f大小差不多1.可選步數(shù)為1m的連續(xù)整數(shù)，直接取模即可，SG(x) = x % (m+1);2.可選步數(shù)為任意步，SG(x) = x; 3. 可選步數(shù)為一系列不連續(xù)的數(shù)，用GetSG()計算/f：可以取走的石子個數(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)東西。上邊那個模版求hash時候并沒有考慮fj有效長度，在某些題目中可以通過，比如這個。因?yàn)樵谇箪巢瞧鯏?shù)列時候肯定多求了一個，而就是因?yàn)檫@個會在求hash時候打破循環(huán)。其實(shí)總的來說還是這個函數(shù)并不嚴(yán)密。因?yàn)橛械臅r候f是有有效長度的，如果多出了這個長度就會出現(xiàn)錯誤，如果你的初值都是0，那么就會取到0，如果是-1，那么就會取到-1，肯定不對。比如這個題。下面這兩個模版應(yīng)該就比較嚴(yán)密了，這個里邊的f是從零開始的。轉(zhuǎn)自：1、 sg打表/f：可以取走的石子個數(shù) /sg:0n

37、的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的有效長度 hashsgi-fj=1; for(int j=0; ; j+) /求mes中未出現(xiàn)的最小的非負(fù)整數(shù) if(hashj=0) sgi=j; break; 2、 Dfs/注意 S數(shù)組要按從小到大排序 SG函數(shù)要初始化為-1 對于每個集合只需初始化1遍 /n是集合s的大小

38、 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; 博弈問題之SG函數(shù)博弈小結(jié)2013-09-05 09:11:30 我來說兩句 作者：Bright-xl 收藏 我要投稿SG函數(shù)：給定一個有向無環(huán)圖和一個起始頂點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行

39、移動，無法移 動者判負(fù)。事實(shí)上，這個游戲可以認(rèn)為是所有Impartial Combinatorial Games的抽象模型。也就是說，任何一個ICG都可以通過把每個局面看成一個頂點(diǎn)，對每個局面和它的子局面連一條有向邊來抽象成這個“有向圖游戲”。下 面我們就在有向無環(huán)圖的頂點(diǎn)上定義Sprague-Garundy函數(shù)。首先定義mex(minimal excludant)運(yùn)算，這是施加于一個集合的運(yùn)算，表示最小的不屬于這個集合的非負(fù)整數(shù)。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。在我的理解中，sg函數(shù)就是一個對有向無環(huán)圖dfs的過程，在處理nim博弈時，多個石堆可以看成多個sg

40、函數(shù)值的異或。例題：POJ2311 Cutting Game典型的sg博弈，找后繼狀態(tài)。題意是給出一個n*m的紙片，每次剪成兩部分，誰先剪到1*1就勝利。這就是一個找后繼的題目，每次剪成的兩部分就是前一狀態(tài)的后繼，只要將兩個部分的sg值異或起來就是前一狀態(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 name