学步园

Description

Input

Output

Sample Input

3 
2001 11 3 
2001 11 2 
2001 10 3 

Sample Output

YES
NO
NO

#include <iostream>
using namespace std;

struct Date
{
	int y,m,d;
}date;

bool state[102][13][32];
bool leapFlag;
int month[]={31,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leapYear(int y)   //是否为闰年
{
	if(y%4==0)
	{
		if(y%400!=0)return false;
		return true;
	}
	return false;
}

bool getDayBefore()      //获取前一天的日期
{
	bool loopFlag=true;
	if(date.d>1){date.d--;return loopFlag;}
	if(date.m==3)
	{
		date.m--;
		if(leapFlag) date.d=29;
		else date.d=28;
	}else if(date.m==1)
	{
		date.y--;
		date.m=12;
		date.d=month[12];
		loopFlag=false;
	}else
	{
		date.m--;
		date.d=month[date.m];
	}
	return loopFlag;
}

bool isValidNextMonth()  //判断下个月的这天是否有效
{
	if(date.y>=101 && ((date.m==10 && date.d>4)||(date.m>10)))return false;
	if(date.d<=month[(date.m+1)%12])return true;                //将month[0]=31 便可用 %12
	if(leapFlag && date.m==1 && date.d<30)return true;
	return false;
}

void init()
{
	memset(state,0,102*13*32);
	date.y=101;
	date.m=11;
	date.d=3;
	Date time={101,11,4};
	bool loopFlag;
	while(date.y>=0)
	{
		leapFlag=is_leapYear(date.y+1900);
		loopFlag=true;
		while(loopFlag)
		{
			if(!state[time.y][time.m][time.d])
			{
				state[date.y][date.m][date.d]=true;
			}else
			{
				if(isValidNextMonth())
				{
					if(date.m==12)
					{
						if(!state[date.y+1][1][date.d])state[date.y][date.m][date.d]=true;
					}else if(!state[date.y][date.m+1][date.d])state[date.y][date.m][date.d]=true;
				}
			}
			time=date;
			loopFlag=getDayBefore();
		}
	}
}

int main()
{
	freopen("in.txt","r",stdin);
	int i,n;
	int y,m,d;
	cin>>n;
	init();
	for(i=0;i<n;i++)
	{
		cin>>y>>m>>d;
		if(state[y-1900][m][d])cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

网上还有一种超简单的方法，分析：2种操作，日+1，或月+1，（除了几个特殊日期外）均能改变月+日的奇偶性，    而目标11.4，月+日为奇数，所以只要起始日期的月+日为偶数,Adam,the first mover,就可能赢。而两个特殊日期（9.30，11.30），尽管月+日为奇数，但下一步仍然可以得到奇数。

#include <iostream>
using namespace std;

bool win(int m,int d)
{
	if((m+d)%2==0)return true;
	if(d==30 && (m==9 ||m==11))return true;
	return false;
}

int main()
{
	freopen("in.txt","r",stdin);
	int i,n;
	int y,m,d;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>y>>m>>d;
		if(win(m,d))cout<<"YES"<<endl;
		else  cout<<"NO"<<endl;
	}
	return 0;
}

我将两者得到的结果进行对比，

	for(i=0;i<102;i++)
	{
		for(j=1;j<13;j++)
		{
			for(z=1;z<=month[j];z++)
			{
				if(win(j,z)!=state[i][j][z])
				{
					cout<<"不一致！ "<<i+1900<<"-"<<j<<"-"<<z<<endl;
				//	system("PAUSE");
				}
			}
		}
	}

发现对于1990-1-1到2001-11-4的所有日期的胜败情况确实是完全一致的。