假設(shè)兩位玩家均采用?最佳?決策。如果 Alice 獲勝，返回?true?；如果 Bob 獲勝，返回?false?。

示例 1：

輸入：stones = [2,1]
輸出：true
解釋：游戲進(jìn)行如下：
- 回合 1：Alice 可以移除任意一個(gè)石子。
- 回合 2：Bob 移除剩下的石子。 
已移除的石子的值總和為 1 + 2 = 3 且可以被 3 整除。因此，Bob 輸，Alice 獲勝。

示例 2：

輸入：stones = [2]
輸出：false
解釋：Alice 會(huì)移除唯一一個(gè)石子，已移除石子的值總和為 2 。 
由于所有石子都已移除，且值總和無法被 3 整除，Bob 獲勝。

示例 3：

輸入：stones = [5,1,2,4,3]
輸出：false
解釋：Bob 總會(huì)獲勝。其中一種可能的游戲進(jìn)行方式如下：
- 回合 1：Alice 可以移除值為 1 的第 2 個(gè)石子。已移除石子值總和為 1 。
- 回合 2：Bob 可以移除值為 3 的第 5 個(gè)石子。已移除石子值總和為 = 1 + 3 = 4 。
- 回合 3：Alices 可以移除值為 4 的第 4 個(gè)石子。已移除石子值總和為 = 1 + 3 + 4 = 8 。
- 回合 4：Bob 可以移除值為 2 的第 3 個(gè)石子。已移除石子值總和為 = 1 + 3 + 4 + 2 = 10.
- 回合 5：Alice 可以移除值為 5 的第 1 個(gè)石子。已移除石子值總和為 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 輸?shù)粲螒?，因?yàn)橐岩瞥又悼偤停?5）可以被 3 整除，Bob 獲勝。

提示：

• 1 <= stones.length <= 105
• 1 <= stones[i] <= 104

思路：

考慮先手贏的條件，問題轉(zhuǎn)化成：
有n0個(gè)0, n1個(gè)1，n2個(gè)2，先手可以選擇1121212...的序列或者2212121...的序列，假設(shè)選出的最長長度分別是x1,x2，
那么先手勝利的條件是，x1或者x2滿足，x加上n0是奇數(shù)，且0<x<n1+n2

代碼：

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int n0=0,n1=0,n2=0;
        for(auto x:stones){
            if(x%3==0)n0++;
            if(x%3==1)n1++;
            if(x%3==2)n2++;
        }
        if(n1>n2)n1^=n2^=n1^=n2;
        int x1=f1(n1,n2);
        int x2=f2(n1,n2);
        return (x1>0&&x1<n1+n2&&(x1+n0)%2)||(x2>0&&x2<n1+n2&&(x2+n0)%2);
    }
    int f1(int n1,int n2){
        if(n1==0 && n2==0)return 0;
        if(n1==0 || n2==0)return min(n1+n2,2);
        return n1*2-1;        
    }
    int f2(int n1,int n2){
        if(n1==0 && n2==0)return 0;
        if(n1==0 || n2==0)return min(n1+n2,2);
        if(n1>=n2-1)return n2*2-1;
        return n1*2+2;
    }
};

可以重構(gòu)成：

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int n0=0,n1=0,n2=0;
        for(auto x:stones){
            if(x%3==0)n0++;
            if(x%3==1)n1++;
            if(x%3==2)n2++;
        }
        if(n1==0 && n2==0)return false;
        if(n1==0 || n2==0)return n1+n2>2 && n0%2;
        if(n1>n2)n1^=n2^=n1^=n2;
        int x = n1>=n2-1 ? n2*2-1 : n1*2+2;
        return (1+n0)%2 || (x<n1+n2 && (x+n0)%2);
    }
};

進(jìn)一步重構(gòu)成：

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int n0=0,n1=0,n2=0;
        for(auto x:stones){
            if(x%3==0)n0++;
            if(x%3==1)n1++;
            if(x%3==2)n2++;
        }
        if(n1==0 || n2==0)return n1+n2>2 && n0%2;
        return (1+n0)%2 || n1+2<n2 || n2+2<n1;
    }
};

力扣 1927. 求和游戲（貪心）

Alice 和 Bob 玩一個(gè)游戲，兩人輪流行動(dòng)，Alice 先手?。

給你一個(gè)?偶數(shù)長度?的字符串?num?，每一個(gè)字符為數(shù)字字符或者?'?'?。每一次操作中，如果?num?中至少有一個(gè)?'?'?，那么玩家可以執(zhí)行以下操作：

1. 選擇一個(gè)下標(biāo)?i?滿足?num[i] == '?'?。
2. 將?num[i]?用?'0'?到?'9'?之間的一個(gè)數(shù)字字符替代。

當(dāng)?num?中沒有?'?'?時(shí)，游戲結(jié)束。

Bob 獲勝的條件是?num?中前一半數(shù)字的和?等于?后一半數(shù)字的和。Alice 獲勝的條件是前一半的和與后一半的和?不相等?。

• 比方說，游戲結(jié)束時(shí)?num = "243801"?，那么?Bob 獲勝，因?yàn)?2+4+3 = 8+0+1?。如果游戲結(jié)束時(shí)?num = "243803"?，那么 Alice 獲勝，因?yàn)?2+4+3 != 8+0+3?。

在 Alice 和 Bob 都采取?最優(yōu)?策略的前提下，如果 Alice 獲勝，請返回?true?，如果 Bob 獲勝，請返回?false?。

示例 1：

輸入：num = "5023"
輸出：false
解釋：num 中沒有 '?' ，沒法進(jìn)行任何操作。
前一半的和等于后一半的和：5 + 0 = 2 + 3 。

示例 2：

輸入：num = "25??"
輸出：true
解釋：Alice 可以將兩個(gè) '?' 中的一個(gè)替換為 '9' ，Bob 無論如何都無法使前一半的和等于后一半的和。

示例 3：

輸入：num = "?3295???"
輸出：false
解釋：Bob 總是能贏。一種可能的結(jié)果是：
- Alice 將第一個(gè) '?' 用 '9' 替換。num = "93295???" 。
- Bob 將后面一半中的一個(gè) '?' 替換為 '9' 。num = "932959??" 。
- Alice 將后面一半中的一個(gè) '?' 替換為 '2' 。num = "9329592?" 。
- Bob 將后面一半中最后一個(gè) '?' 替換為 '7' 。num = "93295927" 。
Bob 獲勝，因?yàn)?9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。

提示：

• 2 <= num.length <= 105
• num.length?是?偶數(shù)?。
• num?只包含數(shù)字字符和?'?'?。

class Solution {
public:
    bool sumGame(string num) {
        int x=0,s=0;
        for(int i=0;i<num.length()/2;i++){
            if(num[i]=='?')x++;
            else s+=num[i]-'0';
        }
        for(int i=num.length()/2;i<num.length();i++){
            if(num[i]=='?')x--;
            else s-=num[i]-'0';
        }
        return x%2 || (x/2*9+s);
    }
};

二，有向圖游戲

1，狹義有向圖游戲

在一張有向無環(huán)圖中，某一個(gè)節(jié)點(diǎn)上有一顆棋子，兩名玩家輪流將棋子沿有向邊移動(dòng)，最先不能移動(dòng)的一方輸。

這里的綠色節(jié)點(diǎn)是敗態(tài)，粉紅色是勝態(tài)，整個(gè)圖可以分為4層：

自底向上推導(dǎo)：

底層是最右邊的最0層，是敗態(tài)。

有一條邊指向任意敗態(tài)節(jié)點(diǎn)的就是勝態(tài)節(jié)點(diǎn)，所以第1層的2個(gè)節(jié)點(diǎn)是勝態(tài)。

所有邊都指向勝態(tài)節(jié)點(diǎn)的節(jié)點(diǎn)的就是敗態(tài)節(jié)點(diǎn)，所以第2層的1個(gè)節(jié)點(diǎn)是敗態(tài)。

第3層的1個(gè)節(jié)點(diǎn)是勝態(tài)。

這個(gè)分層推導(dǎo)的例子，可以推廣到所有的有向無環(huán)圖，最終每個(gè)節(jié)點(diǎn)都有一個(gè)非負(fù)層數(shù)，層數(shù)的奇偶性直接決定是勝態(tài)還是敗態(tài)。

2，狹義有向圖游戲的SG數(shù)

SG數(shù)的定義：

其中x->y表示存在x指向y的一條邊，mex（S）表示不在集合S中的最小自然數(shù)。

SG為0則是敗態(tài)，SG>0則是勝態(tài)。

無論是分層的方式，還是SG數(shù)，都可以通過遍歷來求出所有狀態(tài)是勝態(tài)還是負(fù)態(tài)。

