博弈论的游戏主要分为:
游戏定义:给定 n n n堆物品,第 i i i堆物品有 A i A_i Ai个。两名玩家轮流行动,每次可以人选一堆,取走任意多个物品,可把一堆取光,但不能不取。取走最后一样物品的人获胜。两人都采取最优策略,稳先手能否必胜。
可以看到NIM游戏是一个公平组合游戏
NIM游戏不存在平局,只有先手必胜和先手必败
先手必胜:只要存在某种行动,使得后手一定会输掉游戏
先手必败:无论采取何种行动,先手都会输掉游戏
先手必胜:当且仅当
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
≠
0
A_1 \oplus A_2 \oplus ... \oplus A_n \neq 0
A1⊕A2⊕...⊕An=0
先手必败:当且仅当
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
=
0
A_1 \oplus A_2 \oplus ... \oplus A_n = 0
A1⊕A2⊕...⊕An=0
⊕
\oplus
⊕表示异或(XOR)
当场上不存在石子时,此时 A 1 ⊕ A 2 ⊕ . . . ⊕ A n = 0 ⊕ 0 ⊕ . . . ⊕ 0 = 0 A_1 \oplus A_2 \oplus ... \oplus A_n = 0 \oplus 0 \oplus... \oplus 0=0 A1⊕A2⊕...⊕An=0⊕0⊕...⊕0=0
当场上石子满足 A 1 ⊕ A 2 ⊕ . . . ⊕ A n ≠ 0 A_1 \oplus A_2 \oplus ... \oplus A_n \neq 0 A1⊕A2⊕...⊕An=0时,一定可以在某一堆 A i A_i Ai中取若干石子,使得场上石子变成 A 1 ⊕ A 2 ⊕ . . . ⊕ A n = 0 A_1 \oplus A_2 \oplus ... \oplus A_n = 0 A1⊕A2⊕...⊕An=0
当场上石子满足 A 1 ⊕ A 2 ⊕ . . . ⊕ A n = 0 A_1 \oplus A_2 \oplus ... \oplus A_n = 0 A1⊕A2⊕...⊕An=0时,无论怎么取石子,都会导致场上石子变成 A 1 ⊕ A 2 ⊕ . . . ⊕ A n ≠ 0 A_1 \oplus A_2 \oplus ... \oplus A_n \neq 0 A1⊕A2⊕...⊕An=0
反证:若取后场上石子变成 A 1 ⊕ A 2 ⊕ . . . ⊕ A n = 0 A_1 \oplus A_2 \oplus ... \oplus A_n = 0 A1⊕A2⊕...⊕An=0
当上面三个结论成立时,可以推断出
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
≠
0
A_1 \oplus A_2 \oplus ... \oplus A_n \neq 0
A1⊕A2⊕...⊕An=0使得先手必胜。
这是因为如果初始的石头满足
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
≠
0
A_1 \oplus A_2 \oplus ... \oplus A_n \neq 0
A1⊕A2⊕...⊕An=0,先手可以使石头变成
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
=
0
A_1 \oplus A_2 \oplus ... \oplus A_n = 0
A1⊕A2⊕...⊕An=0,而后手无论怎么取都会使石头变成
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
≠
0
A_1 \oplus A_2 \oplus ... \oplus A_n \neq 0
A1⊕A2⊕...⊕An=0,注意到石头取完的时候,
A
1
⊕
A
2
⊕
.
.
.
⊕
A
n
=
0
A_1 \oplus A_2 \oplus ... \oplus A_n = 0
A1⊕A2⊕...⊕An=0,那么石头取完的情况一定会出现在后手取石头的时候。
#include <iostream>
using namespace std;
int n, a, b;
int main() {
scanf("%d", &n);
while(n -- ) {
scanf("%d", &a);
b ^= a;
}
if (!b) printf("No\n");
else printf("Yes\n");
return 0;
}
和NIM游戏不同的是,每次取得石子数只能是规定的某几个数之一。
要想解决这个问题,需要了解SG函数及其相关概念
求出最小的不属于集合S的非负整数
m
e
x
(
S
)
=
m
i
n
x
∈
N
,
x
∉
S
{
x
}
mex(S)=min_{x\in \mathbb{N}, x\notin S}\{ x\}
mex(S)=minx∈N,x∈/S{x}
例如
S
=
{
0
,
2
,
3
}
S=\{ 0,2,3 \}
S={0,2,3},则
m
e
x
(
S
)
=
1
mex(S)=1
mex(S)=1
定义:给定一个有向无环图,图中有唯一的起点,在起点上放有一枚棋子。两名玩家交替把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动这判负。
任何一个公平组合游戏都可以转化成有向图游戏:每个局面相当于图的一个节点,合法行动是图的边。
设有向图游戏中,节点
x
x
x有
k
k
k条有向边,分别到达节点
y
1
,
y
2
,
.
.
.
,
y
k
y_1,y_2,...,y_k
y1,y2,...,yk,定义
S
G
(
x
)
SG(x)
SG(x)为
x
x
x的后继节点
y
1
,
y
2
,
.
.
.
,
y
k
y_1,y_2,...,y_k
y1,y2,...,yk的
S
G
SG
SG函数值构成的集合再执行
m
e
x
mex
mex运算的结果。
S
G
(
x
)
=
m
e
x
(
{
S
G
(
y
1
)
,
S
G
(
y
2
)
,
.
.
,
S
G
(
y
k
)
}
)
SG(x)=mex(\{SG(y_1),SG(y_2),..,SG(y_k)\})
SG(x)=mex({SG(y1),SG(y2),..,SG(yk)})
整个有向图的SG函数值是起点的SG函数值。
上述定义,说白了就是找 x x x最小不能到达的数字。
设当前有
G
1
,
G
2
,
.
.
.
,
G
m
G_1,G_2,...,G_m
G1,G2,...,Gm总共
m
m
m个有向图游戏,定义有向图游戏
G
G
G,它的行动规则是任选某个有向图
G
i
G_i
Gi,并在
G
i
G_i
Gi上行动一步。
G
G
G就是有向图游戏
G
1
,
G
2
,
.
.
.
,
G
m
G_1,G_2,...,G_m
G1,G2,...,Gm的和。
G
G
G的
S
G
SG
SG函数值等于包含的各个子游戏的
S
G
SG
SG函数值异或和。
S
G
(
G
)
=
S
G
(
G
1
)
⊕
S
G
(
G
2
)
⊕
.
.
.
⊕
S
G
(
G
m
)
SG(G)=SG(G_1) \oplus SG(G_2) \oplus ... \oplus SG(G_m)
SG(G)=SG(G1)⊕SG(G2)⊕...⊕SG(Gm)
像NIM游戏的每堆石子就是一个有向图游戏 G i G_i Gi,整个NIM游戏看作有向图游戏的和。
有向图的某个局面必胜,当且仅当该局面对应节点的SG函数值不等于0
有向图的某个局面必败,当且仅当该局面对应节点的SG函数值等于0
可以看到:
先手只要在
S
G
≠
0
SG\neq 0
SG=0的节点,一定可以让后手处于
S
G
=
0
SG=0
SG=0的节点;后手处于
S
G
=
0
SG=0
SG=0的节点,无论怎么走都会走到
S
G
=
0
SG=0
SG=0的节点;保持这样的关系,最后后手一定会走到没有出边的败局上。
可见
S
G
=
0
SG=0
SG=0的节点就是败局,
S
G
≠
0
SG\neq 0
SG=0的节点就是胜局。
有向图游戏的和证明类似NIM游戏的三个结论。
这题的每堆石子,都是一个有向图游戏。所有石子组成一个有向图游戏的和。
因此只需判断
S
G
(
G
)
=
S
G
(
G
1
)
⊕
S
G
(
G
2
)
⊕
.
.
.
⊕
S
G
(
G
m
)
≠
0
SG(G)=SG(G_1) \oplus SG(G_2) \oplus ... \oplus SG(G_m) \neq 0
SG(G)=SG(G1)⊕SG(G2)⊕...⊕SG(Gm)=0就是胜局。
问题的关键就是如何求一堆石子的SG函数的值,也就是有向图起点SG函数的值。
一堆10个石子,集合
S
=
{
2
,
5
}
S=\{2,5\}
S={2,5}的有向图如下:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
int k, n, s[N], h, ans;
int f[10005];
int dfs(int x) {
if (f[x] != - 1) return f[x];
bool flag[105];
memset(flag, 0, sizeof(flag));
for (int i = 0; i < k; i ++ ) {
if (x >= s[i]) {
flag[dfs(x - s[i])] = 1;
}
}
for (int i = 0; i < N; i ++ ) {
if (!flag[i]) return f[x] = i;
}
}
int main() {
scanf("%d", &k);
for (int i = 0; i < k; i ++ ) scanf("%d", &s[i]);
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
scanf("%d", &h);
memset(f, -1, sizeof(f));
int sg = dfs(h);
ans ^= sg;
}
if (ans) printf("Yes\n");
else printf("No\n");
return 0;
}
也可以用unordered_set代替flag数组
int dfs(int x) {
if (f[x] != - 1) return f[x];
unordered_set<int> num;
for (int i = 0; i < k; i ++ ) {
if (x >= s[i]) {
num.insert(dfs(x - s[i]));
}
}
for (int i = 0; i < N; i ++ ) {
if (!num.count(i)) return f[x] = i;
}
}
要想保证状态稳定,先手必须要将后手的操作抵消:
综上,只考虑奇数台阶的石子异或是否为0,不为0则先手必胜。
#include <iostream>
using namespace std;
int n, a, ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a);
if (i & 1) ans ^= a;
}
if (ans) printf("Yes\n");
else printf("No\n");
return 0;
}
由于每次拆分都会令最大值减少,所以这个游戏最后能够停止。
注意这题和集合NIM游戏不同,集合NIM游戏是在同一个有向图游戏上进行的,这边拆分后会变成两个有向图游戏,所以要求这两个有向图游戏的和的SG值,需要将这两个有向图游戏的SG值异或。
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
int n, a, ans, f[105];
int dfs(int x) {
unordered_set<int> S;
if (f[x] != -1) return f[x];
for (int i = 0; i < x; i ++ ) {
for (int j = 0; j <= i; j ++ ) {
int sg = dfs(i) ^ dfs(j);
S.insert(sg);
}
}
for (int i = 0; ; i ++ ) {
if (!S.count(i)) return f[x] = i;
}
}
int main() {
scanf("%d", &n);
memset(f, -1, sizeof(f));
for (int i = 0; i < n; i ++ ) {
scanf("%d", &a);
ans ^= dfs(a);
}
if (ans) printf("Yes\n");
else printf("No\n");
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