博弈论之SG函数

Nim游戏基本定理： Nim博弈先手必胜，当且仅当$A_{1}xor{A}_{2}xor{A}_3...xor{A}_n\ne 0$

公平组合游戏ICG

1. 两名玩家交替行动；
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3. 不能行动的玩家判负。

有向图游戏 给定一个有向无环图，图中有一个唯一的起点，在起点上放一枚棋子，两名玩家交替的把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏，任何一个公平组合游戏都可以转化为有向图游戏。 有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0； 有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

mex运算 设S表示一个非负整数集合。定义$mex(S)$为求出不属于集合S的最小非负整数的运算： $mex(S)=min$$(x)(x$ $\in$ N$,x$ $\notin$ S)

SG函数 在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点$y_1,y_2,...y_k$，定义SG(x)为x的后继节点
$y_1,y_2,...y_k$的SG函数值构成的集合再执行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​)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点start的SG函数值。

有向图游戏的和 有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和。 $SG(G)=SG(G_1)xorSG(G_2)xorSG(G_3)xor...xorSG(G_m)$

---

891. Nim游戏

#include
using namespace std;
int n,x,ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		ans^=x;
	}
	if(ans) cout<<"Yes";
	else cout<<"No";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

892. 台阶-Nim游戏

因为第一阶拿到地面要拿一次，第二阶拿两次，第三阶拿三次…所以可以看成第二阶有两堆石子，第三阶有三堆…偶数阶石子为偶数堆，异或为0；奇数阶异或后就是原本石子数目，所以可以把原本所有奇数阶的石子进行异或，得到的就是答案。

#include
using namespace std;
int n,x,ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(i%2) ans^=x;
	}
	if(ans) cout<<"Yes";
	else cout<<"No";
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

893. 集合-Nim游戏

#include
using namespace std;

int mem[10010],n,k,a[110],ans,box[10010][110];

int sg(int x)
{
    if(mem[x]!=-1) return mem[x];
    for(int i=1;i<=k;i++)
        if(a[i]<=x)  box[x][sg(x-a[i])]=1;//枚举集合内的数
    for(int i=0;;i++)
        if(!box[x][i]) return mem[x]=i;
}

int main()
{
    cin>>k;
    memset(mem,-1,sizeof mem);
    for(int i=1;i<=k;i++)
        cin>>a[i];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        ans^=sg(x);
    }
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
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

894. 拆分-Nim游戏

#include
using namespace std;

int n,k,a[110],ans,maxn,mem[110],box[110][200];

int sg(int x)
{
    if(mem[x]!=-1) return mem[x];
    for(int i=0;i<x;i++)
        for(int j=0;j<=i;j++)//枚举更小的两个堆
            box[x][sg(i)^sg(j)]=1;
    for(int i=0;;i++)
        if(!box[x][i]) return mem[x]=i;
}

int main()
{
    cin>>n;
    memset(mem,-1,sizeof mem);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans^=sg(a[i]);
    }
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
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

1319. 移棋子游戏

就是建有向图了。

#include
using namespace std;
const int M=6010,N=2010;
int n,m,k,tot,ans,mem[N],box[N][2*N];
int head[N],ver[M],nex[M];

void add(int x,int y)
{
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}


int SG(int u)
{
    if (mem[u]!=-1) return mem[u];值已经被计算过了，直接返回
    set<int> S;     
    for (int i=head[u];i;i=nex[i])
        S.insert(SG(ver[i]));  
    for (int i=0;;i++)    
        if (!S.count(i)) 
            return mem[u]=i;
}