3，廣義有向圖游戲

（1）推廣1

在狹義有向圖游戲的基礎(chǔ)上進(jìn)行推廣，對于任意有向有環(huán)圖，定義其中一些節(jié)點(diǎn)為勝或者負(fù)，兩名玩家輪流將棋子沿有向邊移動(dòng)。

要想保證最終一定會(huì)走到定義了勝負(fù)的節(jié)點(diǎn)，需要保證出度為0的點(diǎn)一定定義了勝負(fù)，出度不為0的每一個(gè)點(diǎn)都可以定義或不定義勝負(fù)。

這一類游戲全部可以轉(zhuǎn)化成狹義有向圖游戲，具體方法是2步：

第1步，把所有定義了勝負(fù)的節(jié)點(diǎn)，出度置為0，即從他們出發(fā)的有向邊全部刪除。

第2步，新增1個(gè)定義為負(fù)的節(jié)點(diǎn)X，把所有定義成勝的節(jié)點(diǎn)，出度置為1，即從他們連一條有向邊到X。

這樣就轉(zhuǎn)化成了狹義有向圖游戲。

（2）推廣2

因?yàn)橛邢驁D本身就是個(gè)建模工具，能表達(dá)豐富的信息，所以很多博弈都可以轉(zhuǎn)化成有向圖游戲（轉(zhuǎn)化成狹義有向圖游戲，或有向圖游戲推廣1），我們把這些游戲都稱為廣義有向圖游戲。

一般說有向圖游戲，指的都是廣義有向圖游戲，屬于公開游戲的一種。

公開游戲可能不是廣義有向圖游戲，因?yàn)楣_游戲可以不滿足每步的走法數(shù)有限。

4，廣義有向圖游戲分類

廣義有向圖游戲分為三類：

（1）狹義有向圖游戲，屬于公平游戲

（2）其他公平游戲

（3）非公平游戲的有向圖游戲。

也就是說，（1）（2）合起來是公平游戲，而（2）（3）合起來是非狹義有向圖游戲的廣義有向圖游戲。

對于（2）（3），要么轉(zhuǎn)化成（1）求解，要么由于有特定的規(guī)則，導(dǎo)致圖不是任意圖，而是有規(guī)律的圖，這樣我們就求解時(shí)就有了簡單的退化的方法，而不用真的沿著圖去遍歷。

5，非公平游戲的有向圖游戲

力扣?2038. 如果相鄰兩個(gè)顏色均相同則刪除當(dāng)前顏色

總共有?n?個(gè)顏色片段排成一列，每個(gè)顏色片段要么是?'A'?要么是?'B'?。給你一個(gè)長度為?n?的字符串?colors?，其中?colors[i]?表示第?i?個(gè)顏色片段的顏色。

Alice 和 Bob 在玩一個(gè)游戲，他們?輪流?從這個(gè)字符串中刪除顏色。Alice?先手?。

• 如果一個(gè)顏色片段為?'A'?且?相鄰兩個(gè)顏色?都是顏色?'A'?，那么 Alice 可以刪除該顏色片段。Alice?不可以?刪除任何顏色?'B'?片段。
• 如果一個(gè)顏色片段為?'B'?且?相鄰兩個(gè)顏色?都是顏色?'B'?，那么 Bob 可以刪除該顏色片段。Bob?不可以?刪除任何顏色?'A'?片段。
• Alice 和 Bob?不能?從字符串兩端刪除顏色片段。
• 如果其中一人無法繼續(xù)操作，則該玩家?輸?掉游戲且另一玩家?獲勝?。

假設(shè) Alice 和 Bob 都采用最優(yōu)策略，如果 Alice 獲勝，請返回?true，否則 Bob 獲勝，返回?false。

示例 1：

輸入：colors = "AAABABB"
輸出：true
解釋：
AAABABB -> AABABB
Alice 先操作。
她刪除從左數(shù)第二個(gè) 'A' ，這也是唯一一個(gè)相鄰顏色片段都是 'A' 的 'A' 。

現(xiàn)在輪到 Bob 操作。
Bob 無法執(zhí)行任何操作，因?yàn)闆]有相鄰位置都是 'B' 的顏色片段 'B' 。
因此，Alice 獲勝，返回 true 。

示例 2：

輸入：colors = "AA"
輸出：false
解釋：
Alice 先操作。
只有 2 個(gè) 'A' 且它們都在字符串的兩端，所以她無法執(zhí)行任何操作。
因此，Bob 獲勝，返回 false 。

示例 3：

輸入：colors = "ABBBBBBBAAA"
輸出：false
解釋：
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的選擇是刪除從右數(shù)起第二個(gè) 'A' 。

ABBBBBBBAA -> ABBBBBBAA
接下來輪到 Bob 操作。
他有許多選擇，他可以選擇任何一個(gè) 'B' 刪除。

然后輪到 Alice 操作，她無法刪除任何片段。
所以 Bob 獲勝，返回 false 。

提示：

• 1 <=?colors.length <= 105
• colors?只包含字母?'A'?和?'B'

class Solution {
public:
    bool winnerOfGame(string colors) {
        vector<int>v(2);
        int n=1;
        for(int i=1;i<=colors.length();i++){
            if(i<colors.length() && colors[i]==colors[i-1])n++;
            else{
                v[colors[i-1]-'A']+=max(n-2,0);
                n=1;
            }
        }
        return v[0]>v[1];
    }
};

三，公平游戲

1，公平游戲

若一個(gè)游戲滿足以下條件：
　　1. 雙人、回合制；
　　2. 信息完全公開（perfect information）；
　　3. 無隨機(jī)因素（deterministic）；
　　4. 必然在有限步內(nèi)結(jié)束，且每步的走法數(shù)有限（finite）；
　　5. 沒有平局；
　　6. 雙方可采取的行動(dòng)及勝利目標(biāo)都相同（impartial）；
　　7. 這個(gè)勝利目標(biāo)是自己親手達(dá)成終局狀態(tài)，或者說走最后一步者為勝（normal play）；

則稱之為公平游戲。

公平游戲都屬于有向圖游戲。

雖然有向圖游戲中的勝負(fù)很明確，但是如果圖非常大，則遍歷需要的時(shí)間很長。

2，Bash Game

有一堆石子共有N個(gè)。A B兩個(gè)人輪流拿，A先拿。每次最少拿1顆，最多拿K顆。

正向：誰拿完就判勝，規(guī)律是N是K+1的倍數(shù)時(shí)先手負(fù)，否則先手勝

反向：誰拿完就判負(fù)，規(guī)律是N-1是K+1的倍數(shù)時(shí)先手負(fù)，否則先手勝

力扣 292. Nim 游戲（正向Bash）

題目：

你和你的朋友，兩個(gè)人一起玩?Nim 游戲：桌子上有一堆石頭，每次你們輪流拿掉?1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。

你們是聰明人，每一步都是最優(yōu)解。 編寫一個(gè)函數(shù)，來判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。

示例:

輸入: 4
輸出: false?
解釋: 如果堆中有 4 塊石頭，那么你永遠(yuǎn)不會(huì)贏得比賽；
?? ? 因?yàn)闊o論你拿走 1 塊、2 塊 還是 3 塊石頭，最后一塊石頭總是會(huì)被你的朋友拿走。

這分明是Bash Game，不是Nim Game

代碼：

class Solution {
public:
    bool canWinNim(int n) {
        return n%4;
    }
};

51Nod 1066 Bash游戲（正向Bash）

有一堆石子共有N個(gè)。A B兩個(gè)人輪流拿，A先拿。每次最少拿1顆，最多拿K顆，拿到最后1顆石子的人獲勝。假設(shè)A B都非常聰明，拿石子的過程中不會(huì)出現(xiàn)失誤。給出N和K，問最后誰能贏得比賽。

例如N = 3，K = 2。無論A如何拿，B都可以拿到最后1顆石子。

Input

第1行：一個(gè)數(shù)T，表示后面用作輸入測試的數(shù)的數(shù)量。（1 <= T <= 10000) 第2 - T + 1行：每行2個(gè)數(shù)N，K。中間用空格分隔。（1 <= N,K <= 10^9)

Output

共T行，如果A獲勝輸出A，如果B獲勝輸出B。

Sample Input

4
3 2
4 2
7 3
8 3

Sample Output

B
A
A
B

#include<iostream>
using namespace std;

int main()
{
    int a,b;
    cin >> a;
    while (cin >> a >> b) {
        if (a % ++b)cout << "A\n";
        else cout << "B\n";
    }
    return 0;
}

51Nod 1067 Bash游戲 V2（正向拓展Bash）

