公开游戏、基于有向图的游戏

目录

〇，背景

一，公开游戏、策梅洛定理

1，公开游戏

2，策梅洛定理

3，非有向图游戏的公开游戏

力扣 486. 预测赢家（区间DP）

力扣 877. 石子游戏（退化贪心）

力扣 1140. 石子游戏 II（二维DP）

力扣 1406. 石子游戏 III（数列DP）

力扣 1563. 石子游戏 V（区间DP）

 力扣 1686. 石子游戏 VI（贪心）

力扣 1690. 石子游戏 VII（区间DP）

力扣 1872. 石子游戏 VIII（数列DP）

力扣 2029. 石子游戏 IX（贪心）

力扣 1927. 求和游戏（贪心）

二，有向图游戏

1，狭义有向图游戏

2，狭义有向图游戏的SG数

3，广义有向图游戏

4，广义有向图游戏分类

5，非公平游戏的有向图游戏

力扣 2038. 如果相邻两个颜色均相同则删除当前颜色

三，公平游戏

1，公平游戏

2，Bash Game

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

51Nod 1066 Bash游戏（正向Bash）

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

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

3，斐波那契博弈

CSU 2048 Bash游戏升级版

HDU 2516 取石子游戏

4，威佐夫博奕

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

HDU 2177 取(2堆)石子游戏

5，其他公平游戏

CSU 1349 Taking Pebbles

CSU 1104 盒子游戏

力扣 294. 翻转游戏 II

力扣 810. 黑板异或游戏

力扣 1025. 除数博弈

力扣 1510. 石子游戏 IV

四，公平组合游戏、Sprague-Grundy定理

1，公平组合游戏

2，Sprague-Grundy定理

3，Nim Game

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

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

FZU 1928 硬币翻转游戏(正向1.5维Nim)

HDU 1907 John (反向Nim)

力扣 1908. Nim 游戏 II

4，Green Hackenbush

力扣 2005. 斐波那契树的移除子树游戏

五，有向有环图游戏

1，模板

2，适用场景说明

3，等价图的最长非零链

4，OJ实战

力扣 913. 猫和老鼠

〇，背景

本文收录基于有向图的博弈，提供通用的解法。

本文涉及5种博弈类型：公开游戏、有向图游戏、有向有环图游戏、公平游戏、公平组合游戏。

五者的关系：公开游戏包括有向图游戏，有向图游戏包括公平游戏，公平游戏包括公平组合游戏，而有向有环图游戏是单独的。

其中有向图游戏指的是基于有向无环图的游戏，有向有环图游戏是基于可能有环的有向图的游戏。

PS：在有向无环图上，我们定义只有胜负的游戏，而在可能有环的有向图上，我们定义有胜负平三种结局的游戏。

一，公开游戏、策梅洛定理

1，公开游戏

若一个游戏满足如下条件：

1. 双人、回合制；
2. 信息完全公开（perfect information）；
3. 无随机因素（deterministic）；
4. 必然在有限步内结束；
5. 没有平局；

则称之为公开游戏。

2，策梅洛定理

策梅洛定理：公开游戏中的任何一个状态，要么先手有必胜策略，要么后手有必胜策略（下文把这两种状态分别称为“胜态”、“败态”）。

常见的牌类游戏大多不满足条件2、3。

常见的棋类游戏（如井字棋、五子棋、围棋、象棋、跳棋）大多满足条件2、3，在正式竞技中也会通过禁止循环的方式保证条件4，但不一定满足条件5。

3，非有向图游戏的公开游戏

这些游戏其实也可以用有向图表示，但是胜负不是靠走到哪个节点决定的，而是走到终点的过程中累积产生的得分决定。

力扣 486. 预测赢家（区间DP）

 给定一个表示分数的非负整数数组。 玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1:

输入: [1, 5, 2]
输出: False
解释: 一开始，玩家1可以从1和2中进行选择。
如果他选择2（或者1），那么玩家2可以从1（或者2）和5中进行选择。如果玩家2选择了5，那么玩家1则只剩下1（或者2）可选。
所以，玩家1的最终分数为 1 + 2 = 3，而玩家2为 5。
因此，玩家1永远不会成为赢家，返回 False。
示例 2:

输入: [1, 5, 233, 7]
输出: True
解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。
最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。
注意:

1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于10000000。
如果最终两个玩家的分数相等，那么玩家1仍为赢家。

class Solution {
public:

    int res[20][20],flag[20][20];
 
    int PredictTheWinner2(vector<int>& nums, int numsSize,int low,int high){
        if(low>high)return 0;
        if(flag[low][high])return res[low][high];
        flag[low][high]=1;
        return res[low][high]=max(nums[low]-PredictTheWinner2(nums,numsSize,low+1,high),nums[high]-PredictTheWinner2(nums,numsSize,low,high-1));
    }
    bool PredictTheWinner(vector<int>& nums){
        memset(flag,0,sizeof(res));
        return PredictTheWinner2(nums,nums.size(),0,nums.size()-1)>=0;
    }
};

