公平组合游戏-巴什游戏、尼姆游戏和SG函数

绝地灬酷狼 2022-12-11 15:13 191阅读 0赞

### 文章目录 ###

*  公平组合游戏
 *  巴什游戏
 *   *  HDU-1846
 *  尼姆游戏
 *   *  HDU-1850
     *  HDU-1907
 *  SG函数
 *   *  SG函数求解巴什游戏
     *   *  HDU-1846
     *  SG函数求解尼姆游戏
     *   *  HDU-1848
     *  HDU-2999
     *  HDU-1524

# 公平组合游戏 #

--------------------

公平组合游戏(Impartral Combinatorial Game)是满足以下特征的一类问题：

1.  有两个玩家，游戏规则对两人是公平的
2.  两人轮流交替回合，当一个玩家不能走时游戏结束
3.  游戏状态和能走的步数都是有限的
4.  游戏局势不能用来区分玩家身份(比如围棋有黑白方就不属于)

*  P点(P-position)是指前一个玩家(即刚走过一步的玩家)的必胜位置，表示先手必败
 *  N点(N-position)是指下一个玩家的必胜位置，表示先手必胜

# 巴什游戏 #

--------------------

巴什游戏(Bash Game)是 n n n颗石子，每次可以拿1~ m m m颗，两人轮流。  
**结论**是若 n n n% ( m + 1 ) = = 0 (m+1)==0 (m\+1)==0则先手败，否则先手胜。

## HDU-1846 ##

[HDU-1846 Brave Game][]

> **Problem Description**  
> 不重要的背景。。。  
> 各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：  
> 1、 本游戏是一个二人游戏;  
> 2、 有一堆石子一共有n个；  
> 3、 两人轮流进行;  
> 4、 每走一步可以取走1…m个石子；  
> 5、 最先取光石子的一方为胜；  
> 如果游戏的双方使用的都是最优策略，请输出哪个人能赢。  
> **Input**  
> 输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。  
> 每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。  
> **Output**  
> 如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。  
> **Sample Input**  
> 2  
> 23 2  
> 4 3  
> **Sample Output**  
> first  
> second

#include<bits/stdc++.h>
    using namespace std;
    int t, n, m;
    int main() { 
    	scanf("%d", &t);
    	while(t--) { 
    		scanf("%d%d", &n, &m);
    		if (n % (m + 1) == 0)
    			puts("second");
    		else puts("first");
    	}
    	return 0;
    }

# 尼姆游戏 #

--------------------

尼姆游戏(Nim Game)是由 n n n对石子，数量分别是\{a1,a2,…,an\}，两个玩家轮流拿石子，每次可以从任意一堆拿走任意数量的石子，拿到最后一个石子的玩家获胜。  
**结论**是若a1⊕a2⊕…an≠0，则先手必胜（N），否则先手必败（P）

## HDU-1850 ##

[HDU-1850 Being a Good Boy in Spring Festival][]

> **Problem Description**  
> 不重要的背景。。。  
> 咱们玩个小游戏吧 ACM课上学的呢～  
> 下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。  
> 现在我们不想研究到底先手为胜还是为负，我只想问大家：  
> ——“先手的人如果想赢，第一步有几种选择呢？”  
> **Input**  
> 输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1<M<=100)，表示扑克牌的堆数，紧接着一行包含M个整数Ni(1<=Ni<=1000000，i=1…M)，分别表示M堆扑克的数量。M为0则表示输入数据的结束。  
> **Output**  
> 如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。  
> **Sample Input**  
> 3  
> 5 7 9  
> 0  
> **Sample Output**  
> 1

**分析**：  
设 H H H是出来 a \[ i \] a\[i\] a\[i\]外的其他所有数的异或，则 a n s = H ans=H ans=H^ a \[ i \] a\[i\] a\[i\]  
 a n s ans ans^ a \[ i \] = H a\[i\]=H a\[i\]=H ^  a \[ i \] a\[i\] a\[i\] ^ a \[ i \] = H a\[i\]=H a\[i\]=H  
所以 ( a n s (ans (ans^ a \[ i \] ) < = a \[ i \] a\[i\])<=a\[i\] a\[i\])<=a\[i\]，即 H < = a \[ i \] H<=a\[i\] H<=a\[i\]，可以把 a \[ i \] a\[i\] a\[i\]减少到 H H H，就是一种可行方案。  
实在不行这边建议打表

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 102;
    int m, ans, sum, a[maxn];
    int main() { 
    	while (~scanf("%d", &m) && m) { 
    		ans = sum = 0;
    		for (int i = 0; i < m; i++) { 
    			scanf("%d", &a[i]);
    			ans ^= a[i];
    		}
    		if (ans == 0)puts("0");
    		else { 
    			for (int i = 0; i < m; i++) { 
    				if ((ans ^ a[i]) <= a[i])
    					sum++;
    			}
    			printf("%d\n", sum);
    		}
    	}
    	return 0;
    }

## HDU-1907 ##

[HDU-1907 John ][HDU-1907 John]

> **Problem Description**  
> 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

**分析**：  
这道题反过来了，拿最后一颗石子则输，反尼姆博弈，注意特殊情况处理下即可。  
特殊情况： 若所有石堆的数量都是1，那么判断奇偶即可（即异或结果等于0先手必胜）。  
否则异或结果不等于0则先手必胜。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 102;
    int t, n, ans, a;
    int main() { 
    	scanf("%d", &t);
    	while (t--) { 
    		bool tag = false;
    		ans = 0;
    		scanf("%d", &n);
    		for (int i = 0; i < n; i++) { 
    			scanf("%d", &a);
    			ans ^= a;
    			if (a > 1)tag = true;
    		}
    		if (tag && ans != 0) //全1且异或非0
    			puts("John");
    		else if (!tag && ans == 0) //否则异或为0也是先手必胜
    			puts("John");
    		else puts("Brother");
    	}
    	return 0;
    }

# SG函数 #

--------------------

SG函数(Sprague-Grundy)函数是在一个图 G ( X , F ) G(X,F) G(X,F)中，定义结点 x x x的sg函数为 s g ( x ) sg(x) sg(x)，它等于没有指定给它的任意后继结点的 s g sg sg值的最小非负整数。  
有点拗口，不急，他就是找一个不属于集合里的最小非负整数，这个集合就是图的后记结点。  
![在这里插入图片描述][20201006111008278.png_pic_center]

*  sg(0)=0，因为结点0没有后继结点，0是最小非负整数
 *  sg(1)=1，结点1后继结点是0，不等于sg(0)的最小非负整数是1
 *  sg(2)=2，其后继节点是0和1，不等于sg(0)、sg(1)的最小非负整数是2
 *  sg(3)=0，其后继节点是1和2，不等于sg(1)、sg(2)的最小非负整数是0
 *  sg(4)=1，其后继节点是2和3，不等于sg(2)、sg(3)的最小非负整数是1

## SG函数求解巴什游戏 ##

**结论**：  
 s g ( x ) = 0 sg(x)=0 sg(x)=0的结点 x x x是先手必败点，也就是P点。  
**证明**

> 1.  根据sg函数性质，sg(x)=0的结点，没有sg值等于0的后继节点；sg(y)>0的任意结点，必有一条边通向sg值为0的某个后记结点；
> 2.  若sg(x)=0的结点时图上的终点(没有后继节点，出度为0)，显示x=0，它是一个P点；若x有后继节点，那么这些后继结点都能通向某个sg值为0的结点。当玩家甲处于sg(x)=0的结点时，只能转移到sg(x)≠0的结点，下一个玩家乙必然转移到sg(x)=0的点，从而让甲不利，所以sg(x)=0的点是先手必败点。

### HDU-1846 ###

[HDU-1846 Brave Game][]  
题目详情同上文

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int t, n, m, sg[maxn], s[maxn];
    void getsg() { 
    	for (int i = 1; i <= n; i++) { 
    		memset(s, 0, sizeof(s));
    		for (int j = 1; j <= m && j <= i; j++)
    			s[sg[i - j]] = 1; //更新后继结点
    		for (int j = 0; j <= n; j++) //找最小非负整数
    			if (!s[j]) { 
    				sg[i] = j;
    				break;
    			}
    	}
    }
    int main() { 
    	scanf("%d", &t);
    	while (t--) { 
    		scanf("%d%d", &n, &m);
    		getsg();
    		if (sg[n])puts("first");
    		else puts("second");
    	}
    	return 0;
    }

> （插播反爬信息 ）博主CSDN地址：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]

## SG函数求解尼姆游戏 ##

**结论**：  
计算每堆石子的sg值，把所有sg值异或，若结果=0则先手必败。

### HDU-1848 ###

[HDU-1846 Fibonacci again and again][]