有一堆石子共有N個(gè)。A B兩個(gè)人輪流拿，A先拿。每次只能拿1，3，4顆，拿到最后1顆石子的人獲勝。假設(shè)A B都非常聰明，拿石子的過程中不會(huì)出現(xiàn)失誤。給出N，問最后誰能贏得比賽。

例如N = 2。A只能拿1顆，所以B可以拿到最后1顆石子。

Input

第1行：一個(gè)數(shù)T，表示后面用作輸入測試的數(shù)的數(shù)量。（1 <= T <= 10000) 第2 - T + 1行：每行1個(gè)數(shù)N。(1 <= N <= 10^9)

Output

共T行，如果A獲勝輸出A，如果B獲勝輸出B。

Sample Input

3
2
3
4

Sample Output

B
A
A

思路：以7為周期

#include<iostream>
using namespace std;

int main()
{
    int a;
    cin >> a;
    while (cin >> a) {
        if (a % 7 == 0 || a % 7 == 2)cout << "B\n";
        else cout << "A\n";
    }
    return 0;
}

51Nod 1068 Bash游戲 V3（正向拓展Bash）

有一堆石子共有N個(gè)。A B兩個(gè)人輪流拿，A先拿。每次拿的數(shù)量只能是2的正整數(shù)次冪，比如(1,2,4,8,16....)，拿到最后1顆石子的人獲勝。假設(shè)A B都非常聰明，拿石子的過程中不會(huì)出現(xiàn)失誤。給出N，問最后誰能贏得比賽。

例如N = 3。A只能拿1顆或2顆，所以B可以拿到最后1顆石子。（輸入的N可能為大數(shù)）

Input

第1行：一個(gè)數(shù)T，表示后面用作輸入測試的數(shù)的數(shù)量。（1 <= T <= 1000) 第2 - T + 1行：每行1個(gè)數(shù)N。(1 <= N <= 10^1000)

Output

共T行，如果A獲勝輸出A，如果B獲勝輸出B。

Sample Input

3
2
3
4

Sample Output

A
B
A

思路：2的冪其實(shí)就是mod 3等于1或2，所以只需要看總數(shù)是不是3的倍數(shù)

#include<iostream>
using namespace std;

int main()
{
    int a;
    cin >> a;
    string s;
    while (a--) {
        cin >> s;
        int k = 0;
        for (int i = 0; i < s.length(); i++)k += s[i];
        if (k % 3 == 0)cout << "B\n";
        else cout << "A\n";
    }
    return 0;
}

3，斐波那契博弈

CSU 2048?Bash游戲升級版

題目：

Description
軟件學(xué)院的新生課上，老師講述過這樣一個(gè)游戲。有n個(gè)石子，2個(gè)人輪流取石子，每輪取走1…m個(gè)石子，問如何獲勝。這個(gè)游戲又稱作巴什博弈（Bash Game）。

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

這個(gè)游戲還可以有一種變相的玩法：兩個(gè)人輪流報(bào)數(shù)，每次至少報(bào)一個(gè)，最多報(bào)十個(gè)，誰能報(bào)到100者勝。

現(xiàn)在，我們要該變一下游戲規(guī)則，相對于標(biāo)準(zhǔn)的巴什博奕，我們規(guī)定最后取光者輸，那么又會(huì)如何呢？
顯然，（n-1）%（m+1）==0則后手勝利
先手會(huì)重新決定策略，所以不是簡單的相反行的
例如n=15，m=3
后手?先手?剩余
0??2??13
1??3??9
2??2??5
3??1??1
1??0??0
先手勝利，輸?shù)娜俗詈蟊囟ㄖ蛔プ咭粋€(gè)，如果最后剩下的個(gè)數(shù)大于1個(gè)，則必定會(huì)留一個(gè)給對手。

現(xiàn)在，我們再次改變一下游戲規(guī)則。相對于標(biāo)準(zhǔn)的巴什博奕，我們規(guī)定先取者第1次可以取任意多個(gè)，但不能全部取完，以后每次取的物品數(shù)不能超過上次取的數(shù)量的2倍。取完者勝。 現(xiàn)在想請問已經(jīng)做過數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一的你，兩人開始博弈后，誰有必勝的把握呢？
先取者負(fù)輸出"Second win". 先取者勝輸出"First win".

Input
輸入有多組.每組第1行是2?<?=n?<?231.
n=0退出.

Output
先取者負(fù)輸出"Second win". 先取者勝輸出"First win".
參看Sample Output.

Sample Input
2
3
10000
0
Sample Output
Second win
Second win
First win

思路：斐波那契數(shù)列

代碼：

#include<iostream>
#include<stdio.h>
using namespace std;
 
int main()
{
	int f[44]={2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,
	6765,10946,17711,28657,46368,75025,121393,196418,317811,
	514229,832040,1346269,2178309,3524578,5702887,9227465,
	14930352,24157817,39088169,63245986,102334155,165580141,
	267914296,433494437,701408733,1134903170,1836311903};
	int n;
	while(scanf("%d",&n))
	{
		if(n==0)return 0;
		bool flag=false;
		for(int i=0;i<44;i++)if(f[i]==n)flag=true;
		if(flag)printf("Second win\n");
		else printf("First win\n");
	}
	return 0;
}

HDU?2516 取石子游戲

題目：

Description

1堆石子有n個(gè),兩人輪流取.先取者第1次可以取任意多個(gè)，但不能全部取完.以后每次取的石子數(shù)不能超過上次取子數(shù)的2倍。取完者勝.先取者負(fù)輸出"Second win".先取者勝輸出"First win".?
Input

輸入有多組.每組第1行是2<=n<2^31. n=0退出.?
Output

先取者負(fù)輸出"Second win". 先取者勝輸出"First win".?
參看Sample Output.?
Sample Input

2
13
10000
0
Sample Output

Second win
Second win
First win

這個(gè)博弈俗稱斐波那契博弈，簡稱FIB博弈。

原理到處都有解釋，我就不扯了，不過里面用到的核心定理，我有解釋：斐波那契數(shù)列的齊肯多夫定理

代碼：

#include<iostream>
#include<stdio.h>
using namespace std;

int list[46];

int main()
{
	list[1] = 1;
	list[2] = 2;
	for (int i = 3; i <= 45; i++)list[i] = list[i - 1] + list[i - 2];
	int n;
	while (cin >> n)
	{
		if (n == 0)break;
		int i = 2;
		for (; i <= 45; i++)if (list[i] == n)
		{
			cout << "Second win\n";
			break;
		}
		if (i > 45)cout << "First win\n";
	}
	return 0;
}

4，威佐夫博奕

POJ 1067、OpenJ_Bailian - 1067、HDU 1527 取石子游戲

關(guān)鍵詞：

取石子游戲、威佐夫博奕、beatty貝蒂定理、勝態(tài)、負(fù)態(tài)、狀態(tài)轉(zhuǎn)移、覆蓋（分劃）、高斯函數(shù)、第二數(shù)學(xué)歸納法、黃金分割比例

題目：

Description

有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。
Input

輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個(gè)非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000,000。
Output

輸出對應(yīng)也有若干行，每行包含一個(gè)數(shù)字1或0，如果最后你是勝者，則為1，反之，則為0。
Sample Input

2 1
8 4
4 7
Sample Output

0
1
0

這個(gè)游戲叫威佐夫博奕

下面，我將如實(shí)地展示我的整個(gè)思考過程。

雖然所有的內(nèi)容（除了貝蒂定理）都是自己想的，不過估計(jì)和網(wǎng)上寫的都是差不多的。

因?yàn)槲規(guī)啄暌郧熬椭懒薭eatty貝蒂定理，現(xiàn)在才知道，估計(jì)這個(gè)定理就是從這個(gè)游戲衍發(fā)出來的。

首先，很容易找到，最小的負(fù)態(tài)是（1，2） (不算（0，0）的話)

（如果先手有必贏策略，那么稱為勝態(tài)，否則稱為負(fù)態(tài)）

定理一：(n,n)是勝態(tài)，(n,0)是負(fù)態(tài) （n>0）

定理二：如果（a,b）和（c,d）是2個(gè)負(fù)態(tài)，那么a,b,c,d互不相等

定理三：（a,b）和（b,a）一定是完全等價(jià)的

（所以本文中只出現(xiàn)（3，5）這種狀態(tài)不出現(xiàn)（5，3）這種狀態(tài)（除了本行））

定理四：一個(gè)狀態(tài)無法轉(zhuǎn)移到任何一個(gè)負(fù)態(tài)，當(dāng)且僅當(dāng)它就是負(fù)態(tài)。

一個(gè)狀態(tài)只要能轉(zhuǎn)移到任何一個(gè)負(fù)態(tài)，那么它就是勝態(tài)

