[数据结构与算法] 【模板题】几种常见的Nim游戏（博弈论）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【模板题】几种常见的Nim游戏（博弈论） -> 正文阅读

[数据结构与算法]【模板题】几种常见的Nim游戏（博弈论）

一、经典Nim游戏

【题目描述】
给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

【输入格式】
第一行包含整数 $n$ 。
第二行包含 $n$ 个数字，其中第 $i$ 个数字表示第 $i$ 堆石子的数量。

【输出格式】
如果先手方必胜，则输出Yes。
否则，输出No。

【数据范围】
$1≤n≤10^5$
$1≤每堆石子数≤10^9$

【输入样例】

2
2 3

【输出样例】

Yes

【分析】

首先给出结论：若 $a_1\wedge a_2 \wedge \dots \wedge a_n=0$ （ $a_i$ 表示第 $i$ 堆石子的数量），则先手必败，否则先手必胜。

在讲 $N i m$ 游戏之前，先了解一下什么是公平组合游戏 $(I C G)$ 。若一个游戏满足以下条件，则该游戏称为公平组合游戏：

由两名玩家交替行动
在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
不能行动的玩家判负

$N i m$ 游戏属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和3。

什么是先手必胜状态和先手必败状态？

先手必胜状态：先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
先手必败状态：先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

为什么当 $a_1\wedge a_2 \wedge \dots \wedge a_n=0$ 时先手必败，否则先手必胜？

当到达结束状态时，即无法再进行任何操作，此时 $0\wedge 0\wedge \dots \wedge 0=0$ ；
如果其中某一个状态 $a_1\wedge a_2 \wedge \dots \wedge a_n=x$ （ $x$ 不为 $0$ ），那么一定有一种拿法能够使得剩下的数异或值为 $0$ 。证明如下：
假设 $x$ 的二进制表示里最高的一位 $1$ 在第 $k$ 位，则 $a_1\sim a_n$ 中至少有一个数 $a_i$ 的第 $k$ 位是 $1$ （如果全为 $0$ 那么 $x$ 的第 $k$ 位一定是 $0$ ），那么显然 $a_i\wedge x<a_i$ ，所以我们可以从中拿走 $a_i-(a_i\wedge x)$ 个石子，那么第 $i$ 堆石子就剩 $a_i-(a_i-(a_i\wedge x))=a_i\wedge x$ 个，即原式变为： $a_1\wedge a_2\wedge \dots \wedge (a_i\wedge x)\wedge \dots \wedge a_n$ 。由于 $a_1\wedge a_2\wedge \dots \wedge a_i\wedge \dots \wedge a_n=x$ ，因此上式变为 $x\wedge x=0$ 。
如果其中某一个状态 $a_1\wedge a_2 \wedge \dots \wedge a_n=0$ ，那么不管怎么拿，剩下所有数的异或值一定不为 $0$ ，用反证法证明如下：
假设第 $i$ 堆拿走一部分石子后剩余石子数为 $a'_i$ ，且 $a_1\wedge a_2\wedge \dots \wedge a'_i\wedge \dots \wedge a_n=0$ ，而由于已知原状态为 $a_1\wedge a_2\wedge \dots \wedge a_i\wedge \dots \wedge a_n=0$ ，将两个式子进行异或，由于除了 $a_i、a'_i$ 以外其余数都是成对出现，异或值为 $0$ ，因此结果为 $a_i\wedge a'_i=0$ ，所以 $a_i=a'_i$ ，又由于假设第 $i$ 堆已经拿走一部分石子了，与 $a_i=a'_i$ 矛盾，因此假设不成立，原命题成立。

综上，当先手局面为 $a_1\wedge a_2 \wedge \dots \wedge a_n=0$ 时抛给后手的状态一定为 $a_1\wedge a_2 \wedge \dots \wedge a_n≠0$ ，当先手局面为 $a_1\wedge a_2 \wedge \dots \wedge a_n≠0$ 时抛给后手的状态一定是 $a_1\wedge a_2 \wedge \dots \wedge a_n=0$ 。所以当 $a_1\wedge a_2 \wedge \dots \wedge a_n=0$ 时先手必败，否则先手必胜。

