学步园

tyvj 1968：

我的方法，将SG值打出来，然后就可以看到规律。

具体的想法可以看------>点击打开链接

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

int sg[15][35];
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int getsg(int x, int y)
{
	if(sg[x][y] != -1)
		return sg[x][y];
	bool vis[100];
	memset(vis, 0, sizeof(vis));
	
	if(x < 10 || x == 10 && y <= 4)
		vis[getsg(x + 1, y)] = 1;
	if(y != day[x] && x != 12)
		vis[getsg(x, y + 1)] = 1;
	else
		vis[getsg(x + 1, 1)] = 1;
		
	int i;
	for(i = 0; i < 100; i++)
		if(vis[i] == 0)
			break;
	return sg[x][y] = i;
}

int getsg1(int x, int y)
{
	if(sg[x][y] != -1)
		return sg[x][y];
	bool vis[100];
	memset(vis, 0, sizeof(vis));
	if(x == 12)
	{
		if(y != 31)
			vis[getsg(x, y + 1)] = 1;
		else
			vis[getsg(1, 1)] = 1;
		vis[getsg(1, y)] = 1;
	}
	
	if(x == 11)
	{
		if(y != 30)
			vis[getsg(x, y + 1)] = 1;
		else
			vis[getsg(x + 1, 1)] = 1;
		vis[getsg(x + 1, y)] = 1;
	}
	int i;
	for(i = 0; i < 100; i++)
		if(vis[i] == 0)
			break;
	return sg[x][y] = i;
}


int main (void)
{
	memset(sg, -1, sizeof(sg));
	sg[11][4] = 0;
	sg[11][3] = 1;
	sg[11][2] = 0;
	sg[11][1] = 1;
	int i, j;
	for(i = 10; i > 0; i--)
		for(j = day[i]; j > 0; j--)
			getsg(i, j);

	for(i = day[12]; i > 0; i--)
		getsg1(12, i);
	for(i = day[11]; i >= 5; i--)	
		getsg1(11, i);
			
	for(i = 1; i <= 12; i++)
	{
		printf("%d: ", i);
		for(j = 1; j <= day[i]; j++)
		{
			if(sg[i][j] != 0)
				printf("1 ");
			else
				printf("0 ");
		}
		printf("\n");
	}
	return 0;
	
}

打表结果：

1: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
2: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
3: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
4: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
5: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
6: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
7: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
8: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
9: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
10: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
11: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
12: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

#include <stdio.h>

int main (void)
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int y, m, d;
		scanf("%d %d %d", &y, &m, &d);
		if((m + d) % 2 == 0)
				printf("YES\n");
		else
		{
			if((m == 11 || m == 9) && d == 30)
				printf("YES\n");
			else	
				printf("NO\n");
		}
	}
	return 0;
}

tyvj 1140：

用到了德巴赫猜想：

1.每个不小于6的偶数都可以表示为两个奇素数之和
2.每个不小于9的奇数都可以表示为三个奇素数之和

所以只要输入的是一个偶数，那么它可以通过2步完成，输入的是一个奇数，那么需要3步完成。
但是，有一些需要注意的地方：
1 如果这个数本身就是质数或者1，那么只需要一步
2 如果一个数减去2以后是质数，那么它也只需要2步（只有奇数才会执行）

#include <stdio.h>
#include <limits>

int isprime(int x)
{
	int i;
	for(i = 2; i * i <= x; i++)
		if(x % i == 0)
			return 0;
	return 1;
}


int get(int x)
{
	if(x <= 2)
		return 1;
	if(isprime(x))//是素数 
		return 1;
	if(x % 2 == 0)//偶数 
		return 2;
	if(isprime(x - 2))//奇数减2是素数 
		return 2;
	return 3;//奇数 
}

int main (void)
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int a, b, c, d;
		scanf("%d %d", &a, &b);
		c = get(a);
		d = get(b);
		if(a > b)
		{
			if(c <= d)
				printf("YES\n");
			else
				printf("NO\n");
		}
		else
		{
			if(c < d)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
	return 0;
}