> **Problem Description**  
> 不重要的背景。。。  
> 今天，又一个关于Fibonacci的题目出现了，它是一个小游戏，定义如下：  
> 1、 这是一个二人游戏;  
> 2、 一共有3堆石子，数量分别是m, n, p个；  
> 3、 两人轮流走;  
> 4、 每走一步可以选择任意一堆石子，然后取走f个；  
> 5、 f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）；  
> 6、 最先取光所有石子的人为胜者；  
> 假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。  
> **Input**  
> 输入数据包含多个测试用例，每个测试用例占一行，包含3个整数m,n,p（1<=m,n,p<=1000）。  
> m=n=p=0则表示输入结束。  
> **Output**  
> 如果先手的人能赢，请输出“Fibo”，否则请输出“Nacci”，每个实例的输出占一行。  
> **Sample Input**  
> 1 1 1  
> 1 4 1  
> 0 0 0  
> **Sample Output**  
> Fibo  
> Nacci

**分析**：  
注意处理下后继节点即可，值只能取斐波那契数列，然后套结论。（该题三堆石子，多堆也一样）

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int sg[maxn], s[maxn];
    int n, m, p;
    int fibo[15] = {  1,2,3 };
    void getsg() { 
    	for (int i = 0; i <= maxn; i++) { 
    		memset(s, 0, sizeof(s));
    		for (int j = 0; j < 15 && fibo[j] <= i; j++) 
    			s[sg[i - fibo[j]]] = 1;  //更新后继节点
    		for (int j = 0; j <= maxn; j++)  //找最小非负整数
    			if (!s[j]) { 
    				sg[i] = j;
    				break;
    			}
    	}
    }
    int main() { 
    	for (int i = 3; i < 15; i++)
    		fibo[i] = fibo[i - 1] + fibo[i - 2];
    	getsg();
    	while (~scanf("%d%d%d", &n, &m, &p) && (n + m + p)) { 
    		if (sg[n] ^ sg[m] ^ sg[p])
    			puts("Fibo");
    		else puts("Nacci");
    	}
    	return 0;
    }

## HDU-2999 ##

[HDU-2999 Stone Game, Why are you always there? ][HDU-2999 Stone Game_ Why are you always there_]

> **Problem Description**  
> “Alice and Bob are playing stone game…”  
> “Err… Feel bored about the stone game? Don’t be so, because stone game changes all the time!”  
> “What the hell are they thinking for?”  
> “You know, whenever Alice is trying to make fun of Bob, she asked him to play stone game with him.”  
> “Poor Bob… What’s the rule today?”  
> “It seems Alice only allows some fixed numbers of continuous stones can be taken each time. And they begin with one string of stones.”  
> “A string? Formed as a circle or a line?”  
> “A line.”  
> “Well, I think I may help Bob with that.”  
> “How?”  
> “I may tell him to skip this round if he has no chance to win.”  
> “Good idea maybe, I mean, Alice always let Bob play first, because she think herself is smart enough to beat Bob no matter how.”  
> “Yes, she’s actually right about herself. Let me see if Bob has a chance to win…”  
> …  
> **Input**  
> There are multiple test cases, for each test case:  
> The first line has a positive integer N (1<=N<=100).  
> The second line contains N positive integers, a1, a2 … an, separated by spaces, which indicate the fixed numbers Alice gives.  
> The third line, a positive integer M. (M<=1000)  
> Following M lines, one positive integer K (K<=1000) each line. K means in this round, the length of the stone string.  
> **Output**  
> For each K, output “1” if Bob has a chance to win, output “2” if Bob has no chance, or “0” if it’s undeterminable.  
> **Sample Input**  
> 3  
> 1 5 1  
> 1  
> 1  
> **Sample Output**  
> 1

**分析**：  
取出连续的石子，注意位置不能合并(2拿完后，1和3认为是不相邻的)，比如5个石子，S=\{2\}，拿完后剩(3,4,5)、\{(1),(4,5)\}、\{(1,2),(5)\}和(1,2,3)四种情况，只关心剩余区间的长度即\{0,3\}、\{1,2\}，后继状态变成了两个子区间长度的SG函数的异或和。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int sg[maxn], s[maxn];
    int n, m, k, a[102];
    void getsg() { 
    	for (int i = 0; i <= maxn; i++) { 
    		memset(s, 0, sizeof(s));
    		for (int j = 0; j < n && a[j] <= i; j++)
    			for (int k = i - a[j]; k >= 0; k--)//两个状态异或
    				s[sg[k] ^ sg[i - a[j] - k]] = 1;
    		for (int j = 0; j <= maxn; j++)
    			if (!s[j]) { 
    				sg[i] = j;
    				break;
    			}
    	}
    }
    int main() { 
    	while (~scanf("%d", &n)) { 
    		for (int i = 0; i < n; i++)
    			scanf("%d", &a[i]);
    		sort(a, a + n);
    		getsg();
    		scanf("%d", &m);
    		while (m--) { 
    			scanf("%d", &k);
    			if (sg[k])puts("1");
    			else puts("2");
    		}
    	}
    	return 0;
    }

## HDU-1524 ##

[HDU-1524 A Chess Game][]

> **Problem Description**  
> Let’s design a new chess game. There are N positions to hold M chesses in this game. Multiple chesses can be located in the same position. The positions are constituted as a topological graph, i.e. there are directed edges connecting some positions, and no cycle exists. Two players you and I move chesses alternately. In each turn the player should move only one chess from the current position to one of its out-positions along an edge. The game does not end, until one of the players cannot move chess any more. If you cannot move any chess in your turn, you lose. Otherwise, if the misfortune falls on me… I will disturb the chesses and play it again.  
> Do you want to challenge me? Just write your program to show your qualification!  
> **Input**  
> Input contains multiple test cases. Each test case starts with a number N (1 <= N <= 1000) in one line. Then the following N lines describe the out-positions of each position. Each line starts with an integer Xi that is the number of out-positions for the position i. Then Xi integers following specify the out-positions. Positions are indexed from 0 to N-1. Then multiple queries follow. Each query occupies only one line. The line starts with a number M (1 <= M <= 10), and then come M integers, which are the initial positions of chesses. A line with number 0 ends the test case.  
> **Output**  
> There is one line for each query, which contains a string “WIN” or “LOSE”. “WIN” means that the player taking the first turn can win the game according to a clever strategy; otherwise “LOSE” should be printed.  
> **Sample Input**  
> 4  
> 2 1 2  
> 0  
> 1 3  
> 0  
> 1 0  
> 2 0 2  
> 0  
> 4  
> 1 1  
> 1 2  
> 0  
> 0  
> 2 0 1  
> 2 1 1  
> 3 0 1 3  
> 0  
> **Sample Output**  
> WIN  
> WIN  
> WIN  
> LOSE  
> WIN

**分析**：  
有向无环图，最后不能移动就输了，就是sg函数的定义，用dfs异或路径即可。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int sg[maxn], s[maxn];
    int n, m, k, mp[maxn][maxn];
    int dfs(int x) { 
    	if (sg[x] != -1)return sg[x];
    	int vis[maxn] = {  0 };
    	for (int i = 0; i < n; i++)
    		if (mp[x][i])
    			vis[dfs(i)] = 1;
    	for (int i = 0; i < maxn; i++) { 
    		if (!vis[i]) { 
    			sg[x] = i;
    			break;
    		}
    	}
    	return sg[x];
    }
    int main() { 
    	while (~scanf("%d", &n)) { 
    		memset(sg, -1, sizeof(sg));
    		memset(mp, 0, sizeof(mp));
    		for (int i = 0; i < n; i++) { 
    			scanf("%d", &m);
    			for (int j = 0; j < m; j++) { 
    				scanf("%d", &k);
    				mp[i][k] = 1;
    			}
    			if (m == 0)sg[i] = 0;
    		}
    		while (~scanf("%d", &m) && m) { 
    			int ans = 0;
    			for (int i = 0; i < m; i++) { 
    				scanf("%d", &k);
    				if (sg[k] != -1)ans ^= sg[k];
    				else ans ^= dfs(k);
    			}
    			if (ans)puts("WIN");
    			else puts("LOSE");
    		}
    	}
    	return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得一键三连❤*

[HDU-1846 Brave Game]: https://vjudge.net/problem/HDU-1846
[HDU-1850 Being a Good Boy in Spring Festival]: https://vjudge.net/problem/HDU-1850
[HDU-1907 John]: https://vjudge.net/problem/HDU-1907
[20201006111008278.png_pic_center]: /images/20221123/e0d7abfe639442a0a5e80202f06054ff.png
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708
[HDU-1846 Fibonacci again and again]: https://vjudge.net/problem/HDU-1848
[HDU-2999 Stone Game_ Why are you always there_]: https://vjudge.net/problem/HDU-2999
[HDU-1524 A Chess Game]: https://vjudge.net/problem/HDU-1524