【代码】

#include <iostream>
using namespace std;

int main()
{
	int n, res = 0;
	cin >> n;
	while (n--)
	{
		int x;
		cin >> x;
		res ^= x;
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}

二、台阶Nim游戏

【题目描述】
现在，有一个 $n$ 级台阶的楼梯，每级台阶上都有若干个石子，其中第 $i$ 级台阶上有 $a_i$ 个石子 $(i \geq 1)$ 。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

【输入格式】
第一行包含整数 $n$ 。
第二行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 级台阶上的石子数 $a_i$ 。

【输出格式】
如果先手方必胜，则输出Yes。
否则，输出No。

【数据范围】
$1≤n≤10^5$
$1≤a_i≤10^9$

【输入样例】

3
2 1 3

【输出样例】

Yes

【分析】

结论：当奇数级阶梯的石子数量异或值为 $0$ ，即 $a_1\wedge a_3\wedge \dots \wedge a_{2n-1}=0$ 时，先手必败，否则先手必胜。证明思路同经典 $N i m$ 游戏相似。

【代码】

#include <iostream>
using namespace std;

int main()
{
    int n, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (i % 2) res ^= x;
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}

三、集合Nim游戏（SG函数）

【题目描述】
给定 $n$ 堆石子以及一个由 $k$ 个不同正整数构成的数字集合 $S$ 。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 $S$ ，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

【输入格式】
第一行包含整数 $k$ ，表示数字集合 $S$ 中数字的个数。
第二行包含 $k$ 个整数，其中第 $i$ 个整数表示数字集合 $S$ 中的第 $i$ 个数 $s_i$ 。
第三行包含整数 $n$ 。
第四行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 堆石子的数量 $h_i$ 。

【输出格式】
如果先手方必胜，则输出Yes。
否则，输出No。

【数据范围】
$1 \leq n, k \leq 100$
$1≤s_i,h_i≤10000$

【输入样例】

【输出样例】

Yes

【分析】

1.Mex运算：
设 $S$ 表示一个非负整数集合，定义 $m e x (S)$ 为求出不属于集合 $S$ 的最小非负整数运算，即：
$mex(S)=min\left\{x\right\}$ ；
例如： $S=\left\{0,1,2,4\right\}$ ，那么 $m e x (S) = 3$ 。

2.SG函数
在有向图游戏中,对于每个节点 $x$ ,设从 $x$ 出发共有 $k$ 条有向边,分别到达节点 $y_1,y_2,\dots ,y_k$ ，定义 $S G (x)$ 为 $x$ 的后继节点 $y_1,y_2,\dots ,y_k$ 的 $S G$ 函数值构成的集合执行 $m e x$ 运算的结果,即：
$SG(x)=mex(\left\{SG(y_1),SG(y_2),\dots ,SG(y_k)\right\})$
特别地,整个有向图游戏 $G$ 的 $S G$ 函数值被定义为有向图游戏起点 $s$ 的 $S G$ 函数值,即： $S G (G) = S G (s)$ 。
定义终点的 $S G$ 函数值为 $0$ 。

3.有向图游戏的和
设 $G_1,G_2,\dots ,G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G ，$ 他的行动规则是任选某个有向图游戏 $G_i$ ，并在 $G_i$ 上行动一步， $G$ 被称为有向图游戏 $G_1,G_2,\dots ,G_m$ 的和。
有向图游戏的和的 $S G$ 函数值等于它包含的各个子游戏 $S G$ 函数的异或和，即：
$SG(G)=SG(G_1)\wedge SG(G_2)\wedge \dots \wedge SG(G_m)$ 。

4.结论

对于一个图 $G$ ，如果 $S G (G) \neq = 0$ ，则先手必胜，反之必败。
证明：根据 $m e x$ 运算的定义可知，如果 $S G (G) \neq = 0$ ，那么其连接的一点必为 $0$ （如果其后继结点的值均不为 $0$ ，那么该点的 $m e x$ 结果必定为 $0$ ），当走到 $S G$ 值为 $0$ 的这一点时，由于 $m e x$ 运算，该结点所连接的结点的 $S G$ 值必定不为 $0$ 。又因为终点状态的 $S G$ 值为 $0$ ，所以只要先手的 $S G$ 值不为 $0$ ，便可以一直走向 $S G$ 值为 $0$ 的状态，最终走向终点。
对于 $n$ 个图，如果 $SG(G_1)\wedge SG(G_2)\wedge \dots \wedge SG(G_n)≠0$ ，则先手必胜，反之必败。

例子：假设有一堆石子，石子数量为 $10$ ，每次可以拿走 $2$ 个或 $5$ 个，那么其有向图如下图所示：

在这里插入图片描述

红色标注的数字为该结点的 $S G$ 函数值，由于起点 $10$ 的 $S G$ 函数值不为 $0$ ，因此该游戏局面为先手必胜状态。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;

const int N = 110, M = 10010;
int s[N], f[M];
int n, k;

//记忆化搜索保存各结点的SG值
int sg(int x)
{
	if (~f[x]) return f[x];
	unordered_set<int> st;//保存x能到达的后继结点的SG值
	//枚举x能到达的所有状态
	for (int i = 0; i < k; i++)
		if (s[i] <= x) st.insert(sg(x - s[i]));
	//mex操作，找出x后继结点中未出现过的最小的非负整数
	for (int i = 0; ; i++)
		if (!st.count(i))
			return f[x] = i;
}

int main()
{
	cin >> k;
	for (int i = 0; i < k; i++) cin >> s[i];
	memset(f, -1, sizeof f);
	int res = 0;
	cin >> n;
	while (n--)
	{
		int x;
		cin >> x;
		res ^= sg(x);//对每个有向图的起始结点的SG值进行异或运算
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}

四、拆分Nim游戏

【题目描述】
给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 $0$ ，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

【输入格式】
第一行包含整数 $n$ 。
第二行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 堆石子的数量 $a_i$ 。

【输出格式】
如果先手方必胜，则输出Yes。
否则，输出No。

【数据范围】
$1≤n,a_i≤100$

【输入样例】

2
2 3

【输出样例】

Yes

【分析】

相比于集合 $N i m$ 游戏，这里的每一堆可以变成小于原来那堆的任意大小的两堆。
即 $a [i]$ 可以拆分成 $(b [i], b [j])$ ，为了避免重复规定 $b[i]\geq b[j]$ ，即： $a[i]>b[i]\geq b[j]$ 。
相当于一个局面拆分成了两个局面，由 $S G$ 函数理论，多个独立局面的 $S G$ 值，等于这些局面 $S G$ 值的异或和。
因此需要存储的状态就是 $sg(b[i])\wedge sg(b[j])$ 。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;

const int N = 110;
int f[N];
int n;

int sg(int x)
{
	if (~f[x]) return f[x];
	unordered_set<int> st;
	//枚举x可变成的所有状态(i, j)，防止重复j只用枚举到i即可
	for (int i = 0; i < x; i++)
		for (int j = 0; j <= i; j++)
			st.insert(sg(i) ^ sg(j));
	//mex操作
	for (int i = 0; ; i++)
		if (!st.count(i))
			return f[x] = i;
}

int main()
{
	cin >> n;
	memset(f, -1, sizeof f);
	int res = 0;
	while (n--)
	{
		int x;
		cin >> x;
		res ^= sg(x);
	}
	if (res) puts("Yes");
	else puts("No");
	return 0;
}

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2021-10-27 13:04:40 更:2021-10-27 13:07:04

360图书馆购物三丰科技阅读网日历万年历 2024年11日历

-2024/11/26 8:17:44-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码