hdu 4559 涂色游戏(SG)

在一个2*N的格子上,Alice和Bob又开始了新游戏之旅。

这些格子中的一些已经被涂过色,Alice和Bob轮流在这些格子里进行涂色操作,使用两种涂色工具,第一种可以涂色任意一个格子,第二种可以涂色任意一个2*2的格子。每一轮游戏里,他们可以选择一种工具来涂色尚未被染色的格子。需要注意,涂色2*2的格子时,4个格子都应当未被涂色。最后一步涂满所有格子的玩家获胜。

一如既往,Alice先手,最优策略,谁是赢家?

在一个2*N的格子上染色 每次可以染1*1的格子 或者2*2的格子 最后涂满所有格子的人胜 m为已染色格子的个数 Alice先手

1*1的点SG值为1 sg【i】表示连续2*i的SG值 sg【3】 就是连续2*3空白格子  最后对整个棋盘分段 分为连续空白的2*i格子 和 某列中涂过色的格子

假如n = 3
在一个已经涂了一个1*1个格子的情况下,有以下子情况: 
情况1 假如是在第1行第1列的那个格子已经被涂了色

整个棋盘可分为:连续0列的格子+第1列剩下的那一个格子+最后连续2列的格子

ans=sg[0]^1^sg[2]

情况2 假如是在第1行第2列的那个格子已经被涂了色

整个棋盘可分为:连续1列的格子+第2列剩下的那一个格子+最后连续1列的格子

ans=sg[1]^1^sg[1]

情况3 假如是在第1行第3列的那个格子已经被涂了色(其实这个同理情况1)

整个棋盘可分为:连续2列的格子+第3列剩下的那一个格子+连续0列的格子

ans=sg[2]^1^sg[0]

 

在一个已经涂一个2*1个格子的情况下  那么有以下几种子情况

情况1 假如是在第1行第1列的那2个格子已经被涂了色

整个棋盘可分为:连续0列的格子+最后连续2列的格子

ans=sg[0]^sg[2]

情况2 假如是在第1行第2列的那2个格子已经被涂了色

整个棋盘可分为:连续1列的格子+最后连续1列的格子

ans=sg[1]^sg[1]

情况3 同理情况1

为什么1*1的SG值为1

它的后继,涂一个格子,然后没有空白格子,后继值也就是sg[0] = 0

取自然数的补集,再从集合里去最小元素,就是1

sg[1]怎么求,他的后继就是涂了一个格子后,剩1个格子。

sg[1]的后继的sg值为1,取补取最小值后,为0,sg[1]=0

sg[2]怎么求,他的后继

后继1:涂了2*2的格子后,后继的sg值为0(sg[0])

后继2:涂1个1*1格子后,剩一个格子和一个2*1,也就是1^s[1]=1

sg[2]的后继的sg值有0,1,取补取最小值后,为2,sg[2]=2

sg[3]怎么求,他的后继

后继1:涂1个1*1格子后,剩一个格子和一个2*2,也就是1^s[2]=3

后继2:涂1个1*1格子后,剩一个格子和2个2*1,也就是1^s[1]^sg[1]=1

后继3:涂1个2*2,剩一个2*1,也就是sg[1]=0

sg[3]的后继的sg值有0,1,3,取补取最小值后,为2,sg[3]=2

sg[4]........

Sample Input
2
2 0 // n m
2 2 //n m
1 1 //已染色格子的坐标
2 2

Sample Output
Case 1: Alice
Case 2: Bob

 # include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# include <queue>
# include <list>
# define LL long long
using namespace std ;
const int MAXN=;
int sg[MAXN];
bool vis[MAXN];
bool g[][MAXN];
int mex(int x)
{
if(sg[x]!=-)return sg[x];
memset(vis,false,sizeof(vis));
for(int i=;i<=x--i;i++) //染1*1
{
int tmp=mex(i)^mex(x--i)^;
vis[tmp]=true;
}
for(int i=;i<=x--i;i++)//染2*2
{
int tmp=mex(i)^mex(x--i);
vis[tmp]=true;
}
for(int i=;;i++)
if(!vis[i])
{
sg[x]=i;
break;
}
return sg[x];
} int main()
{ memset(sg,-,sizeof(sg));
sg[]=;
for(int i=;i<;i++)
sg[i]=mex(i);
int T;
scanf("%d",&T);
int iCase=;
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(g,false,sizeof(g));
int u,v;
while(m--)
{
scanf("%d%d",&u,&v);
u--;v--;
g[u][v]=true;
}
int len=;
int ans=;
for(int i=;i<n;i++)
{
if(g[][i]||g[][i])
{
ans^=sg[len];
len=;
if(g[][i]&&g[][i])continue;
ans^=;
}
else len++;
}
ans^=sg[len];
iCase++;
if(ans)printf("Case %d: Alice\n",iCase);
else printf("Case %d: Bob\n",iCase);
}
return ;
}
上一篇:LeetCode Solutions : Reorder List


下一篇:hdu 4559 涂色游戏(对SG函数的深入理解,推导打SG表)