力扣 877. 石子游戏（退化贪心）

题目：

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。
 

提示：

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。

因为限制了数组长度是偶数，所以先手有不败策略。

bool stoneGame(int* piles, int pilesSize){
    return true;
}

力扣 1140. 石子游戏 II（二维DP）

爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

示例 1：

输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。

示例 2:

输入：piles = [1,2,3,4,5,100]
输出：104

提示：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

#define MAX_LENGTH 555

class Solution {
public:
	int maxScore(vector<int>& piles, int i, int M) {
		if (ans.find(i*MAX_LENGTH + M) != ans.end())return ans[i*MAX_LENGTH + M];
		if (piles.size() <= i + M * 2) {
			return ans[i*MAX_LENGTH + M] = sp[piles.size() - 1] - sp[i - 1];
		}
		ans[i*MAX_LENGTH + M] = INT_MIN;
		for (int j = i + 1; j <= i + M * 2; j++) {
			ans[i*MAX_LENGTH + M] = max(ans[i*MAX_LENGTH + M],
				sp[j - 1] - sp[i - 1] - maxScore(piles, j, max(M, j - i)));
		}
		return ans[i*MAX_LENGTH + M];
	}
	int stoneGameII(vector<int>& piles) {
		for (int i = 0; i < piles.size(); i++)sp[i] = sp[i - 1] + piles[i];
        ans.clear();
		auto s = maxScore(piles, 0, 1) + sp[piles.size() - 1];
		return s / 2;
	}
	map<int, int>sp;
    map<int, int>ans;
};

力扣 1406. 石子游戏 III（数列DP）

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

提示：

• 1 <= stoneValue.length <= 5 * 104
• -1000 <= stoneValue[i] <= 1000

class Solution {
public:
	string stoneGameIII(vector<int>& piles) {
		for (int i = 0; i < piles.size(); i++)sp[i] = sp[i - 1] + piles[i];
		ans.clear();
		for (int i = piles.size() - 1; i >= 0; i--) {
			auto t = INT_MIN;
			for (int j = i + 1; j <= i + 3 && j <= piles.size(); j++) {
				t = max(t, sp[j - 1] - ans[j]);
			}
			ans[i] = t - sp[i - 1];
		}
		auto s = ans[0];
		if (s)return s > 0 ? "Alice" : "Bob";
		return "Tie";
	}
	unordered_map<int, int>sp;
	unordered_map<int, int>ans;
};

力扣 1563. 石子游戏 V（区间DP）

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

提示：

• 1 <= stoneValue.length <= 500
• 1 <= stoneValue[i] <= 10^6

class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        m.resize(stoneValue.size());
        for(auto &mi:m)mi.resize(stoneValue.size());
        s.clear();
        s.push_back(0);
        int n = 0;
        for (auto x : stoneValue) {
            n += x;
            s.push_back(n);
        }
        return dp(stoneValue, 0, stoneValue.size() - 1);
    }
    int dp(vector<int>& stoneValue, int low, int high) {
        if (high <= low)return 0;
        if (m[low][high])return m[low][high];
        int ans = 0;
        for (int i = low; i < high; i++) {
            int s1 = s[i + 1] - s[low];
            int s2 = s[high + 1] - s[i + 1];
            int x = 0;
            if (s1 < s2)x = s1 + dp(stoneValue, low, i);
            else if (s1 > s2)x = s2 + dp(stoneValue, i + 1, high);
            else x = s1 + max(dp(stoneValue, low, i), dp(stoneValue, i + 1, high));
            ans = max(ans, x);
        }
        return m[low][high] = ans;
    }
    vector<vector<int>>m;
    vector<int>s;
};

 力扣 1686. 石子游戏 VI（贪心）

Alice 和 Bob 轮流玩一个游戏，Alice 先手。

一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果，用如下的方式表示：

• 如果 Alice 赢，返回 1 。
• 如果 Bob 赢，返回 -1 。
• 如果游戏平局，返回 0 。

示例 1：

输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。

示例 2：

输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。

示例 3：

输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

提示：

• n == aliceValues.length == bobValues.length
• 1 <= n <= 105
• 1 <= aliceValues[i], bobValues[i] <= 100

class Solution {
public:
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        int s=0;
        for(int i=0;i<aliceValues.size();i++){
            aliceValues[i]+=bobValues[i];
            s-=bobValues[i];
        }
        sort(aliceValues.begin(),aliceValues.end());
        for(int i=aliceValues.size()-1;i>=0;i-=2){
            s+=aliceValues[i];
        }
        if(s>0)return 1;
        if(s<0)return -1;
        return 0;
    }
};

力扣 1690. 石子游戏 VII（区间DP）

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

提示：

• n == stones.length
• 2 <= n <= 1000
• 1 <= stones[i] <= 1000

class Solution {
public:
    int stoneGameVII(vector<int>& stoneValue) {
        m.resize(stoneValue.size());
        for(auto &mi:m)mi.resize(stoneValue.size());
        int s=0;
        for(auto x:stoneValue)s+=x;
        return dp(stoneValue, s,0, stoneValue.size() - 1);
    }
    int dp(vector<int>& stoneValue, int s, int low, int high) {
        if (high <= low)return 0;
        if (m[low][high])return m[low][high]-x;
        int ans1 = s-stoneValue[low]-dp(stoneValue, s-stoneValue[low],low+1,high);
        int ans2 = s-stoneValue[high]-dp(stoneValue, s-stoneValue[high],low,high-1);
        int ans = max(ans1,ans2);
        m[low][high] = ans+x;
        return ans;
    }
    vector<vector<int>>m;
    int x = 123456;
};

力扣 1872. 石子游戏 VIII（数列DP）

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

1. 选择一个整数 x > 1 ，并且 移除 最左边的 x 个石子。
2. 将 移除 的石子价值之 和 累加到该玩家的分数中。
3. 将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。

当只剩下 一个 石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下，Alice 和 Bob 的 分数之差 。

示例 1：

输入：stones = [-1,2,-3,4,-5]
输出：5
解释：
- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
两者分数之差为 2 - (-3) = 5 。

示例 2：

输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
两者分数之差为 13 - 0 = 13 。

示例 3：

输入：stones = [-10,-12]
输出：-22
解释：
- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
两者分数之差为 (-22) - 0 = -22 。

提示：

• n == stones.length
• 2 <= n <= 105
• -104 <= stones[i] <= 104

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n=0;
        for(auto x:stones){
            n+=x;
            s.push_back(n);
        }
        n=stones.size();
        map<int,int>dp;
        int maxs = s[n-1];
        for(int i=n-1;i;i--){
            dp[i]=maxs;
            maxs=max(maxs,s[i-1]-dp[i]);
        }
        return dp[1];
    }
    vector<int>s;
};

力扣 2029. 石子游戏 IX（贪心）

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

• 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
• 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

示例 1：

输入：stones = [2,1]
输出：true
解释：游戏进行如下：
- 回合 1：Alice 可以移除任意一个石子。
- 回合 2：Bob 移除剩下的石子。 
已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。

示例 2：

输入：stones = [2]
输出：false
解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 
由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。

示例 3：

输入：stones = [5,1,2,4,3]
输出：false
解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：
- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。

提示：

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

思路：

考虑先手赢的条件，问题转化成：
有n0个0, n1个1，n2个2，先手可以选择1121212...的序列或者2212121...的序列，假设选出的最长长度分别是x1,x2，
那么先手胜利的条件是，x1或者x2满足，x加上n0是奇数，且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;
    }
};

可以重构成：

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);
    }
};

进一步重构成：

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 玩一个游戏，两人轮流行动，Alice 先手 。

给你一个 偶数长度 的字符串 num ，每一个字符为数字字符或者 '?' 。每一次操作中，如果 num 中至少有一个 '?' ，那么玩家可以执行以下操作：

1. 选择一个下标 i 满足 num[i] == '?' 。
2. 将 num[i] 用 '0' 到 '9' 之间的一个数字字符替代。

当 num 中没有 '?' 时，游戏结束。

Bob 获胜的条件是 num 中前一半数字的和 等于 后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 不相等 。

• 比方说，游戏结束时 num = "243801" ，那么 Bob 获胜，因为 2+4+3 = 8+0+1 。如果游戏结束时 num = "243803" ，那么 Alice 获胜，因为 2+4+3 != 8+0+3 。

在 Alice 和 Bob 都采取 最优 策略的前提下，如果 Alice 获胜，请返回 true ，如果 Bob 获胜，请返回 false 。

示例 1：

输入：num = "5023"
输出：false
解释：num 中没有 '?' ，没法进行任何操作。
前一半的和等于后一半的和：5 + 0 = 2 + 3 。

示例 2：

输入：num = "25??"
输出：true
解释：Alice 可以将两个 '?' 中的一个替换为 '9' ，Bob 无论如何都无法使前一半的和等于后一半的和。

示例 3：

输入：num = "?3295???"
输出：false
解释：Bob 总是能赢。一种可能的结果是：
- Alice 将第一个 '?' 用 '9' 替换。num = "93295???" 。
- Bob 将后面一半中的一个 '?' 替换为 '9' 。num = "932959??" 。
- Alice 将后面一半中的一个 '?' 替换为 '2' 。num = "9329592?" 。
- Bob 将后面一半中最后一个 '?' 替换为 '7' 。num = "93295927" 。
Bob 获胜，因为 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。

提示：

• 2 <= num.length <= 105
• num.length 是 偶数 。
• num 只包含数字字符和 '?' 。

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，狭义有向图游戏

在一张有向无环图中，某一个节点上有一颗棋子，两名玩家轮流将棋子沿有向边移动，最先不能移动的一方输。

这里的绿色节点是败态，粉红色是胜态，整个图可以分为4层：

自底向上推导：

底层是最右边的最0层，是败态。

有一条边指向任意败态节点的就是胜态节点，所以第1层的2个节点是胜态。