想清楚了這四點(diǎn)之后，可以開始找出所有負(fù)態(tài)了。（都是顯然的定理，我就不證明了）

首先，（3，3）是勝態(tài)，（3，4）因?yàn)榭梢赞D(zhuǎn)移到（1，2）所以是勝態(tài)，（3，5）因?yàn)闆]法轉(zhuǎn)移到任何一個(gè)負(fù)態(tài)，所以它就是負(fù)態(tài)。

然后，（4，4）是勝態(tài)，（4，5）和（4，6）可以轉(zhuǎn)移到（3，5）所以是勝態(tài)，（4，7）是負(fù)態(tài)。

現(xiàn)在，有了前3個(gè)負(fù)態(tài)，（1，2）（3，5）（4，7）

光憑這3組數(shù)據(jù)是不可能發(fā)現(xiàn)規(guī)律的，但是如果結(jié)合剛剛找到它們的方法仔細(xì)思考，那就不一樣了。

比如在找第4個(gè)負(fù)態(tài)的時(shí)候，我們發(fā)現(xiàn)，在（6，6）（6，7）（6，8）（6，9）......

這個(gè)序列中，如果找到1個(gè)負(fù)態(tài)的話，后面的狀態(tài)都可以轉(zhuǎn)移到這個(gè)狀態(tài)，所以后面所有的狀態(tài)都是勝態(tài)。（這其實(shí)就是定理二）

可是要怎么樣知道這個(gè)序列里面有沒有一個(gè)狀態(tài)不能轉(zhuǎn)移到前面3個(gè)負(fù)態(tài)中的任何1個(gè)呢？

請注意！如果這個(gè)序列中的某個(gè)狀態(tài)不能轉(zhuǎn)移到前面3個(gè)負(fù)態(tài)中的任何1個(gè)，那么它就是負(fù)態(tài)！

那么關(guān)鍵來了！狀態(tài)轉(zhuǎn)移的本質(zhì)數(shù)量關(guān)系是什么？

本質(zhì)數(shù)量關(guān)系就是，如果1個(gè)狀態(tài)的2個(gè)數(shù)之差等于另外1個(gè)狀態(tài)的2個(gè)數(shù)之差，那么它們是可以轉(zhuǎn)移的！

前面3個(gè)狀態(tài)的2個(gè)數(shù)之差分別是1，2，3，那么很明顯，上述序列中，有且僅有1個(gè)序列是無法轉(zhuǎn)移到這3個(gè)序列的，就是那個(gè)差為4的狀態(tài)，即（6，10）

到了這里，可能你已經(jīng)明白了，如何快速求出所有的負(fù)態(tài)。

負(fù)態(tài)的2個(gè)數(shù)之差的序列就是1，2，3，4......

如果你認(rèn)為到了這里，我只是發(fā)現(xiàn)規(guī)律，只是猜想第i個(gè)負(fù)態(tài)的2個(gè)數(shù)之差是i，請從頭再看一遍。

實(shí)際上，我們不僅已經(jīng)得到了一個(gè)定理，第i個(gè)負(fù)態(tài)的2個(gè)數(shù)之差是i

我們還得到了另外1個(gè)非常重要的定理，第i個(gè)負(fù)態(tài)的較小數(shù)是集合A中的最小數(shù)，

其中A是自然數(shù)集，去掉前i-1個(gè)負(fù)態(tài)的2*（i-1）個(gè)數(shù)，得到的集合。

結(jié)合定理二可以發(fā)現(xiàn)，任何正整數(shù)都恰好出現(xiàn)在某個(gè)負(fù)態(tài)中而且僅出現(xiàn)1次！

當(dāng)我想到這個(gè)地方的時(shí)候，我突然想起來beatty貝蒂定理

其實(shí)我對這個(gè)定理印象不深，因?yàn)閺膩頉]有用過，直到做這個(gè)題目才是第一次用。

beatty定理：對于任意滿足1/a+1/b=1, 的正無理數(shù)a，b，

都有結(jié)論：[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......都是不同的數(shù)，而且覆蓋正整數(shù)集。

于是我懷疑，beatty貝蒂定理和本題有著本質(zhì)的聯(lián)系。

因?yàn)閷?shí)在是好幾年了，所以我想，還是先證明一下beatty貝蒂定理，找找感覺吧。

beatty貝蒂定理的證明：

對于任意正整數(shù)n，考慮[a]，[2a]，[3a]，[4a]......里面有多少個(gè)數(shù)小于n

(如果考慮有多少個(gè)數(shù)小于等于n，那就得不到什么結(jié)論，因?yàn)楦舅悴怀鰜?，這是由高斯函數(shù)的特性決定的)

根據(jù)高斯函數(shù)的特性，[ka]<n ?iff ka<n ?即，k<n/a （k為整數(shù)）

因?yàn)閚/a是無理數(shù)，所以上式還等價(jià)于k<=[n/a]

所以說，[a]，[2a]，[3a]，[4a]......里面有[n/a]個(gè)數(shù)小于n

同理，[b]，[2b]，[3b]，[4b]......里面有[n/b]個(gè)數(shù)小于n

那么，一共有多少呢？

這個(gè)地方就體現(xiàn)了為什么要是無理數(shù)，因?yàn)閚/a和n/b是無理數(shù)，那么就不是整數(shù)

又因?yàn)閚/a+n/b=n，所以[n/a]+[n/b]=n-1

所以說，對于任意正整數(shù)n，[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......中有n-1個(gè)數(shù)小于n

由此，可以利用數(shù)學(xué)歸納法推出betty貝蒂定理。

數(shù)學(xué)歸納法我就不寫了，簡述如下：

考慮[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......中每個(gè)正整數(shù)有多少個(gè)

有1個(gè)數(shù)小于2，所以有1個(gè)1

有2個(gè)數(shù)小于3，所以有1個(gè)2

有3個(gè)數(shù)小于4，所以有1個(gè)3

......

就這樣，利用第二數(shù)學(xué)歸納法，可以得到每個(gè)正整數(shù)都有且僅有1個(gè)。證畢□

有了貝蒂定理，（1，2）（3，5）（4，7）（6，10）。。。這各序列的通項(xiàng)又要怎么求呢？

還是說，這個(gè)序列根本沒法用貝蒂定理來求？

我不是想死套這個(gè)定理，只是在思考，這2個(gè)東西這么像，應(yīng)該是有本質(zhì)聯(lián)系的吧？

如果親愛的讀者是第一次知道貝蒂定理，可能感覺兩者的關(guān)系并不是很密切。

那么你就需要像我初學(xué)貝蒂定理的時(shí)候一樣，找?guī)讉€(gè)簡單的實(shí)例，比如a=sqrt(2)，或者a=sqrt(3)這種簡單的例子。

a=sqrt(2)時(shí)，b=sqrt(2)+2，把正整數(shù)集的劃分表示成二元組就是：

（1,3）（2,6）（4,10）（5,13）（7,17）。。。。。。

差分別是2,4,6,8,10......規(guī)律和本題的幾乎一樣！只不過都乘了2而已

a=sqrt(3)時(shí)，b=(sqrt(3)+3)/2，把正整數(shù)集的劃分表示成二元組就是：

（1,2）（3,4）（5,7）（6,9）（8,11）。。。。。。

差分別是1,1,2,3,3......這個(gè)貌似沒什么規(guī)律吧？

為什么1個(gè)有規(guī)律，1個(gè)沒規(guī)律呢？

看看a和b的值就一目了然了，a=sqrt(2)時(shí)，b=sqrt(2)+2，[kb]-[ka]=k*2恒成立。

現(xiàn)在是不是感覺這個(gè)數(shù)列和本題的數(shù)列非常像了呢？

還不夠。

不管是a=sqrt(2)還是a=sqrt(3)還是其實(shí)的情況，根據(jù)貝蒂定理，都可以直接推出：

第i二元組中的較小數(shù)是集合A中的最小數(shù)，其中A是自然數(shù)集，去掉前i-1個(gè)二元組的2*（i-1）個(gè)數(shù)得到的集合。

這句話是不是很眼熟？是的，前面描述負(fù)態(tài)二元組的時(shí)候我也是這么描述的。

讓我戳破最后一張紙吧。

相信聰明的讀者也已經(jīng)想到了，如果存在滿足1/a+1/b=1, 且b=a+1，的正無理數(shù)a，b

那第i個(gè)二元組的差不就剛好是i了嗎？

解這個(gè)方程可以得到，a=(sqrt(5)+1)/2，b=(sqrt(5)+3)/2

綜上所述，取a=(sqrt(5)+1)/2，b=(sqrt(5)+3)/2，那么（[ak],b[k]）（k=1,2,3,4......）就是所有的負(fù)態(tài)。

沒錯(cuò)，a-1=(sqrt(5)-1)/2=0.618就是黃金分割！數(shù)學(xué)就是這么美妙而神奇！

代碼：

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
	double Au = (sqrt(5) + 1) / 2;
	int n, m, d;
	while (cin >> n >> m)
	{
		if (n > m)cout << (m != int((n - m)*Au)) << endl;
		else cout << (n != int((m - n)*Au)) << endl;
	}
	return 0;
}

HDU 2177 取(2堆)石子游戲

題目：
Description

有兩堆石子，數(shù)量任意，可以不同。游戲開始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你先取，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。如果你勝，你第1次怎樣取子??
Input

輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個(gè)非負(fù)整數(shù)a和b，表示兩堆石子的數(shù)目，a和b都不大于1,000,000，且a<=b。a=b=0退出。?
Output

輸出也有若干行，如果最后你是敗者，則為0，反之，輸出1，并輸出使你勝的你第1次取石子后剩下的兩堆石子的數(shù)量x,y,x<=y。如果在任意的一堆中取走石子能勝同時(shí)在兩堆中同時(shí)取走相同數(shù)量的石子也能勝，先輸出取走相同數(shù)量的石子的情況.?
Sample Input

1 2?
5 8
4 7
2 2
0 0
Sample Output

0
1
4 7
3 5
0
1
0 0
1 2

這里的get就是直接求含n的負(fù)態(tài)二元組（一定是恰好存在1個(gè)）中，和n對應(yīng)的那個(gè)數(shù)。

代碼：

#include<iostream>
using namespace std;

double Au = (sqrt(5) + 1) / 2;

int get(int n)
{
	int m1 = (int)(n*Au), m2 = (int)((n + 1)*Au - 1);
	if (m1 < m2)return m2;
	return (int)(n*(Au - 1));
}

void out(int m, int n)
{
	if (m>n)cout << n << " " << m << endl;
	else cout << m << " " << n << endl;
}

int main()
{	
	int m, n;
	while (cin >> m >> n)
	{
		if (n == 0)break;
		int k = (int)((n - m)*Au);
		if (m == k)cout << 0 << endl;
		else
		{
			cout << 1 << endl;
			if (m > k)cout << k << " " << n - m + k << endl;
			if (m > get(n))out(n, get(n));
			if (m != n && n > get(m))out(m, get(m));
		}
	}
	return 0;
}

5，其他公平游戲

CSU 1349?Taking Pebbles

題目：

Description
????There is a pile of?N?pebbles initially. Alice and Bob are playing a taking pebbles game as follows:
????Alice and Bob moves by turns, Alice moves first. For each move, the player can takes away at least one and at most half of the pebbles remained (“at most half” means you can take way at most?k?(k?>= 1) pebbles if there are 2*k?or 2*k+1 pebbles remained). If there is only one pebble remained, the player can also take away this pebble. The player who takes away the last pebble wins.
????If Alice and Bob are both clever enough, and they both want to be the winner, who will win?

Input
????The first line has one integer?T?(1 <=?T?<= 200), means there are?T?test cases.
????For each test case, there is only one line with an integer?N?(2 <=?N?<= 109), means the number of pebbles initially.

Output
????For each test case, print “Alice” (without quotation marks) in one line if Alice will win. Otherwise print “Bob” (without quotation marks) instead.

Sample Input
5
2
3
4
5
6
Sample Output
Bob
Alice
Alice
Bob
Alice

題意：

當(dāng)n=1時(shí)可以取1個(gè)，當(dāng)n>1時(shí)最少取1個(gè)最多取n/2個(gè)，兩人輪流取，取完者判勝。

規(guī)律：

當(dāng)n為2,5,11,23......的時(shí)候后手Bob贏，每一項(xiàng)是前一項(xiàng)的2倍加1

當(dāng)n為其他數(shù)時(shí)，先手Alice贏

代碼：

#include<iostream>
using namespace std;
 
int main()
{
	int n, m;
	cin >> n;
	while (cin >> n)
	{
		m = (n + 1) / 3;
		cout << ((n % 3 == 2 && (m&-m) == m) ? "Bob\n" : "Alice\n");
	}
	return 0;
}

CSU 1104?盒子游戲

題目：

Description
有兩個(gè)相同的盒子，其中一個(gè)裝了n個(gè)球，另一個(gè)裝了一個(gè)球。Alice和Bob發(fā)明了一個(gè)游戲，規(guī)則如下：

Alice和Bob輪流操作，Alice先操作。每次操作時(shí)，游戲者先看看哪個(gè)盒子里的球的數(shù)目比較少，然后清空這個(gè)盒子（盒子里的球直接扔掉），然后把另一個(gè)盒子里的球拿一些到這個(gè)盒子中，使得兩個(gè)盒子都至少有一個(gè)球。如果一個(gè)游戲者無法進(jìn)行操作，他（她）就輸了。下圖是一個(gè)典型的游戲：

? ? ?Alice ? ? ? Bob ? ? ? Alice
(5,1)----->(2,3)----->(1,2)----->(1,1)
面對兩個(gè)各裝一個(gè)球的盒子，Bob無法繼續(xù)操作，因此Alice獲勝。你的任務(wù)是找出誰會(huì)獲勝。假定兩人都很聰明，總是采取最優(yōu)策略。

Input
輸入最多包含300組測試數(shù)據(jù)。每組數(shù)據(jù)僅一行，包含一個(gè)整數(shù)n（2<=n<=109）。輸入結(jié)束標(biāo)志為n=0。

Output
對于每組數(shù)據(jù)，輸出勝者的名字

Sample Input
2
3
4
0
Sample Output
Alice
Bob
Alice

思路：

這題其實(shí)就是CSU 1349: Taking Pebbles的變形，也是2倍加1的遞推關(guān)系。

代碼：

#include<iostream>
using namespace std;
 
int main()
{
	int n;
	while (cin >> n && n > 0)cout << (((++n&(-n)) == n) ? "Bob\n" : "Alice\n");
	return 0;
}

力扣 294. 翻轉(zhuǎn)游戲 II

你和朋友玩一個(gè)叫做「翻轉(zhuǎn)游戲」的游戲。游戲規(guī)則如下：

給你一個(gè)字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友輪流將連續(xù)的兩個(gè)?"++"?反轉(zhuǎn)成?"--" 。當(dāng)一方無法進(jìn)行有效的翻轉(zhuǎn)時(shí)便意味著游戲結(jié)束，則另一方獲勝。

請你寫出一個(gè)函數(shù)來判定起始玩家 是否存在必勝的方案 ：如果存在，返回 true ；否則，返回 false 。

?
示例 1：

輸入：currentState = "++++"
輸出：true
解釋：起始玩家可將中間的 "++" 翻轉(zhuǎn)變?yōu)?"+--+" 從而得勝。
示例 2：

輸入：currentState = "+"
輸出：false
?

提示：

1 <= currentState.length <= 60
currentState[i] 不是 '+' 就是 '-'
?

進(jìn)階：請推導(dǎo)你算法的時(shí)間復(fù)雜度。

思路：暴力完成轉(zhuǎn)態(tài)轉(zhuǎn)化

時(shí)間復(fù)雜度很高，粗略估計(jì)是O（L*n!），其中n是字符串中加號的數(shù)量，L是字符串總長度

實(shí)際上的時(shí)間復(fù)雜度比這低，但是不好推導(dǎo)，比較復(fù)雜。

class Solution {
public:
    bool canWin(string s) {        
        for(int i=0;i<s.length()-1;i++){
            if(s[i]=='-'||s[i+1]=='-')continue;
            s[i]='-',s[i+1]='-';
            if(!canWin(s))return true;
            s[i]='+',s[i+1]='+';
        }
        return false;
    }
};

力扣?810. 黑板異或游戲

黑板上寫著一個(gè)非負(fù)整數(shù)數(shù)組 nums[i] 。Alice 和 Bob 輪流從黑板上擦掉一個(gè)數(shù)字，Alice 先手。如果擦除一個(gè)數(shù)字后，剩余的所有數(shù)字按位異或運(yùn)算得出的結(jié)果等于 0 的話，當(dāng)前玩家游戲失敗。?(另外，如果只剩一個(gè)數(shù)字，按位異或運(yùn)算得到它本身；如果無數(shù)字剩余，按位異或運(yùn)算結(jié)果為?0。）

換種說法就是，輪到某個(gè)玩家時(shí)，如果當(dāng)前黑板上所有數(shù)字按位異或運(yùn)算結(jié)果等于 0，這個(gè)玩家獲勝。

假設(shè)兩個(gè)玩家每步都使用最優(yōu)解，當(dāng)且僅當(dāng) Alice 獲勝時(shí)返回 true。

示例：

輸入: nums = [1, 1, 2]
輸出: false
解釋:?
Alice 有兩個(gè)選擇: 擦掉數(shù)字 1 或 2。
如果擦掉 1, 數(shù)組變成 [1, 2]。剩余數(shù)字按位異或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意數(shù)字，因?yàn)?Alice 會(huì)成為擦掉最后一個(gè)數(shù)字的人，她總是會(huì)輸。
如果 Alice 擦掉 2，那么數(shù)組變成[1, 1]。剩余數(shù)字按位異或得到 1 XOR 1 = 0。Alice 仍然會(huì)輸?shù)粲螒颉?br> ?

