calendar game(博弈搜索).cpp

杭电acm解题报告2001---2099.

//模拟也可以过
#include <cstdio>
#include <string>

int t;
int y,m,d;
int days[15] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
char hash[2100][15][35];

bool isleap_year(int y)
{
	if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0) ) {
		return true;
	}
	return false;
}

bool isok(int y,int m,int d)
{
	if (m != 2) {
		if (d > days[m]) {
			return false;
		}
	}
	else {
		int t = days[2];
		if (isleap_year(y)) {
			t ++;
		}
		if (d > t) {
			return false;
		}
	}
	return true;
}

char isend(int y, int m, int d)
{
	if (y == 2001 && m == 11 && d == 4) {//已经是目标状态，再移动就输了
		return 'L';
	}
	if (y == 2001) {
		if (m > 11) {
			return 'W';
		}
		else if (m == 11 && d > 4) {
			return 'W';
		}
	}
	return '#';
}

void next_day(int &y, int &m, int &d)
{
	int t;
	d ++;
	if (m != 2) {
		t = days[m];
	}
	else {
		t = days[2];
		if (isleap_year(y)) {
			t ++;
		}
	}
	if (d > t) {
		d = d % t;
		m ++;
	}
	if (m > 12) {
		y ++;
	}
}

char game(int y, int m, int d)
{
	char now = isend(y,m,d);
	if (now != '#') {
		return now;
	}
	//next month
	int ty = y, tm = m+1, td = d;
	if (tm > 12) {
		tm = 1;
		ty ++;
	}
	if (isok(ty,tm,td)) {
		if (hash[ty][tm][td] == 0) {
			hash[ty][tm][td] = game(ty,tm,td);
		}
		if (hash[ty][tm][td] == 'L') {//输态能推出胜态
			return 'W';
		}
	}
	//next day
	ty = y, tm = m, td = d;
	next_day(ty,tm,td);
	if (hash[ty][tm][td] == 0) {
		hash[ty][tm][td] = game(ty,tm,td);
	}
	if (hash[ty][tm][td] == 'L') {
		return 'W';
	}
	return 'L';
}

int main()
{
	int i,j;
	memset(hash,0,sizeof(hash));
	scanf("%d",&t);
	while (t --) {
		scanf("%d %d %d",&y,&m,&d);
		if (hash[y][m][d] == 0) {
			hash[y][m][d] = game(y,m,d);
		}
		if (hash[y][m][d] == 'L') {
			puts("NO");
		}
		else {
			puts("YES");
		}
	}
}