博弈问题之SG函数博弈小结
SG函数：
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移 动者判负。事实上，这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下 面我们就在有向无环图的顶点上定义Sprague-Garundy函数。首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
在我的理解中，sg函数就是一个对有向无环图dfs的过程，在处理nim博弈时，多个石堆可以看成多个sg函数值的异或。
例题：
POJ2311 Cutting Game
典型的sg博弈，找后继状态。题意是给出一个n*m的纸片，每次剪成两部分，谁先剪到1*1就胜利。这就是一个找后继的题目，每次剪成的两部分就是前一状态的后继，只要将两个部分的sg值异或起来就是前一状态的sg值。
[cpp]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int sg[201][201];
int dfs(int a,int b)//sg函数的一般写法
{
if(sg[a][b]>=0)
{
return sg[a][b];
}
int i,map[201],r;//map标记数组一定要在dfs内部定义，不然会出现错误
mem(map,0);
FOR(2,(a/2),i)
{
r=dfs(i,b)^dfs(a-i,b);//后继的异或得到前一状态的sg值
map[r]=1;
}
FOR(2,(b/2),i)
{
r=dfs(a,i)^dfs(a,b-i);
map[r]=1;
}
FOR(0,200,i)
{
if(map[i]==0)
{
return sg[a][b]=i;//mex公式的应用
}
}
}
int main()
{
int n,m,sum;
mem(sg,-1);
while(scanf("%d%d",&n,&m)!=EOF)
{
sum=dfs(n,m);
if(sum>0)
{
printf("WIN\n");
}
else
{
printf("LOSE\n");
}
}
return 0;
}
POJ2425 A Chess Game
题意是给你一个拓扑图，一个起点上的n个棋子，两个玩家交替移动棋子，谁无法移动谁输，典型的sg函数运用。套用模板就行了。此题数据量较大，加入了输入优化后刷到了第一版第四名，nice!
[cpp]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int vis[1001][1001],sg[1001];
int n;
int dfs(int x)//典型的sg过程
{
int i;
if(sg[x]!=-1)
{
return sg[x];
}
int f[1001];
mem(f,0);
For(0,n,i)
{
if(vis[x][i]!=-1)
{
f[dfs(i)]=1;
}
}
i=0;
while(f[i])
{
i++;
}
return sg[x]=i;
}
int main()
{
int i,j,k,t,x,p,sum;
while(scanf("%d",&n)!=EOF)
{
mem(vis,-1);
mem(sg,-1);
For(0,n,i)