int main()
{
    cin>>n>>m>>k;
    memset(mem,-1,sizeof mem);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=k;i++)
    {
        int x;
        scanf("%d",&x);
        /*for(int j=head[i];j;j=nex[j])
            cout<
        ans^=SG(x);
        //cout<<"x:"<
    }
    if(ans) cout<<"win";
    else cout<<"lose";
    return 0;
}
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

P2575 高手过招

状态压缩，在SG内转移状态

#include
using namespace std;
int T,n,m,x;
int mem[1<<20];

int SG(int state)
{
	if(mem[state]!=-1) return mem[state];
	set<int>S;
	for(int i=0;i<20;i++) 
	{
		if((state>>i)&1)
		{
			for(int j=i-1;j>=0;j--)
			{
				if(!((state>>j)&1))
				{
					S.insert(SG(state^(1<<i)^(1<<j)));
					break;
				}
			}
		}
	}
	for(int i=0;;i++)
		if(S.count(i)==0)
		{
			//printf("SG(%d):%d\n",state,i);
			return mem[state]=i;
		}
}

int main()
{
	memset(mem,-1,sizeof mem);
	for(int i=1;i<=20;i++)
		mem[(1<<i)-1]=0;
	cin>>T;
	while(T--)
	{
		cin>>n;
		int ans=0;
		while(n--)
		{
			cin>>m;
			int state=0;
			for(int i=0;i<m;i++)
			{
				scanf("%d",&x);
				state|=(1<<(20-x));
			}
			ans^=SG(state);
		}
		if(ans) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}
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

上面的有点慢，开氧气能卡过。试图预处理一下，结果MLE了。。。

#include
#define lowbit(x) x&(-x)
using namespace std;
int T,n,m,x;
int mem[1<<20],nex[21],a[21],num[1<<20];

int SG(int state)
{
	if(mem[state]!=-1) return mem[state];
	set<int>S;
	int now=state,last=0;
	while(now)
	{
		int t=lowbit(now);
		if(nex[num[t]]!=-1)
			S.insert(SG(state^t^(1<<nex[num[t]])));
		now-=t;
	}
	/*for(int i=0;i<20;i++) 
	{
		if((state>>i)&1)
		{
			for(int j=i-1;j>=0;j--)
			{
				if(!((state>>j)&1))
				{
					S.insert(SG(state^(1<
	for(int i=0;;i++)
		if(S.count(i)==0)
		{
			//printf("SG(%d):%d\n",state,i);
			return mem[state]=i;
		}
}

int main()
{
	memset(mem,-1,sizeof mem);
	for(int i=1;i<=20;i++)
		mem[(1<<i)-1]=0,num[1<<(i-1)]=(i-1);
	cin>>T;
	while(T--)
	{
		cin>>n;
		int ans=0;
		while(n--)
		{
			cin>>m;
			int state=0;
			for(int i=0;i<m;i++)
			{
				scanf("%d",&a[i]);
				a[i]=20-a[i];
				state|=(1<<(a[i]));
			}
			nex[m-1]=a[m-1]-1;
			for(int i=m-2;i>=0;i--)
			{
				if(a[i]==a[i+1]+1) nex[i]=nex[i+1];
				else nex[i]=a[i]-1;
			}//预处理出下一个位置
			ans^=SG(state);
		}
		if(ans) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

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

不好想的是当作台阶Nim处理QAQ：

图源

#include
using namespace std;
int T,n;
int vis[25];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		int ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		{
			int now=0,num;
			memset(vis,0,sizeof(vis));
			scanf("%d",&num);
			for(int j=1;j<=num;++j)
			{
				int x;
				scanf("%d",&x);
				vis[x]=1;
			}
			int cnt=0,tot=0;
			for(int j=20;j>=0;j--)
			{
				if(!vis[j])
				{
					if(tot)
					{
						ans^=tot;
						tot=0;
					}
					cnt^=1;
				}
				else if(cnt) ++tot;
			}
			if(tot) ans^=tot;
		}
		printf("%s\n",ans?"YES":"NO");
	}
	return 0;
}
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

---

另外扔一些最近写的博弈

P4643 [国家集训队]阿狸和桃子的游戏

#include
#include
using namespace std;

int n,m,ans,a[10001];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
    {
		cin>>a[i];
		a[i]*=2;
	}
	for(int i=1;i<=m;i++)
    {
		int x,y,z;
		cin>>x>>y>>z;
		a[x]+=z,a[y]+=z;
	}
	sort(a+1,a+1+n);
	for(int i=n;i>=1;i-=2)
		ans+=a[i]-a[i-1];
	cout<<ans/2;
	return 0;
}
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

Take Apples

首先，“一眼能看出”

if(m<=n) cout<<"Alice"<<endl;
if(m>n&&(m-n)%(s+1)==0) cout<<"Alice"<<endl;
1
2

考虑当m>n&&(m-n)%(s+1)!=0时，Alice是否有办法用一步变成后手必胜局面。可以斩三堆使得n

Bob必胜态大小为$n$的堆Alice取一个Bob取另一个，大小为$m$的堆Bob取$s+1-$Alice取的数量。
否则Alice能一步变成后手必胜态（$n>s$时同时取3个堆，否则取$m$堆）。

然后这个题目有点坑，输入顺序应该是m,n,s…

#include
using namespace std;

int main()
{
    int s,m,n;
    while(~scanf("%d%d%d",&m,&n,&s))
    {
        if(n<=s&&m%(s+1)==0) cout<<"Bob"<<endl;
        else cout<<"Alice"<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12