目录
博弈论
巴什博弈 Bash Game
Problem
有一堆物品共n个，两个人轮流拿，每次至少拿一个，至多拿k个，问是否有必胜的可能？先手必胜还是后手必胜？
结论
若n%(k+1)==0,,则先手必败
例题:CQYZ 取石子游戏1
Problem
Code
#include <cstdio>
#include <iostream>
using namespace std;
void read(int &n){
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
num=num*10+ch-'0';
ch=getchar();
}
n=num*w;
}
int n,k;
int main(){
read(n);
printf(n%(1+k)==0?"2":"1");
return 0;
}尼姆博弈 Nim Game
什么，是inm？？？
Problem
有n堆物品，第i堆数量为a[i]，两个人轮流从某一堆取任意多的物品，每次至少一个，多者不限，最后取光者得胜。
结论
记k=a[1] xor a[2] xor a[3] xor ... xor a[n]
若k==0,则先手必败,否则先手必胜。
例题:luogu P2197 【模板】nim游戏
什么？是inm游戏？
Problem
Code
#include <cstdio>
#include <iostream>
using namespace std;
void read(int &n){
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
num=num*10+ch-'0';
ch=getchar();
}
n=num*w;
}
const int maxn=10005;
int t,n,a[maxn],k;
int main(){
read(t);
while(t--){
read(n);
for(int i=1;i<=n;i++) read(a[i]);
k=a[1];
for(int i=2;i<=n;i++) k=k^a[i];
printf(k==0?"No\n":"Yes\n");
}
return 0;
}SG函数
公平组合游戏
定义：
1、由对阵双方交替行动
2、游戏进程的任意时刻，可以执行的合法行动与轮到哪个玩家无关
3、不能行动的玩家判负。
有向图游戏
给定一个DAG图（有向无环），图中有唯一的起点，在起点处放一个棋子，两名玩家交替沿着边的方向移动棋子，每次只能移动一步，无法移动着判负。这样的游戏叫做“有向图游戏”。
显然，任何的公平组合游戏都可以转化为有向图游戏：我们把每个局面看作节点，当一个局面通过合法行动变成另一个局面时，给这两个局面节点连一条有向边。就像我们画状态转移图一样。
Mex运算
设S表示一个非负整数集合，定义Mex(S)表示求一个不属于S的最小非负整数的运算，即：
\[
mex\left(S\right)=min\left(x\right),x\in N \ and \ x \notin S
\]
SG函数
在有向图游戏中，对于每个节点x,若其儿子为y1,y2…yk,定义函数SG(x)，其值为x的所有儿子的SG函数值构成的集合再执行mex运算的结果，即：
\[
SG\left(x\right)=mex\left(\{SG\left(y_i\right)\}\right)
\]
特别的，整个有向图G的SG函数值被定义为起点s的SG函数值，即:SG(G)=SG(s)。令，对于终点e有SG(e)=0。
SG函数结论：
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0.
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0.
应用
有向图游戏的和
定义一个有向图游戏G，它的每一次行动都可以在G1,G2…Gm共m个子游戏中选择，这里的G就叫做有向图G1,G2…Gm的和。则
\[
SG\left(G\right)=SG\left(G_1\right)\ xor \ SG\left(G_2\right)...\ xor\ SG\left(G_m\right)
\]
例题：CQYZ 移棋子游戏
Problem
分析
题目已经给出是DAG图，然后有K个棋子，自动联想到DAG游戏的和。
分析得到SG(u)的过程，我们需要得到这个u的所有后继节点vi的SG值。
所以考虑用拓扑排序。
于是便有两个部分：
1、求SG->需要找到后继->用正图存
2、求topolsit->需要找前继->用反图存
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
void read(int &n){
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
num=num*10+ch-'0';
ch=getchar();
}
n=num*w;
}
const int maxn=2005;
int n,m,k,pos[maxn],rd[maxn],SG[maxn],vis[maxn];
vector<int> g[maxn],g2[maxn];//正图和反图 正图找后继求SG值 反图找祖宗拓扑排序
void toposort(){
queue<int> q;
for(int i=1;i<=n;i++) if(rd[i]==0) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
//求Mex值
memset(vis,0,sizeof(vis));
int maxx=0;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
maxx=max(maxx,SG[v]);
vis[SG[v]]=1;
}
for(int mex=0;mex<=maxx+1;mex++)
if(!vis[mex]){
SG[u]=mex;
break;
}
//toposort
for(int i=0;i<g2[u].size();i++){
int v=g2[u][i];
if(rd[v]) rd[v]--;
if(rd[v]==0) q.push(v);
}
}
}
bool iswin(){
int S=SG[pos[1]];
for(int i=2;i<=k;i++) S=S^SG[pos[i]];
return S;
}
int main(){
read(n);read(m);read(k);
for(int i=1;i<=m;i++){
int u,v;read(u);read(v);
g[u].push_back(v);
g2[v].push_back(u);
rd[u]++;
}
for(int i=1;i<=k;i++) read(pos[i]);
toposort();
printf(iswin()?"win":"lose");
return 0;
}