所有边都指向胜态节点的节点的就是败态节点，所以第2层的1个节点是败态。

第3层的1个节点是胜态。

这个分层推导的例子，可以推广到所有的有向无环图，最终每个节点都有一个非负层数，层数的奇偶性直接决定是胜态还是败态。

2，狭义有向图游戏的SG数

SG数的定义：

其中x->y表示存在x指向y的一条边，mex（S）表示不在集合S中的最小自然数。

SG为0则是败态，SG>0则是胜态。

无论是分层的方式，还是SG数，都可以通过遍历来求出所有状态是胜态还是负态。

3，广义有向图游戏

（1）推广1

在狭义有向图游戏的基础上进行推广，对于任意有向有环图，定义其中一些节点为胜或者负，两名玩家轮流将棋子沿有向边移动。

要想保证最终一定会走到定义了胜负的节点，需要保证出度为0的点一定定义了胜负，出度不为0的每一个点都可以定义或不定义胜负。

这一类游戏全部可以转化成狭义有向图游戏，具体方法是2步：

第1步，把所有定义了胜负的节点，出度置为0，即从他们出发的有向边全部删除。

第2步，新增1个定义为负的节点X，把所有定义成胜的节点，出度置为1，即从他们连一条有向边到X。

这样就转化成了狭义有向图游戏。

（2）推广2

因为有向图本身就是个建模工具，能表达丰富的信息，所以很多博弈都可以转化成有向图游戏（转化成狭义有向图游戏，或有向图游戏推广1），我们把这些游戏都称为广义有向图游戏。

一般说有向图游戏，指的都是广义有向图游戏，属于公开游戏的一种。

公开游戏可能不是广义有向图游戏，因为公开游戏可以不满足每步的走法数有限。

4，广义有向图游戏分类

广义有向图游戏分为三类：

（1）狭义有向图游戏，属于公平游戏

（2）其他公平游戏

（3）非公平游戏的有向图游戏。

也就是说，（1）（2）合起来是公平游戏，而（2）（3）合起来是非狭义有向图游戏的广义有向图游戏。

对于（2）（3），要么转化成（1）求解，要么由于有特定的规则，导致图不是任意图，而是有规律的图，这样我们就求解时就有了简单的退化的方法，而不用真的沿着图去遍历。

5，非公平游戏的有向图游戏

力扣 2038. 如果相邻两个颜色均相同则删除当前颜色

总共有 n 个颜色片段排成一列，每个颜色片段要么是 'A' 要么是 'B' 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。

Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。

• 如果一个颜色片段为 'A' 且 相邻两个颜色 都是颜色 'A' ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 'B' 片段。
• 如果一个颜色片段为 'B' 且 相邻两个颜色 都是颜色 'B' ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 'A' 片段。
• Alice 和 Bob 不能 从字符串两端删除颜色片段。
• 如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。

假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。

示例 1：

输入：colors = "AAABABB"
输出：true
解释：
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 'A' ，这也是唯一一个相邻颜色片段都是 'A' 的 'A' 。

现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 'B' 的颜色片段 'B' 。
因此，Alice 获胜，返回 true 。

示例 2：

输入：colors = "AA"
输出：false
解释：
Alice 先操作。
只有 2 个 'A' 且它们都在字符串的两端，所以她无法执行任何操作。
因此，Bob 获胜，返回 false 。

示例 3：

输入：colors = "ABBBBBBBAAA"
输出：false
解释：
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 'A' 。

ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择，他可以选择任何一个 '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，公平游戏

若一个游戏满足以下条件：
　　1. 双人、回合制；
　　2. 信息完全公开（perfect information）；
　　3. 无随机因素（deterministic）；
　　4. 必然在有限步内结束，且每步的走法数有限（finite）；
　　5. 没有平局；
　　6. 双方可采取的行动及胜利目标都相同（impartial）；
　　7. 这个胜利目标是自己亲手达成终局状态，或者说走最后一步者为胜（normal play）；

则称之为公平游戏。

公平游戏都属于有向图游戏。

虽然有向图游戏中的胜负很明确，但是如果图非常大，则遍历需要的时间很长。

2，Bash Game

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗。

正向：谁拿完就判胜，规律是N是K+1的倍数时先手负，否则先手胜

反向：谁拿完就判负，规律是N-1是K+1的倍数时先手负，否则先手胜

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

题目：

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

这分明是Bash Game，不是Nim Game

代码：

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

51Nod 1066 Bash游戏（正向Bash）

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。

例如N = 3，K = 2。无论A如何拿，B都可以拿到最后1颗石子。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000) 第2 - T + 1行：每行2个数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个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

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

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000) 第2 - T + 1行：每行1个数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个。A B两个人轮流拿，A先拿。每次拿的数量只能是2的正整数次幂，比如(1,2,4,8,16....)，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

例如N = 3。A只能拿1颗或2颗，所以B可以拿到最后1颗石子。（输入的N可能为大数）

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 1000) 第2 - T + 1行：每行1个数N。(1 <= N <= 10^1000)

Output

