现在的位置: 首页 > 综合 > 正文

HDOJ 1851 A Simple Game 博弈 SG函数中找规律

2014年01月02日 ⁄ 综合 ⁄ 共 498字 ⁄ 字号 评论关闭
//HDOJ 1851 A Simple Game SG函数中找规律

/*
题意:有n堆石子,每堆分别有m1,m2,m3...个
	  每堆每次最多能取走最多l1,l2,l3...个,最少去一个

      问后手的胜负态

思路:用sg(n,k)表示剩余n个的一堆石子中 每次最多能取走k个
	  则有
	  sg(0,1)=0  sg(0,2)=0  sg(0.3)=0  ...
	  sg(1,1)=1  sg(1.2)=1  sg(1,3)=1  ...
	  sg(2,1)=0  sg(2,2)=2  sg(2,3)=2  ...
	  sg(3,1)=1  sg(3,2)=0  sg(3,3)=3  ...
	  ...        ...        ...

	  则可以从sg函数中发现规律,注意题目求的是后手的胜负态
*/

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

int T,n,m,k;

int main(){
	int i,ans;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&m);
		ans = 0;
		for(i = 1; i <= m; ++i){
			scanf("%d %d",&n,&k);
			ans ^= n%(k+1);
		}
		puts(ans?"No":"Yes");
	}
	return 0;
}

抱歉!评论已关闭.