博弈论
N:必胜局面
P:必败局面
巴什博奕
一堆物品有n个，两个人轮流拿，每次至少拿1个，至多拿k个。
则n%(k+1)==0时先手必败其他情况下先手必胜
尼姆博奕
n堆物品，第i堆数量为a[i]，两人轮流从某一堆里曲任意多的物品
记k=a[1]^a[2]^...^a[n]
若k==0则先手必败
否则先手必胜
SG函数
以下内容全摘自PPT
公平组合游戏
若一个游戏满足条件：
- 由对阵双方交替行动
- 游戏进程的任意时刻，可以执行的合法行动与轮到哪个玩家无关
- 不能行动的玩家判负。
- 则称这样的游戏为公平组合游戏。
显然，巴什博弈、尼姆博弈都是公平组合游戏，而常见的棋类游戏就不是公平组合游戏，尤其是五子棋（先手有必胜态，不知道吧？）
以上摘自PPT
有向图游戏
给定一个DAG图（有向无环），图中有唯一的起点，在起点处放一个棋子，两名玩家交替沿着边的方向移动棋子，每次只能移动一步，无法移动着判负。这样的游戏叫做“有向图游戏”。
显然，任何的公平组合游戏都可以转化为有向图游戏：我们把每个局面看作节点，当一个局面通过合法行动变成另一个局面时，给这两个局面节点连一条有向边。就像我们画状态转移图一样。
摘自PPT
Mex运算
设S表示一个非负整数集合，定义Mex(S)表示求一个不属于S的最小非负整数的运算，即：
mex(S)=min(x),e∈N且x∈/S
摘自PPT
SG函数
在有向图游戏中，对于每个节点x,
若其儿子为y1,y2…yk,定义函数SG(x)，
其值为x的所有儿子的SG函数值构成的集合再执行mex运算的结果，即：
SG(x)=mex(SG(yi))
特别的，整个有向图G的SG函数值被定义为起点s的SG函数值，
即:SG(G)=SG(s)。令，对于终点e有SG(e)=0。
对于一个状态，若其SG值等于0，则一定是P态，否则就是N态。
特点
- 根据mex函数的特点，设Si的某个后继节点为Sj，当SG(Sj)=0时，SG(Si)必然不等于0，表明当一个局面的后继局面中存在必败局，则该局面必胜。
- 若Si的所有后继节点Sj,都有SG(Sj)!=0，则SG(Si)必然等于0，说明一个局面的全部后继都是必胜局面，则该局面为必败局面。
- SG的求解似乎都需要逆推，因为SG(终态)=0
有向图游戏和
定义一个有向图游戏G，它的每一次行动都可以在G1,G2…Gm共m个子游戏中选择，这里的G就叫做有向图G1,G2…Gm的和。则：
SG(G)=SG(G1)xorSG(G2)xor...xorSG(Gm)
例题（板子）
1
2
3
4
5
6
| 移棋子游戏
题目描述：给定一个有N个节点的DAG图，图中某些节点上有棋子，两名玩家交替移动棋子。玩家每一步可以将任意一颗棋子沿着有向边移动到下一个节点，无法移动者输掉游戏。
假设双方都足够聪明。问先手必胜还是后手必胜！
输入：第一行三个整数N,M,K,表示N个节点M条边K个棋子，接下来M行，每行两个整数x,y,代表x节点到y节点的有向边，再接下来K行，表示K个棋子所在的节点编号。
输出：先手胜则输出“win”，否则输出“lose”
Hint:N<=2000,M<=6000,1<=K<=N;
|
还是有点像拓扑
需要一个正图一个反图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define clear(a) memset(a,0,sizeof(a))
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int MAXN=6005;
int n,m,k;
int chudu[MAXN],qizi[MAXN],v[MAXN],sg[MAXN];
struct tu{
public:
int newp;
int head[MAXN];
struct ed{
int to,w,nex;
} e[MAXN];
tu(void){
clear(head);
clear(e);
}
void insert(int p1,int p2){
++newp;
e[newp].to=p2;
e[newp].nex=head[p1];
//e[newp].w=w;
head[p1]=newp;
}
};
tu a,b;
string solve(void);
int main(void){
cin>>n>>m>>k;
for(int i=1;i<=m;++i){
int x,y;
cin>>x>>y;
a.insert(x,y);
b.insert(y,x);
++chudu[x];
}
for(int i=1;i<=k;++i){
cin>>qizi[i];
}
cout<<solve()<<endl;
return 0;
}
string solve(void){
queue<int> q;
for(int i=1;i<=n;++i){
if(!chudu[i]){
q.push(i);
}
}
while(!q.empty()){
clear(v);
int u=q.front();
q.pop();
int maxsg=0;
for(int i=a.head[u];i;i=a.e[i].nex){
int y=a.e[i].to;
maxsg=max(maxsg,sg[y]);
v[sg[y]]=1;
}
int i=0;
while(i<=maxsg+1){
if(!v[i])break;
++i;
}
sg[u]=i;
for(int i=b.head[u];i;i=b.e[i].nex){
--chudu[b.e[i].to];
if(!chudu[b.e[i].to])q.push(b.e[i].to);
}
}
int ans=sg[qizi[1]];
for(int i=2;i<=k;++i){
ans^=sg[qizi[i]];
}
if(!ans)return "lose";
else return "win";
}
|