共T行，如果A获胜输出A，如果B获胜输出B。

Sample Input

3
2
3
4

Sample Output

A
B
A

思路：2的幂其实就是mod 3等于1或2，所以只需要看总数是不是3的倍数

#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
软件学院的新生课上，老师讲述过这样一个游戏。有n个石子，2个人轮流取石子，每轮取走1…m个石子，问如何获胜。这个游戏又称作巴什博弈（Bash Game）。

巴什博弈就是只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（k≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。

现在，我们要该变一下游戏规则，相对于标准的巴什博奕，我们规定最后取光者输，那么又会如何呢？
显然，（n-1）%（m+1）==0则后手胜利
先手会重新决定策略，所以不是简单的相反行的
例如n=15，m=3
后手 先手 剩余
0  2  13
1  3  9
2  2  5
3  1  1
1  0  0
先手胜利，输的人最后必定只抓走一个，如果最后剩下的个数大于1个，则必定会留一个给对手。

现在，我们再次改变一下游戏规则。相对于标准的巴什博奕，我们规定先取者第1次可以取任意多个，但不能全部取完，以后每次取的物品数不能超过上次取的数量的2倍。取完者胜。 现在想请问已经做过数据结构实验一的你，两人开始博弈后，谁有必胜的把握呢？
先取者负输出"Second win". 先取者胜输出"First win".

Input
输入有多组.每组第1行是2 < =n < 231.
n=0退出.

Output
先取者负输出"Second win". 先取者胜输出"First win".
参看Sample Output.

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

思路：斐波那契数列

代码：

#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个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win". 
Input

输入有多组.每组第1行是2<=n<2^31. n=0退出. 
Output

先取者负输出"Second win". 先取者胜输出"First win". 
参看Sample Output. 
Sample Input

2
13
10000
0
Sample Output

Second win
Second win
First win

这个博弈俗称斐波那契博弈，简称FIB博弈。

原理到处都有解释，我就不扯了，不过里面用到的核心定理，我有解释：斐波那契数列的齐肯多夫定理

代码：

#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 取石子游戏

关键词：

取石子游戏、威佐夫博奕、beatty贝蒂定理、胜态、负态、状态转移、覆盖（分划）、高斯函数、第二数学归纳法、黄金分割比例

题目：

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

这个游戏叫威佐夫博奕

下面，我将如实地展示我的整个思考过程。

虽然所有的内容（除了贝蒂定理）都是自己想的，不过估计和网上写的都是差不多的。

因为我几年以前就知道了beatty贝蒂定理，现在才知道，估计这个定理就是从这个游戏衍发出来的。

首先，很容易找到，最小的负态是（1，2） (不算（0，0）的话)

（如果先手有必赢策略，那么称为胜态，否则称为负态）

定理一：(n,n)是胜态，(n,0)是负态 （n>0）

定理二：如果（a,b）和（c,d）是2个负态，那么a,b,c,d互不相等

定理三：（a,b）和（b,a）一定是完全等价的

（所以本文中只出现（3，5）这种状态不出现（5，3）这种状态（除了本行））

定理四：一个状态无法转移到任何一个负态，当且仅当它就是负态。

一个状态只要能转移到任何一个负态，那么它就是胜态

想清楚了这四点之后，可以开始找出所有负态了。（都是显然的定理，我就不证明了）

首先，（3，3）是胜态，（3，4）因为可以转移到（1，2）所以是胜态，（3，5）因为没法转移到任何一个负态，所以它就是负态。

然后，（4，4）是胜态，（4，5）和（4，6）可以转移到（3，5）所以是胜态，（4，7）是负态。

现在，有了前3个负态，（1，2）（3，5）（4，7）

光凭这3组数据是不可能发现规律的，但是如果结合刚刚找到它们的方法仔细思考，那就不一样了。

比如在找第4个负态的时候，我们发现，在（6，6）（6，7）（6，8）（6，9）......

这个序列中，如果找到1个负态的话，后面的状态都可以转移到这个状态，所以后面所有的状态都是胜态。（这其实就是定理二）

可是要怎么样知道这个序列里面有没有一个状态不能转移到前面3个负态中的任何1个呢？

请注意！如果这个序列中的某个状态不能转移到前面3个负态中的任何1个，那么它就是负态！

那么关键来了！状态转移的本质数量关系是什么？

本质数量关系就是，如果1个状态的2个数之差等于另外1个状态的2个数之差，那么它们是可以转移的！

前面3个状态的2个数之差分别是1，2，3，那么很明显，上述序列中，有且仅有1个序列是无法转移到这3个序列的，就是那个差为4的状态，即（6，10）

到了这里，可能你已经明白了，如何快速求出所有的负态。

负态的2个数之差的序列就是1，2，3，4......

如果你认为到了这里，我只是发现规律，只是猜想第i个负态的2个数之差是i，请从头再看一遍。

实际上，我们不仅已经得到了一个定理，第i个负态的2个数之差是i

我们还得到了另外1个非常重要的定理，第i个负态的较小数是集合A中的最小数，

