## （一）巴什博奕（Bash Game）： ~~~ 問題描述：有一堆n個物品，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取m 個。最后取光者得勝。 顯然，如果n=m+1，那么由于一次最多只能取m 個，所以，無論先取者拿走多少個, 后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發現了如何取勝的法則：如果n=（m+1）r+s，（r為任意自然數，s≤m),那么先取者要拿走s個物品，如果后取者拿走k（≤m)個，那么先取者再拿走m+1-k個，結果剩下(m+1)(r-1)個，以后保持這樣的取法，那么先取者肯定獲勝。總之，要保持給對手留下（m+1）的倍數，就能最后獲勝。 這個游戲還可以有一種變相的玩法：兩個人輪流報數，每次至少報一個，最多報十個，誰能報到100 者勝。 必勝局面：n%(m+1)!=0 必敗局面：n%(m+1)=0 例題： 取棋子游戲(I)分數: 16 時間限制：1 秒 內存限制：128 兆 特殊判題：?否 提交：26 解決：?20 題目描述 有N個棋子, 兩個人輪流從這堆物品中取, 規定每次至少取1個, 最多取3個.? 最后取光者得勝. 要求找出先行者是否有必勝策略，第一步應該取多上個棋子。 輸入格式 有多行數據，每行數據是一個正數N<10^7； 輸出 如果該行數據具有先行者必勝策略，則輸出第一步應取的棋子。若沒有必勝策略，輸出loss 樣例輸入 1 1000 樣例輸出 1 loss ~~~ #### 源碼 ~~~ #include<iostream> using namespace std; /** 若n%4==0，先行者必敗 否則先行者必贏n%4 */ int main(){ int n; while(cin>>n){ if(n%4==0){ cout<<"loss"<<endl; }else{ cout<<n%4<<endl; } } return 0; } ~~~ ## （二）威佐夫博奕（Wythoff Game） ~~~ 問題描述：有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規定每次至少取一個，多者不限，最后取光者得勝。 這種情況下是頗為復雜的。我們用（ak，bk）（ak?≤ bk?,k=0，1，2，...,n)表示兩堆物品的數量并稱其為局勢，如果甲面對(0,0)，那么甲已經輸了，這種局勢我們稱為奇異局勢。 前幾個奇異局勢是： （0，0） （1，2） （3，5） （4，7） （6，10） （8，13） （9，15） （11，18） （12，20） 可以看出,a0=b0=0,ak?是未在前面出現過的最小自然數,而bk= ak+k，奇異局勢有如下三條性質： 1、任何自然數都包含在一個且僅有一個奇異局勢中。 由于ak是未在前面出現過的最小自然數，所以有ak>ak-1，而bk= ak+k> ak-1+(k-1)=bk-1>ak-1。所以性質1成立。 2、任意操作都可將奇異局勢變為非奇異局勢。 事實上，若只改變奇異局勢（ak，bk）的某一個分量，那么另一個分量不可能在其他奇異局勢中，所以必然是非奇異局勢。如果使（ak，bk）的兩個分量同時減少，則由于其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢。 3、采用適當的方法，可以將非奇異局勢變為奇異局勢。 假設面對的局勢是(a,b)，分以下幾種情況討論： 1) 若b=a，則同時從兩堆中取走a 個物體，就變為了奇異局勢（0，0）； 2) 若a=ak?，b >bk，那么，從第二堆中取走b- bk個物體，即變為奇異局勢(ak,bk)； 3) 若a=ak?，b < bk,則同時從兩堆中拿走a-a(b-a)個物體,變為奇異局勢(a(b- a)?, b(b -a))； 4) 若a>ak?，b = ak?+ k,則從第一堆中拿走多余的數量a -ak即可； 5) 若a<ak?，b = ak?+ k,分兩種情況： ??? (1) a=aj?（j < k）時，從第二堆里面拿走b-bj即可，變為(aj?, bj)； ??? (2) a=bj?（j < k）時，從第二堆里面拿走b-aj即可，變為(bj?, aj)。 注意：a!=ak且b!=bk?的情況不存在，因為由a或b的值肯定能確定一種奇異局勢，即要么a=ak,要么b=bk。 從如上性質可知，兩個人如果都采用正確操作，那么面對非奇異局勢，先拿者必勝；反之，則后拿者取勝。 那么任給一個局勢(a，b）(a<b)，怎樣判斷它是不是奇異局勢呢？我們有如下公式： ak?=[k(1+√5)/2]，bk= ak?+ k （k=0，1，2，...,n 方括號表示取整函數） 奇妙的是其中出現了黃金分割數（1+√5）/2 = 1.618...,因此,由ak，bk?組成的矩形近似為黃金矩形，由于2/(1+√5)=(√5-1)/2， 可以先確定這是第幾個局勢。設該局勢是第j個局勢，那么j=[a(√5-1)/2]，此時這個奇異局勢有2種可能： 1)若a=[j(1+√5)/2]，那么a = aj，若同時有b= aj?+ j，則奇異局勢為(aj,bj)； 2)若a!=[j(1+√5)/2]，那么有可能是a = aj+1，此時如果又有b = aj+1+(j + 1)，則奇異局勢為(aj+1,bj+1)。 若以上兩種情況都不是，那么就不是奇異局勢。然后再按照上述法則進行，一定會遇到奇異局勢。 例題： 取石子游戲 Time Limit:?1000MS Memory Limit:?10000K Total Submissions:?36229 Accepted:?12266 Description 有兩堆石子，數量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最后把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的策略，問最后你是勝者還是敗者。 Input 輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。 Output 輸出對應也有若干行，每行包含一個數字1或0，如果最后你是勝者，則為1，反之，則為0。 Sample Input 2 1 8 4 4 7 Sample Output 0 1 0 ~~~ #### 源碼： ~~~ 取石子游戲 Time Limit:?1000MS Memory Limit:?10000K Total Submissions:?36229 Accepted:?12266 Description 有兩堆石子，數量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最后把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的策略，問最后你是勝者還是敗者。 Input 輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。 Output 輸出對應也有若干行，每行包含一個數字1或0，如果最后你是勝者，則為1，反之，則為0。 Sample Input 2 1 8 4 4 7 Sample Output 0 1 0 ~~~ ## （三）尼姆博奕（Nimm Game） #### 問題描述： 有三堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規定每次至少取一個，多者不限，最后取光者得勝。 這種情況最有意思，它與二進制有密切關系，我們用（a，b，c）表示某種局勢，首先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢是（0，n，n），只要與對手拿走一樣多的物品，最后都將導致（0，0，0）。仔細分析一下，（1，2，3）也是奇異局勢，無論對手如何拿，接下來都可以變為（0，n，n）的情形。 計算機算法里面有一種叫做按位模2 加，也叫做異或的運算，我們用符號（+）表示這 種運算。這種運算和一般加法不同的一點是1+1=0。先看（1，2，3）的按位模2 加的結果： 1 =二進制01 2 =二進制10 3 =二進制11 （+） ——————— 0 =二進制00 （注意不進位） 對于奇異局勢（0，n，n）也一樣，結果也是0。 任何奇異局勢（a，b，c）都有a（+）b（+）c =0。 如果我們面對的是一個非奇異局勢（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）即可。 例1：（14，21，39），14（+）21=27，3927=12，所以從39 中拿走12 個物體即可達到奇異局勢（14，21，27）。 例2：（55，81，121），55（+）81=102，121102=19，所以從121 中拿走19 個物品就形成了奇異局勢（55，81，102）。 例3：（29，45，58），29（+）45=48，5848=10，從58 中拿走10 個，變（29，45，48）。 例4：我們來實際進行一盤比賽看看： 甲:(7,8,9)>(1,8,9)奇異局勢 乙:(1,8,9)>(1,8,4) 甲:(1,8,4)>(1,5,4)奇異局勢 乙:(1,5,4)>(1,4,4) 甲:(1,4,4)>(0,4,4)奇異局勢 乙:(0,4,4)>(0,4,2) 甲:(0.4,2)>(0,2,2)奇異局勢 乙:(0,2,2)>(0,2,1) 甲:(0,2,1)>(0,1,1)奇異局勢 乙:(0,1,1)>(0,1,0) 甲:(0,1,0)>(0,0,0)奇異局勢 甲勝。 對于本次普及組“取石子游戲”來說， 19 010011 7 000111 5 000101 3 000011 010010 (18)10 50－18＝32 所以第1 次只能在第5 堆石子中取32 粒，使得取出32 粒后為奇異局勢，即異或運算結果為0。 #### 例題： ~~~ Georgia and Bob Time Limit:?1000MS Memory Limit:?10000K Total Submissions:?8134 Accepted:?2527 Description Georgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by 1, 2, 3, ..., and place N chessmen on different grids, as shown in the following figure for example:? Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game.? Georgia always plays first since "Lady first". Suppose that Georgia and Bob both do their best in the game, i.e., if one of them knows a way to win the game, he or she will be able to carry it out.? Given the initial positions of the n chessmen, can you predict who will finally win the game?? Input The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case contains two lines. The first line consists of one integer N (1 <= N <= 1000), indicating the number of chessmen. The second line contains N different integers P1, P2 ... Pn (1 <= Pi <= 10000), which are the initial positions of the n chessmen. Output For each test case, prints a single line, "Georgia will win", if Georgia will win the game; "Bob will win", if Bob will win the game; otherwise 'Not sure'. Sample Input 2 3 1 2 3 8 1 5 6 7 9 12 14 17 Sample Output Bob will win Georgia will win ~~~ #### 源碼： ~~~ #include<iostream> #include<algorithm> using namespace std; /** 當有兩顆棋子緊貼在一起時，先行者只能移動前一顆，后行者為了獲勝必然移動后一顆至緊貼前一顆， 這樣先行者永遠處于劣勢，于是我們可以把棋盤上的棋子看成一對一對組合，當每一對棋子都緊貼時， 先行者必敗。于是可以把每一對棋子中空格視為一堆石子，接下來就是取石子游戲問題了。接下來就是 判斷當前局勢是否處于奇異局勢，若處于奇異局勢則先行者敗，后行者敗. 若棋子數量為偶數，剛好可以把棋子分對 否則把最左端視為一顆棋子 注意：棋子的順序不一定有序，所以要先進行排序 */ int n,num[1000],i,sum,t; int main(){ cin>>t; while(t>0){ t--; cin>>n; //棋子不一定有序 for(i=0;i<n;i++){ cin>>num[i]; } sort(num,num+n); sum=0; if(n%2==0){ for(i=0;i<n;i=i+2){ sum=sum^(num[i+1]-num[i]-1); } }else{ sum=sum^(num[0]-1); for(i=1;i<n;i=i+2){ sum=sum^(num[i+1]-num[i]-1); } } if(sum==0){ cout<<"Bob will win"<<endl; }else{ cout<<"Georgia will win"<<endl; } } return 0; } ~~~