+1学姐玩跳棋（SG函数）

+1学姐玩跳棋

Description

拥有复读机buff的+1学姐一路顺利，现在已经来到了最后一个关卡——跳棋大作战，该关卡有三个BOSS，分别是Gevjon，Tyr和Hoder。

战斗规则是，在1*n的棋盘上,从左到右依次标号为1，2，3……n-1，n。跳棋起初放在最左端，即位置1上。+1学姐和BOSS轮流进行一次操作，以一定的规则向右挪动棋子，将棋子恰好挪到最右端，即位置n上的人获胜。不能向左移动，只能在棋盘上移动，不能超出位置n。如果轮到某人移动棋子，但是棋子无法移动，则此人失败，对方获胜。

下面介绍移动规则，三场战斗移动规则不同：

Gevjon：两人轮流将棋子往右移动a格，即如果跳棋的当前位置为i,则这步操作可以将跳棋移至i+a;
Tyr：两人轮流将棋子往右移动1格或b格，即如果跳棋的当前位置为i,则这步操作可以将跳棋移至i+1或i+b;
Hoder：两人轮流将棋子往右移动c格或d格，即如果跳棋的当前位置为i,则这步操作可以将跳棋移至i+c或i+d;

假设+1学姐和三个BOSS都选择了最优策略。

由于BOSS不能主动攻击，所以每一个关卡都是+1学姐先手。

三场战斗独立进行，即这三场战斗跳棋起初都放在位置1上。

三场战斗使用的棋盘大小可能不同，即n可能不同。

现在给出n1，n2，n3，a，b，c，d(n1,n2,n3即三场棋盘的大小，a,b,c,d如上所述)，请判断+1学姐能否通关。三个BOSS都被打败才算通关。

Input

第1行：一个数T，表示有T组样例。（1 <= T <= 10)

第2 - T + 1行：每行7个数n1，n2，n3，a，b，c，d。(1 <= n1,n2 <= 10^9,1<=n3<=1000，1<a,b<=10^9,1<=c,d<=1000)

Output

共T行，如果+1学姐能通关输出“YES”，否则输出“NO”。

Sample Input 1

3
7 11 15 2 6 3 5
7 10 15 2 6 3 5
6 11 18 2 6 3 5

Sample Output 1

YES
NO
NO

Hint

Sample1 解释

第一组样例，+1学姐可以打败所有BOSS，所以输出“YES”。

第二组样例，+1学姐可以打败第一个BOSS Gevjon和第三个BOSS Hoder，但是不能打败第二个BOSS Tyr，所以输出“NO”。

第三组样例，+1学姐可以打败第二个BOSS，不能打败第一个和第三个BOSS，所以输出“NO”。

思路：

第一场：可以看做有n1-1颗石子，每次拿a颗，如果拿奇数次能拿完（或者不能再拿了），那么先手必胜，否则必败

第二场：打表找规律

如果 b 是奇数的话，只需要判断 n2 的奇偶性，n2 为偶数则必胜;
如果 b 是偶数，则 n2 每 b + 1 会出现 0101010 .......... 101011 的循环，所以只需要先将 n2％（b + 1），再判断奇偶性，若为偶数则必胜。

第三场：打表找规律

n3-1每c+d会出现c个0，d个1的循环，所以（n3-1）%（c+d）<c的话就是必败态。

组合游戏不会推就直接sg函数打表找规律吧（打表代码见最下面）

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
	int T,n1,n2,n3,a,b,c,d,k;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d%d%d%d",&n1,&n2,&n3,&a,&b,&c,&d);
		bool flag1=false,flag2=false,flag3=false;
		//1
		k=(n1-1)/a;
		if(k&1) flag1=true; 
		//2
		if((b&1)&&n2%2==0) flag2=true; 
		if(b%2==0&&(n2%(1+b))%2==0) flag2=true;
		//3
		if(c>d) swap(c,d);
		k=(n3-1)%(c+d);
		if(k>=c) flag3=true;
		//总
		//printf("%d%d%d\n",flag1,flag2,flag3);
		if(flag1&&flag2&&flag3) printf("YES\n");
		else printf("NO\n"); 
	}
	return 0;
}

打表里的i是n-1

#include<cstdio>
#include<cstring>
using namespace std;
int sg[100];
int a,b,c,d,n;
void init(){
	memset(sg,-1,sizeof(sg));
}
int Getsg(int x){
	if(sg[x]!=-1) return sg[x];
	if(x==0) return sg[x]=0;
	if(x==c||x==d) return sg[x]=1;
	if(x<c) return sg[x]=0;
	bool book[100];
	memset(book,0,sizeof(book));
	if(x>=d){
		sg[x-c]=Getsg(x-c);
		book[sg[x-c]]=true;
		sg[x-d]=Getsg(x-d);
		book[sg[x-d]]=true;
	}
	if(x>=c&&x<d){
		sg[x-c]=Getsg(x-c);
		book[sg[x-c]]=true;
	}
	for(int i=0;;i++){
		if(!book[i]) return sg[x]=i;
	}
}
int main(){
	scanf("%d%d",&c,&d);
	printf("c = %d , d = %d\n",c,d);
	for(int i=0;i<100;i++){//i是n-1
		init();
		int ans=Getsg(i);
		if(ans!=0) ans=1;//为了好观察，所有的必胜态的sg值都输出1
		printf("%3d  %3d : %3d\n",i,(i+1)%(c+d),ans);
	}
	return  0;
}

+1学姐玩跳棋 （SG函数）

+1学姐玩跳棋（SG函数）