其中A是自然数集，去掉前i-1个负态的2*（i-1）个数，得到的集合。

结合定理二可以发现，任何正整数都恰好出现在某个负态中而且仅出现1次！

当我想到这个地方的时候，我突然想起来beatty贝蒂定理

其实我对这个定理印象不深，因为从来没有用过，直到做这个题目才是第一次用。

beatty定理：对于任意满足1/a+1/b=1, 的正无理数a，b，

都有结论：[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......都是不同的数，而且覆盖正整数集。

于是我怀疑，beatty贝蒂定理和本题有着本质的联系。

因为实在是好几年了，所以我想，还是先证明一下beatty贝蒂定理，找找感觉吧。

beatty贝蒂定理的证明：

对于任意正整数n，考虑[a]，[2a]，[3a]，[4a]......里面有多少个数小于n

(如果考虑有多少个数小于等于n，那就得不到什么结论，因为根本算不出来，这是由高斯函数的特性决定的)

根据高斯函数的特性，[ka]<n  iff ka<n  即，k<n/a （k为整数）

因为n/a是无理数，所以上式还等价于k<=[n/a]

所以说，[a]，[2a]，[3a]，[4a]......里面有[n/a]个数小于n

同理，[b]，[2b]，[3b]，[4b]......里面有[n/b]个数小于n

那么，一共有多少呢？

这个地方就体现了为什么要是无理数，因为n/a和n/b是无理数，那么就不是整数

又因为n/a+n/b=n，所以[n/a]+[n/b]=n-1

所以说，对于任意正整数n，[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......中有n-1个数小于n

由此，可以利用数学归纳法推出betty贝蒂定理。

数学归纳法我就不写了，简述如下：

考虑[a]，[2a]，[3a]，[4a]......[b]，[2b]，[3b]，[4b]......中每个正整数有多少个

有1个数小于2，所以有1个1

有2个数小于3，所以有1个2

有3个数小于4，所以有1个3

......

就这样，利用第二数学归纳法，可以得到每个正整数都有且仅有1个。证毕□

有了贝蒂定理，（1，2）（3，5）（4，7）（6，10）。。。这各序列的通项又要怎么求呢？

还是说，这个序列根本没法用贝蒂定理来求？

我不是想死套这个定理，只是在思考，这2个东西这么像，应该是有本质联系的吧？

如果亲爱的读者是第一次知道贝蒂定理，可能感觉两者的关系并不是很密切。

那么你就需要像我初学贝蒂定理的时候一样，找几个简单的实例，比如a=sqrt(2)，或者a=sqrt(3)这种简单的例子。

a=sqrt(2)时，b=sqrt(2)+2，把正整数集的划分表示成二元组就是：

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

差分别是2,4,6,8,10......规律和本题的几乎一样！只不过都乘了2而已

a=sqrt(3)时，b=(sqrt(3)+3)/2，把正整数集的划分表示成二元组就是：

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

差分别是1,1,2,3,3......这个貌似没什么规律吧？

为什么1个有规律，1个没规律呢？

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

现在是不是感觉这个数列和本题的数列非常像了呢？

还不够。

不管是a=sqrt(2)还是a=sqrt(3)还是其实的情况，根据贝蒂定理，都可以直接推出：

第i二元组中的较小数是集合A中的最小数，其中A是自然数集，去掉前i-1个二元组的2*（i-1）个数得到的集合。

这句话是不是很眼熟？是的，前面描述负态二元组的时候我也是这么描述的。

让我戳破最后一张纸吧。

相信聪明的读者也已经想到了，如果存在满足1/a+1/b=1, 且b=a+1，的正无理数a，b

那第i个二元组的差不就刚好是i了吗？

解这个方程可以得到，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......）就是所有的负态。

没错，a-1=(sqrt(5)-1)/2=0.618就是黄金分割！数学就是这么美妙而神奇！

代码：

#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

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子? 
Input

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。 
Output

输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况. 
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的负态二元组（一定是恰好存在1个）中，和n对应的那个数。

代码：

#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

题意：

当n=1时可以取1个，当n>1时最少取1个最多取n/2个，两人轮流取，取完者判胜。

规律：

当n为2,5,11,23......的时候后手Bob赢，每一项是前一项的2倍加1

当n为其他数时，先手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
有两个相同的盒子，其中一个装了n个球，另一个装了一个球。Alice和Bob发明了一个游戏，规则如下：

Alice和Bob轮流操作，Alice先操作。每次操作时，游戏者先看看哪个盒子里的球的数目比较少，然后清空这个盒子（盒子里的球直接扔掉），然后把另一个盒子里的球拿一些到这个盒子中，使得两个盒子都至少有一个球。如果一个游戏者无法进行操作，他（她）就输了。下图是一个典型的游戏：

     Alice       Bob       Alice
(5,1)----->(2,3)----->(1,2)----->(1,1)
面对两个各装一个球的盒子，Bob无法继续操作，因此Alice获胜。你的任务是找出谁会获胜。假定两人都很聪明，总是采取最优策略。

Input
输入最多包含300组测试数据。每组数据仅一行，包含一个整数n（2<=n<=109）。输入结束标志为n=0。

Output
对于每组数据，输出胜者的名字

Sample Input
2
3
4
0
Sample Output
Alice
Bob
Alice

思路：

这题其实就是CSU 1349: Taking Pebbles的变形，也是2倍加1的递推关系。

代码：

#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. 翻转游戏 II

你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：

给你一个字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友轮流将连续的两个 "++" 反转成 "--" 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。

请你写出一个函数来判定起始玩家 是否存在必胜的方案 ：如果存在，返回 true ；否则，返回 false 。

 
示例 1：

输入：currentState = "++++"
输出：true
解释：起始玩家可将中间的 "++" 翻转变为 "+--+" 从而得胜。
示例 2：

输入：currentState = "+"
输出：false
 

提示：

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

进阶：请推导你算法的时间复杂度。

思路：暴力完成转态转化

时间复杂度很高，粗略估计是O（L*n!），其中n是字符串中加号的数量，L是字符串总长度

实际上的时间复杂度比这低，但是不好推导，比较复杂。

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. 黑板异或游戏

黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）

换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

示例：

输入: nums = [1, 1, 2]
输出: false
解释: 
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。
 

提示：

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. 除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一 x，满足 0 < x < n 且 n % x == 0 。
• 用 n - x 替换黑板上的数字 n 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：n = 2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

输入：n = 3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

• 1 <= n <= 1000

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

力扣 1510. 石子游戏 IV

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

示例 1：

输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。

示例 2：

输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。

示例 3：

输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。

示例 4：

输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。

示例 5：

输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，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，公平组合游戏

如果一个公平游戏的每个状态，都可以表示成若干个子状态的组合，且游戏每一次操作，都只能对一个子状态进行操作，则称之为公平组合游戏。

公平组合游戏都属于公平游戏。

公平游戏可以表示成有向图，而公平组合游戏可以表示成若干个有向连通分量。

2，Sprague-Grundy定理

公平组合游戏中，一个状态的SG数，是所有子状态的SG数的异或和。

PS：只要学过NIM博弈，就很好理解了，每个公平组合游戏都可以映射成一个NIM博弈，其中每个有向连通分量，就是NIM博弈中的一个石头堆，整个有向图就是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游戏就是谁拿完最后一堆获胜，规律很简单，只要保持自己每次拿完之后，所有堆的数量异或和为0 即可。

即：异或和为0时先手负，不为0时先手胜

反向是谁拿完就判负，规律比较复杂：如果至少有一堆数量大于1，那么，异或和为0时先手负，不为0时先手胜，否则，异或和为0时先手胜，不为0时先手负。

Nim游戏的SG数：一堆石头的SG数就是石头数。

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

题目：
Description

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.
Input

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出. 
Output

先取者负输出No.先取者胜输出Yes,然后输出先取者第1次取子的所有方法.如果从有a个石子的堆中取若干个后剩下b个后会胜就输出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游戏早就被研究透了，我就不扯了，直接说结论。

取r为所有数的异或总值，如果r为0那么先手败，否则先手胜。

如果先手胜的话，他的策略是调整1个数，使得所有数的异或总值为0

也就是说，取某个x，将x变成x^r

只要x大于x^r，这个操作就是允许的。

这样的x，至少存在一个，可能会有很多个，本题要我们全部输出。

代码：
 

#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个棋子排成一排，位置分别是所给定的整数，双方轮流把其中一个棋子往左移，但是不能超过左边的棋子，也不能移到同一个位置，只能移到它的右边一格。

问先手还是后手有必胜策略。

思路：

两两一组，如果是奇数个，最左边的单独一组，通过差分，化成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 硬币翻转游戏(正向1.5维Nim)

题目：

Description

Alice和Bob决定玩一种硬币翻转游戏。游戏的最初有n * m个硬币被放在一个棋盘上，有的正面朝上，有的反面朝上，当游戏开始的时候，他们轮流对硬币进行操作。
游戏的规则是这样的，当轮到一个人操作的时候，他必须挑选两枚硬币，将它们分别翻转(不是交换)，同时这两枚硬币必须满足以下条件：

1. 两枚硬币必须在同一行或同一列

2. 两枚硬币中最右下的那枚必须是从正面翻转到反面

当一方无法做出满足上面要求的操作时，这一方就输了，游戏结束。

比如，当游戏初始状态是棋盘1时，Alice翻转完2枚硬币，可以将其变成 棋盘2的状态或棋盘3的状态。

​

Alice总是第一个操作，假设Alice和Bob都采取最优策略来玩这个游戏，请 你写一个程序判断Alice是否能赢。

Input

首先第一行为T，表示有T组数据。接下来为每组数据的结构：
每组测试数据的第一行有两个整数n和m (2 <= n, m <= 1000)，代表棋盘上排列着n行m列的硬币，接下来n行，每行 m个字符描述硬币的初始状态，’F’代表硬币正面朝上，’B’代表硬币反面朝上。

Output

对于每组数据输出一行先输出组数(从1开始)，接下来如果Alice能赢，输出YES，否则输出NO.
Sample Input

2
2 2
FB
BB
2 2
BF
BB
Sample Output

Case 1: NO
Case 2: YES

我只能说这个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堆的数量大于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 交替进行一个游戏，由 Alice 先手。

在游戏中，共有 n 堆石头。在每个玩家的回合中，玩家需要 选择 任一非空石头堆，从中移除任意 非零 数量的石头。如果不能移除任意的石头，就输掉游戏，同时另一人获胜。

给定一个整数数组 piles ，piles[i] 为 第 i 堆石头的数量，如果 Alice 能获胜返回 true ，反之返回 false 。

Alice 和 Bob 都会采取 最优策略 。

示例 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
 

进阶：你能想出一个 线性时间 的解决方案吗？虽然这一答案可能超出了面试所需的范围，但了解它可能会很有趣。

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

4，Green Hackenbush

Hackenbush游戏是通过移除一个有根图的某些边并自动不和根相连的部分，最终没有边可移除则判负。

Green Hackenbush，每条边都是绿色的，双方都可以操作。

Blue-Red Hackenbush，有些边是蓝色，有些边是红色，而玩家一只能删除蓝色边，玩家二只能删除红色边。

力扣 2005. 斐波那契树的移除子树游戏

斐波那契树是一种按这种规则函数 order(n) 创建的二叉树：

• order(0) 是空树。
• order(1) 是一棵只有一个节点的二叉树。
• order(n) 是一棵根节点的左子树为 order(n - 2) 、右子树为 order(n - 1) 的二叉树。

Alice 和 Bob 在玩一种关于斐波那契树的游戏，由 Alice 先手。在每个回合中，每个玩家选择一个节点，然后移除该节点及其子树。只能删除根节点 root 的玩家输掉这场游戏。

给定一个整数 n，假定两名玩家都按最优策略进行游戏，若 Alice 赢得这场游戏，返回 true 。若 Bob 赢得这场游戏，返回 false 。

一棵二叉树的子树 tree 是由 tree 中某个节点及其所有后代节点组成的树。树 tree 也可当作自身的子树。

示例 1:

输入: n = 3
输出: true
解释:
Alice 移除右子树中的节点 1。
Bob 要么移除左子树中的 1，要么移除右子树中的 2。
Alice 可以移除 Bob 未移除的任意节点。
Bob 只能删除根节点 3，所以 Bob 输了。
返回 true，因为 Alice 赢了。

示例 2:

输入: n = 1
输出: false
解释:
Alice 只能移除根节点 1, 所以 Alice 输了。
返回 false，因为 Alice 输了。

示例 3:

输入: n = 2
输出: true
解释:
Alice 删除节点 1.
Bob 只能删除根节点 2，所以 Bob 输了。
返回 true，因为 Alice 赢了。

提示：

• 1 <= n <= 100

思路：Green Hackenbush的一个特例。

如果是树而不是图，那么sg函数的递推式就是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;
    }
};

