`
lovnet
  • 浏览: 6670333 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

HDOJ 3389 Game (博弈:Staircase Nim)

 
阅读更多
//3389 Game (Staircase Nim)
/*
题意:有n个盒子编号为1-n,每个盒子里面有若干物品
	  当编号满足a>b && (a+b)%3==0 && (a+b)%2==1时
	  可以从a盒子中拿>=1个物品到b盒子中

思路:找规律后转换为Staircase Nim
	  满足此条件:(a+b)%3==0 && (a+b)%2==1的即是3个倍数并且是奇数:3、9、15、21,即%6==3
	  每六个拆开后会发现如下3组可以传递的关系:
	  1<--2<--7<--8<--13<--14
	  3<--6<--9<--12<--15<--18
	  4<--5<--10<--11<--16<--17
	  即3组Staircase Nim,3组结果异或即可。
*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 10005

int T,n;
int num[N];

int main(){
	int i,j,ca = 1;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(i = 1; i <= n; ++i)
			scanf("%d",&num[i]);
		int sg1 = 0,sg2 = 0,sg3 = 0,sg = 0;
		for(i = 2; i <= n; i += 6)
			sg1 ^= num[i];
		for(i = 6; i <= n; i += 6)
			sg2 ^= num[i];
		for(i = 5; i <= n; i += 6)
			sg3 ^= num[i];
		sg = sg1^sg2^sg3;
		printf("Case %d: ",ca++);
		puts(sg?"Alice":"Bob");

	}
	return 0;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics