首页 > ACM题库 > HDU-杭电 > HDU 4559-涂色游戏[解题报告]HOJ
2015
07-25

HDU 4559-涂色游戏[解题报告]HOJ

涂色游戏

问题描述 :

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

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

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

输入:

输入第一行为T,表示有T组测试数据。
每组数据包含两个数字,N与M,M表示有多少个已被染色的格子。接下来的M行每行有两个数字Xi与Yi,表示已经被涂色的格子坐标。

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N <= 4747
3. 0 <= M <= 2 * N
4. 1 <= Xi <= 2, 1 <= Yi <= N,格子坐标不会重复出现

输出:

输入第一行为T,表示有T组测试数据。
每组数据包含两个数字,N与M,M表示有多少个已被染色的格子。接下来的M行每行有两个数字Xi与Yi,表示已经被涂色的格子坐标。

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N <= 4747
3. 0 <= M <= 2 * N
4. 1 <= Xi <= 2, 1 <= Yi <= N,格子坐标不会重复出现

样例输入:

2
2 0
2 2
1 1
2 2

样例输出:

Case 1: Alice
Case 2: Bob

/*

http://hi.baidu.com/chenwenwen0210/item/00cb739a43e8516bf14215eb


http://www.cnblogs.com/kuangbin/archive/2013/05/24/3097767.html

  */

#include<cstdio>
#include<cstring>

const int maxn=5000;
int SG[maxn];
int n,m;
bool vis[maxn];
bool map[2][maxn];

int Gao(int tot){
	int i,j,k;
	if(SG[tot]!=-1)return SG[tot]; 
	memset(vis,0,sizeof(vis));
	for(i=0;i<=tot-i-1;i++){
		k=Gao(i)^Gao(tot-i-1)^1;
		vis[k]=1;
	}
	for(i=0;i<=tot-i-2;i++){
		k=Gao(i)^Gao(tot-i-2);
		vis[k]=1;
	}
	for(i=0;i<maxn;i++)
		if(!vis[i]){
			SG[tot]=i;
			break;
		}
	return SG[tot];
}

void Init(){
	memset(SG,-1,sizeof(SG));
	for(int i=1;i<maxn;i++)
		SG[i]=Gao(i);
}

int main(){
	int i,j,T,x,y;
	Init();
	int cas;
	scanf("%d",&T);
	for(int cas=1;cas<=T;cas++){
		memset(map,0,sizeof(map));
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++){
			scanf("%d%d",&x,&y);
			x--;y--;
			map[x][y]++;
		}
		int ans=0;
		int len=0;
		for(i=0;i<n;i++){
			if(map[0][i] ||map[1][i]){
				ans^=SG[len];
				len=0;
				if(map[0][i] && map[1][i])
					continue;
				ans^=1;
			}else{
				len++;
			}
		}
		ans^=SG[len];
		if(ans)printf("Case %d: Alice\n",cas);
		else printf("Case %d: Bob\n",cas);
	}
	return 0;
}

参考:http://blog.csdn.net/sunyuntaoyukar/article/details/9569281