五，有向有环图游戏

1，模板

在一张可能有环的有向图中，某一个节点上有一颗棋子，两名玩家轮流将棋子沿有向边移动，要么走到预先定义了胜负平的节点，要么沿着环移动判定为平局。

策略：

（1）能走到负节点，那就走到负节点，当前就是胜节点

（2）如果只能走到胜节点，那当前就是负节点

（3）反复运用前2条规则之后，还没有确定的节点，都是平节点，包括有环的情况。 

按照这个策略，其实求解过程也不难。

class JudgeDirectedCyclicGraph {
public:
    //输入每个节点的出度out, 反图rg，已知胜1负-1平0的节点集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，适用场景说明

对于初始节点集s，可以只有胜节点没有负节点，也可以只有负节点没有胜节点，也可以都有。但是，一定要保证所有出度为0的点都在s中。

实际上，这样给出的图和初始胜负节点，有一个等价图，就是新增一个负节点，把所有的胜节点都指向这个负节点。这样的等价图中，出度为0的点就只有负节点和平节点。

3，等价图的最长非零链

在上面的模板中，我用正负1表示胜负，0表示平局。

那么在这个带权值的有向图的等价图中，最长的非零链的长度，决定了博弈者最多在多少个回合之前就确定了已经有必胜策略了。

要计算最长非零链，只需要统计fromV1ToV2和fromV2ToV1的调用次数即可。

如果2个函数一共调用了n次，那么最长非零链就是n个节点。

4，OJ实战

力扣 913. 猫和老鼠

两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：

• 如果猫和老鼠出现在同一个节点，猫获胜。
• 如果老鼠到达洞中，老鼠获胜。
• 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。

给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

• 如果老鼠获胜，则返回 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] 互不相同
• 猫和老鼠在游戏中总是可以移动

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;
	}
};

六，有向有环图的文章来源地址https://www.toymoban.com/news/detail-705133.html

到了这里，关于公开游戏、基于有向图的游戏的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！