提示：

1 <= N <= 1000
0 <= nums[i] <= 2^16

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int s=0;
        for(int i=0;i<nums.size();i++)s^=nums[i];
        return s==0 || nums.size()%2==0;
    }
};

力扣?1025.?除數(shù)博弈

愛麗絲和鮑勃一起玩游戲，他們輪流行動(dòng)。愛麗絲先手開局。

最初，黑板上有一個(gè)數(shù)字?n?。在每個(gè)玩家的回合，玩家需要執(zhí)行以下操作：

• 選出任一?x，滿足?0 < x < n?且?n % x == 0?。
• 用?n - x?替換黑板上的數(shù)字?n?。

如果玩家無法執(zhí)行這些操作，就會(huì)輸?shù)粲螒颉?/p>

只有在愛麗絲在游戲中取得勝利時(shí)才返回?true?。假設(shè)兩個(gè)玩家都以最佳狀態(tài)參與游戲。

示例 1：

輸入：n = 2
輸出：true
解釋：愛麗絲選擇 1，鮑勃無法進(jìn)行操作。

示例 2：

輸入：n = 3
輸出：false
解釋：愛麗絲選擇 1，鮑勃也選擇 1，然后愛麗絲無法進(jìn)行操作。

提示：

• 1 <= n <= 1000

class Solution {
public:
    bool divisorGame(int n) {
        return n%2-1;
    }
};

力扣?1510.?石子游戲 IV

Alice 和 Bob 兩個(gè)人輪流玩一個(gè)游戲，Alice 先手。

一開始，有?n?個(gè)石子堆在一起。每個(gè)人輪流操作，正在操作的玩家可以從石子堆里拿走?任意?非零?平方數(shù)?個(gè)石子。

如果石子堆里沒有石子了，則無法操作的玩家輸?shù)粲螒颉?/p>

給你正整數(shù)?n?，且已知兩個(gè)人都采取最優(yōu)策略。如果 Alice 會(huì)贏得比賽，那么返回?True?，否則返回?False?。

示例 1：

輸入：n = 1
輸出：true
解釋：Alice 拿走 1 個(gè)石子并贏得勝利，因?yàn)?Bob 無法進(jìn)行任何操作。

示例 2：

輸入：n = 2
輸出：false
解釋：Alice 只能拿走 1 個(gè)石子，然后 Bob 拿走最后一個(gè)石子并贏得勝利（2 -> 1 -> 0）。

示例 3：

輸入：n = 4
輸出：true
解釋：n 已經(jīng)是一個(gè)平方數(shù)，Alice 可以一次全拿掉 4 個(gè)石子并贏得勝利（4 -> 0）。

示例 4：

輸入：n = 7
輸出：false
解釋：當(dāng) Bob 采取最優(yōu)策略時(shí)，Alice 無法贏得比賽。
如果 Alice 一開始拿走 4 個(gè)石子， Bob 會(huì)拿走 1 個(gè)石子，然后 Alice 只能拿走 1 個(gè)石子，Bob 拿走最后一個(gè)石子并贏得勝利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一開始拿走 1 個(gè)石子， Bob 會(huì)拿走 4 個(gè)石子，然后 Alice 只能拿走 1 個(gè)石子，Bob 拿走最后一個(gè)石子并贏得勝利（7 -> 6 -> 2 -> 1 -> 0）。

示例 5：

輸入：n = 17
輸出：false
解釋：如果 Bob 采取最優(yōu)策略，Alice 無法贏得勝利。

提示：

• 1 <= n <= 10^5

class Solution {
public:
	bool winnerSquareGame(int n) {
		vector<int>v(n + 1, 0);
		for (int i = 0; i <= n; i++) {
			if (v[i] == 0) {
				for (int j = 1; j*j <= n - i; j++)v[j*j + i] = 1;
			}
		}
		return v[n];
	}
};

四，公平組合游戲、Sprague-Grundy定理

1，公平組合游戲

如果一個(gè)公平游戲的每個(gè)狀態(tài)，都可以表示成若干個(gè)子狀態(tài)的組合，且游戲每一次操作，都只能對一個(gè)子狀態(tài)進(jìn)行操作，則稱之為公平組合游戲。

公平組合游戲都屬于公平游戲。

公平游戲可以表示成有向圖，而公平組合游戲可以表示成若干個(gè)有向連通分量。

2，Sprague-Grundy定理

公平組合游戲中，一個(gè)狀態(tài)的SG數(shù)，是所有子狀態(tài)的SG數(shù)的異或和。

PS：只要學(xué)過NIM博弈，就很好理解了，每個(gè)公平組合游戲都可以映射成一個(gè)NIM博弈，其中每個(gè)有向連通分量，就是NIM博弈中的一個(gè)石頭堆，整個(gè)有向圖就是NIM博弈中的所有石頭堆。

3，Nim Game

Nim is a mathematical game of strategy in which two players take turns removing (or "nimming") objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

正向Nim游戲就是誰拿完最后一堆獲勝，規(guī)律很簡單，只要保持自己每次拿完之后，所有堆的數(shù)量異或和為0 即可。

即：異或和為0時(shí)先手負(fù)，不為0時(shí)先手勝

反向是誰拿完就判負(fù)，規(guī)律比較復(fù)雜：如果至少有一堆數(shù)量大于1，那么，異或和為0時(shí)先手負(fù)，不為0時(shí)先手勝，否則，異或和為0時(shí)先手勝，不為0時(shí)先手負(fù)。

Nim游戲的SG數(shù)：一堆石頭的SG數(shù)就是石頭數(shù)。

HDU?2176 取(m堆)石子游戲 (正向Nim)

題目：
Description

m堆石子,兩人輪流取.只能在1堆中取.取完者勝.先取者負(fù)輸出No.先取者勝輸出Yes,然后輸出怎樣取子.例如5堆 5,7,8,9,10先取者勝,先取者第1次取時(shí)可以從有8個(gè)的那一堆取走7個(gè)剩下1個(gè),也可以從有9個(gè)的中那一堆取走9個(gè)剩下0個(gè),也可以從有10個(gè)的中那一堆取走7個(gè)剩下3個(gè).
Input

輸入有多組.每組第1行是m,m<=200000. 后面m個(gè)非零正整數(shù).m=0退出.?
Output

先取者負(fù)輸出No.先取者勝輸出Yes,然后輸出先取者第1次取子的所有方法.如果從有a個(gè)石子的堆中取若干個(gè)后剩下b個(gè)后會(huì)勝就輸出a b.參看Sample Output.?
Sample Input

2
45 45
3
3 6 9
5
5 7 8 9 10
0
Sample Output

No
Yes
9 5
Yes
8 1
9 0
10 3

Nim游戲早就被研究透了，我就不扯了，直接說結(jié)論。

取r為所有數(shù)的異或總值，如果r為0那么先手?jǐn)?，否則先手勝。

如果先手勝的話，他的策略是調(diào)整1個(gè)數(shù)，使得所有數(shù)的異或總值為0

也就是說，取某個(gè)x，將x變成x^r

只要x大于x^r，這個(gè)操作就是允許的。

這樣的x，至少存在一個(gè)，可能會(huì)有很多個(gè)，本題要我們?nèi)枯敵觥?/p>

代碼：
?

#include<iostream>
using namespace std;

int num[200005];

int main()
{	
	int m, r;
	while (scanf("%d",&m))
	{
		if (m == 0)break;
		r = 0;
		for (int i = 0; i < m; i++)
		{
			scanf("%d", &num[i]);
			r = r^num[i];
		}
		if (r == 0)printf("No\n");
		else
		{
			printf("Yes\n");
			for (int i = 0; i < m; i++)if (num[i] >(num[i] ^ r))
				printf("%d %d\n", num[i], num[i] ^ r);
		}
	}
	return 0;
}

POJ 1704 Georgia and Bob (正向Nim的變形)

題目：

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

題意：

有N個(gè)棋子排成一排，位置分別是所給定的整數(shù)，雙方輪流把其中一個(gè)棋子往左移，但是不能超過左邊的棋子，也不能移到同一個(gè)位置，只能移到它的右邊一格。

問先手還是后手有必勝策略。

思路：

兩兩一組，如果是奇數(shù)個(gè)，最左邊的單獨(dú)一組，通過差分，化成Nim博弈

代碼：

#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
	int T, n, s, l[1005];
	cin >> T;
	while (T--)
	{
		cin >> n;
		s = 0;
		for (int i = 0; i < n; i++)cin >> l[i];
		sort(l, l + n);
		if (n % 2)s = l[0] - 1;
		for (int i = n % 2; i < n; i += 2)s ^= l[i + 1] - l[i] - 1;
		if (s)cout << "Georgia will win\n";
		else cout << "Bob will win\n";
	}
	return 0;
}

FZU?1928 硬幣翻轉(zhuǎn)游戲(正向1.5維Nim)

題目：

Description

Alice和Bob決定玩一種硬幣翻轉(zhuǎn)游戲。游戲的最初有n * m個(gè)硬幣被放在一個(gè)棋盤上，有的正面朝上，有的反面朝上，當(dāng)游戲開始的時(shí)候，他們輪流對硬幣進(jìn)行操作。
游戲的規(guī)則是這樣的，當(dāng)輪到一個(gè)人操作的時(shí)候，他必須挑選兩枚硬幣，將它們分別翻轉(zhuǎn)(不是交換)，同時(shí)這兩枚硬幣必須滿足以下條件：

1. 兩枚硬幣必須在同一行或同一列

2. 兩枚硬幣中最右下的那枚必須是從正面翻轉(zhuǎn)到反面

當(dāng)一方無法做出滿足上面要求的操作時(shí)，這一方就輸了，游戲結(jié)束。

比如，當(dāng)游戲初始狀態(tài)是棋盤1時(shí)，Alice翻轉(zhuǎn)完2枚硬幣，可以將其變成 棋盤2的狀態(tài)或棋盤3的狀態(tài)。

?

Alice總是第一個(gè)操作，假設(shè)Alice和Bob都采取最優(yōu)策略來玩這個(gè)游戲，請 你寫一個(gè)程序判斷Alice是否能贏。

Input

首先第一行為T，表示有T組數(shù)據(jù)。接下來為每組數(shù)據(jù)的結(jié)構(gòu)：
每組測試數(shù)據(jù)的第一行有兩個(gè)整數(shù)n和m (2 <= n, m <= 1000)，代表棋盤上排列著n行m列的硬幣，接下來n行，每行 m個(gè)字符描述硬幣的初始狀態(tài)，’F’代表硬幣正面朝上，’B’代表硬幣反面朝上。

Output

對于每組數(shù)據(jù)輸出一行先輸出組數(shù)(從1開始)，接下來如果Alice能贏，輸出YES，否則輸出NO.
Sample Input

2
2 2
FB
BB
2 2
BF
BB
Sample Output

Case 1: NO
Case 2: YES

我只能說這個(gè)OJ絕對有毒啊

#include<iostream>
using namespace std;

int main()
{
	int t, n, m, ans = 0;
	cin >> t;
	char c;
	for (int cas = 1; cas <= t; cas++)
	{
		cin >> n >> m;
		for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)
		{
			cin >> c;
			if (c == 'F')ans ^= (i^j);
		}
		if (ans)cout << "Case " << cas << ": " << "YES" << endl;
		else cout << "Case " << cas << ": " << "NO" << endl;
	}
	return 0;
}

HDU 1907 John (反向Nim)

Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.

Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.
?

Input

The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.

Constraints:
1 <= T <= 474,
1 <= N <= 47,
1 <= Ai <= 4747
?

Output

Output T lines each of them containing information about game winner. Print “John” if John will win the game or “Brother” in other case.
?

Sample Input

2
3
3 5 1
1
1

Sample Output

John
Brother

思路：

flag表示至少有1堆的數(shù)量大于1，s表示異或和，那么if (flag ^ (s > 0))則后手勝，否則先手勝。

代碼：

#include<iostream>
using namespace std;

int main()
{
    int n, a[50];
    cin >> n;
    while (cin >> n) {
        int flag = 0, s = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > 1)flag = 1;
            s ^= a[i];
        }
        if (flag ^ (s > 0))cout << "Brother\n";
        else cout << "John\n";
    }
    return 0;
}

力扣 1908. Nim 游戲 II

Alice 和?Bob 交替進(jìn)行一個(gè)游戲，由 Alice 先手。

在游戲中，共有?n?堆石頭。在每個(gè)玩家的回合中，玩家需要 選擇 任一非空石頭堆，從中移除任意 非零 數(shù)量的石頭。如果不能移除任意的石頭，就輸?shù)粲螒颍瑫r(shí)另一人獲勝。

給定一個(gè)整數(shù)數(shù)組?piles ，piles[i] 為 第?i?堆石頭的數(shù)量，如果 Alice 能獲勝返回?true?，反之返回?false?。

Alice 和 Bob 都會(huì)采取 最優(yōu)策略 。

示例 1：

輸入：piles = [1]
輸出：true
解釋：只有一種可能的情況：
- 第一回合，Alice 移除了第 1 堆中 1 塊石頭。piles = [0]。
- 第二回合，Bob 沒有任何石頭可以移除。Alice 獲勝。
示例?2：

輸入：piles = [1,1]
輸出：false
解釋：可以證明，Bob一定能獲勝。一種可能的情況：
- 第一回合，Alice 移除了第 1 堆中 1 塊石頭。 piles = [0,1]。
- 第二回合，Bob 移除了第 2 堆中 1 塊石頭。 piles = [0,0]。
- 第三回合，Alice 沒有任何石頭可以移除。Bob 獲勝。
示例 3：

輸入：piles = [1,2,3]
輸出：false
解釋：可以證明，Bob一定能獲勝。一種可能的情況：
- 第一回合，Alice 移除了第 3 堆中 3 塊石頭。 piles = [1,2,0]。
- 第二回合，Bob 移除了第 2 堆中 1 塊石頭。 piles = [1,1,0]。
- 第三回合，Alice 移除了第 1 堆中 1 塊石頭。piles = [0,1,0]。
- 第四回合，Bob 移除了第 2 堆中 1 塊石頭。 piles = [0,0,0]。
- 第三回合，Alice 沒有任何石頭可以移除。Bob 獲勝。
?

提示：

n == piles.length
1 <= n <= 7
1 <= piles[i] <= 7
?

進(jìn)階：你能想出一個(gè)?線性時(shí)間?的解決方案嗎？雖然這一答案可能超出了面試所需的范圍，但了解它可能會(huì)很有趣。

class Solution {
public:
    bool nimGame(vector<int>& piles) {
        int ans=0;
        for(auto x:piles)ans^=x;
        return ans;
    }
};

4，Green Hackenbush

Hackenbush游戲是通過移除一個(gè)有根圖的某些邊并自動(dòng)不和根相連的部分，最終沒有邊可移除則判負(fù)。

Green Hackenbush，每條邊都是綠色的，雙方都可以操作。

Blue-Red Hackenbush，有些邊是藍(lán)色，有些邊是紅色，而玩家一只能刪除藍(lán)色邊，玩家二只能刪除紅色邊。

力扣 2005.?斐波那契樹的移除子樹游戲

斐波那契樹是一種按這種規(guī)則函數(shù)?order(n)?創(chuàng)建的二叉樹：

• order(0)?是空樹。
• order(1)?是一棵只有一個(gè)節(jié)點(diǎn)的二叉樹。
• order(n)?是一棵根節(jié)點(diǎn)的左子樹為?order(n - 2)?、右子樹為?order(n - 1)?的二叉樹。

Alice 和?Bob 在玩一種關(guān)于斐波那契樹的游戲，由 Alice 先手。在每個(gè)回合中，每個(gè)玩家選擇一個(gè)節(jié)點(diǎn)，然后移除該節(jié)點(diǎn)及其子樹。只能刪除根節(jié)點(diǎn)?root?的玩家輸?shù)暨@場游戲。

給定一個(gè)整數(shù)?n，假定兩名玩家都按最優(yōu)策略進(jìn)行游戲，若 Alice 贏得這場游戲，返回?true?。若 Bob 贏得這場游戲，返回?false?。

一棵二叉樹的子樹?tree?是由?tree?中某個(gè)節(jié)點(diǎn)及其所有后代節(jié)點(diǎn)組成的樹。樹?tree?也可當(dāng)作自身的子樹。

示例 1:

輸入: n = 3
輸出: true
解釋:
Alice 移除右子樹中的節(jié)點(diǎn) 1。
Bob 要么移除左子樹中的 1，要么移除右子樹中的 2。
Alice 可以移除 Bob 未移除的任意節(jié)點(diǎn)。
Bob 只能刪除根節(jié)點(diǎn) 3，所以 Bob 輸了。
返回 true，因?yàn)?Alice 贏了。

示例 2:

輸入: n = 1
輸出: false
解釋:
Alice 只能移除根節(jié)點(diǎn) 1, 所以 Alice 輸了。
返回 false，因?yàn)?Alice 輸了。

示例 3:

輸入: n = 2
輸出: true
解釋:
Alice 刪除節(jié)點(diǎn) 1.
Bob 只能刪除根節(jié)點(diǎn) 2，所以 Bob 輸了。
返回 true，因?yàn)?Alice 贏了。

提示：

• 1 <= n <= 100

思路：Green Hackenbush的一個(gè)特例。

如果是樹而不是圖，那么sg函數(shù)的遞推式就是sg(root) = (sg(left)+1) ^ (sg(right)+1)

所以本題的sg值就是0 1 3 6 3 3 0 5 7 14 7 7 0 9 11 6 11 0 13......

class Solution {
public:
    bool findGameWinner(int n) {
        return n%6-1;
    }
};

五，有向有環(huán)圖游戲

1，模板

在一張可能有環(huán)的有向圖中，某一個(gè)節(jié)點(diǎn)上有一顆棋子，兩名玩家輪流將棋子沿有向邊移動(dòng)，要么走到預(yù)先定義了勝負(fù)平的節(jié)點(diǎn)，要么沿著環(huán)移動(dòng)判定為平局。

策略：

（1）能走到負(fù)節(jié)點(diǎn)，那就走到負(fù)節(jié)點(diǎn)，當(dāng)前就是勝節(jié)點(diǎn)

（2）如果只能走到勝節(jié)點(diǎn)，那當(dāng)前就是負(fù)節(jié)點(diǎn)

（3）反復(fù)運(yùn)用前2條規(guī)則之后，還沒有確定的節(jié)點(diǎn)，都是平節(jié)點(diǎn)，包括有環(huán)的情況。?

按照這個(gè)策略，其實(shí)求解過程也不難。

class JudgeDirectedCyclicGraph {
public:
    //輸入每個(gè)節(jié)點(diǎn)的出度out, 反圖rg，已知?jiǎng)?負(fù)-1平0的節(jié)點(diǎn)集s
    static void solve(map<int,int>& out, map<int, vector<int>>& rg, map<int, int>& s)
    {
        map<int, int>visit;
        vector<int>v1, v2;
        for (auto si : s) {
            visit[si.first] = 1;
            if (si.second == -1)v1.push_back(si.first);
            if (si.second == 1)v2.push_back(si.first);
        }
        if (!v1.empty())fromV1ToV2(v1, v2, s, visit, rg);
        while (true) {
            if (v2.empty())break;
            else fromV2ToV1(v1, v2, s, visit, rg, out);
            if (v1.empty())break;
            else fromV1ToV2(v1, v2, s, visit, rg);
        }
        for (int i = 0; i < out.size(); i++)s[i];
    }
private:
    static void fromV1ToV2(vector<int>& v1, vector<int>& v2, map<int, int>& s, map<int, int>& visit, map<int, vector<int>>& rg) {
        for (auto x : v1) {
            for (auto x2 : rg[x])
                if (visit[x2] == 0) {
                    s[x2] = 1, v2.push_back(x2), visit[x2] = 1;
                }
        }
        v1.clear();
    }
    static void fromV2ToV1(vector<int>& v1, vector<int>& v2, map<int, int>& s, map<int, int>& visit, map<int, vector<int>>& rg, map<int, int>& out) {
        for (auto x : v2) {
            for (auto x2 : rg[x])if (visit[x2] == 0) {
                if (--out[x2] == 0)s[x2] = -1, v1.push_back(x2), visit[x2] = 1;
            }
        }
        v2.clear();
    }
};

2，適用場景說明

對于初始節(jié)點(diǎn)集s，可以只有勝節(jié)點(diǎn)沒有負(fù)節(jié)點(diǎn)，也可以只有負(fù)節(jié)點(diǎn)沒有勝節(jié)點(diǎn)，也可以都有。但是，一定要保證所有出度為0的點(diǎn)都在s中。

實(shí)際上，這樣給出的圖和初始勝負(fù)節(jié)點(diǎn)，有一個(gè)等價(jià)圖，就是新增一個(gè)負(fù)節(jié)點(diǎn)，把所有的勝節(jié)點(diǎn)都指向這個(gè)負(fù)節(jié)點(diǎn)。這樣的等價(jià)圖中，出度為0的點(diǎn)就只有負(fù)節(jié)點(diǎn)和平節(jié)點(diǎn)。

3，等價(jià)圖的最長非零鏈

在上面的模板中，我用正負(fù)1表示勝負(fù)，0表示平局。

那么在這個(gè)帶權(quán)值的有向圖的等價(jià)圖中，最長的非零鏈的長度，決定了博弈者最多在多少個(gè)回合之前就確定了已經(jīng)有必勝策略了。

要計(jì)算最長非零鏈，只需要統(tǒng)計(jì)fromV1ToV2和fromV2ToV1的調(diào)用次數(shù)即可。

如果2個(gè)函數(shù)一共調(diào)用了n次，那么最長非零鏈就是n個(gè)節(jié)點(diǎn)。

4，OJ實(shí)戰(zhàn)

力扣?913. 貓和老鼠

兩位玩家分別扮演貓和老鼠，在一張?無向?圖上進(jìn)行游戲，兩人輪流行動(dòng)。

圖的形式是：graph[a]?是一個(gè)列表，由滿足?ab?是圖中的一條邊的所有節(jié)點(diǎn)?b?組成。

老鼠從節(jié)點(diǎn)?1?開始，第一個(gè)出發(fā)；貓從節(jié)點(diǎn)?2?開始，第二個(gè)出發(fā)。在節(jié)點(diǎn)?0?處有一個(gè)洞。

在每個(gè)玩家的行動(dòng)中，他們?必須?沿著圖中與所在當(dāng)前位置連通的一條邊移動(dòng)。例如，如果老鼠在節(jié)點(diǎn)?1?，那么它必須移動(dòng)到?graph[1]?中的任一節(jié)點(diǎn)。

此外，貓無法移動(dòng)到洞中（節(jié)點(diǎn)?0）。

然后，游戲在出現(xiàn)以下三種情形之一時(shí)結(jié)束：

• 如果貓和老鼠出現(xiàn)在同一個(gè)節(jié)點(diǎn)，貓獲勝。
• 如果老鼠到達(dá)洞中，老鼠獲勝。
• 如果某一位置重復(fù)出現(xiàn)（即，玩家的位置和移動(dòng)順序都與上一次行動(dòng)相同），游戲平局。

給你一張圖?graph?，并假設(shè)兩位玩家都都以最佳狀態(tài)參與游戲：

• 如果老鼠獲勝，則返回?1；
• 如果貓獲勝，則返回?2；
• 如果平局，則返回?0?。

示例 1：

輸入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
輸出：0

示例 2：

輸入：graph = [[1,3],[0],[3],[0,2]]
輸出：1

提示：

• 3 <= graph.length <= 50
• 1?<= graph[i].length < graph.length
• 0 <= graph[i][j] < graph.length
• graph[i][j] != i
• graph[i]?互不相同
• 貓和老鼠在游戲中總是可以移動(dòng)

class Solution {
public:
	int catMouseGame(vector<vector<int>>& graph) {
		map<int, map<int, map<int, int>>>mn;
		map<int, int>s;
		int id = 0;
		for (int m = 0; m < graph.size(); m++) {
			for (int c = 0; c < graph.size(); c++) {
				for (int t = 0; t <= 1; t++) {
					mn[m][c][t] = id;
					if (m == 0 || c == 0)s[id] = (t ? -1 : 1);
					else if (m == c)s[id] = (t ? 1 : -1);
					id++;
				}
			}
		}
		map<int,int>out;
		map<int, vector<int>> rg;
		for (int m = 0; m < graph.size(); m++) {
			for (int c = 0; c < graph.size(); c++) {
				for (auto m2 : graph[m])out[mn[m][c][0]]++, rg[mn[m2][c][1]].push_back(mn[m][c][0]);
				for (auto c2 : graph[c])out[mn[m][c][1]]++, rg[mn[m][c2][0]].push_back(mn[m][c][1]);
			}
		}
		JudgeDirectedCyclicGraph::solve(out, rg, s);
		int ans = s[mn[1][2][0]];
		return ans == -1 ? 2 : ans;
	}
};

六，有向有環(huán)圖的文章來源地址http://www.zghlxwxcb.cn/news/detail-705133.html

到了這里，關(guān)于公開游戲、基于有向圖的游戲的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！