HDU 1079 Calendar Game （日期博弈，真是日歷都快被我走遍了...）
[導(dǎo)讀]題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1079
題面：
Calendar Game
Time Limit: 5000/1000 MS (Ja
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1079
題面：
Calendar Game Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3240????Accepted Submission(s): 1903
Problem Description Adam and Eve enter this year’s ACM International Collegiate Programming Contest. Last night, they played the Calendar Game, in celebration of this contest. This game consists of the dates from January 1, 1900 to November 4, 2001, the contest day. The game starts by randomly choosing a date from this interval. Then, the players, Adam and Eve, make moves in their turn with Adam moving first: Adam, Eve, Adam, Eve, etc. There is only one rule for moves and it is simple: from a current date, a player in his/her turn can move either to the next calendar date or the same day of the next month. When the next month does not have the same day, the player moves only to the next calendar date. For example, from December 19, 1924, you can move either to December 20, 1924, the next calendar date, or January 19, 1925, the same day of the next month. From January 31 2001, however, you can move only to February 1, 2001, because February 31, 2001 is invalid.
A player wins the game when he/she exactly reaches the date of November 4, 2001. If a player moves to a date after November 4, 2001, he/she looses the game.
Write a program that decides whether, given an initial date, Adam, the first mover, has a winning strategy.
For this game, you need to identify leap years, where February has 29 days. In the Gregorian calendar, leap years occur in years exactly divisible by four. So, 1993, 1994, and 1995 are not leap years, while 1992 and 1996 are leap years. Additionally, the years ending with 00 are leap years only if they are divisible by 400. So, 1700, 1800, 1900, 2100, and 2200 are not leap years, while 1600, 2000, and 2400 are leap years.
?
Input The input consists of T test cases. The number of test cases (T) is given in the first line of the input. Each test case is written in a line and corresponds to an initial date. The three integers in a line, YYYY MM DD, represent the date of the DD-th day of MM-th month in the year of YYYY. Remember that initial dates are randomly chosen from the interval between January 1, 1900 and November 4, 2001.
?
Output Print exactly one line for each test case. The line should contain the answer "YES" or "NO" to the question of whether Adam has a winning strategy against Eve. Since we have T test cases, your program should output totally T lines of "YES" or "NO".
?
Sample Input 3 2001 11 3 2001 11 2 2001 10 3 ?
Sample Output YES NO NO ? 題目大意：
??? 給定一個(gè)初始日期，對于當(dāng)前日期，A，B輪流操作。操作方式有兩種，以天數(shù)為單位后移一天，或者以月為單位，后移一月，但如果后面那個(gè)月份沒有對應(yīng)的天，那么就不能進(jìn)行月移操作。若剛好移到指定日期者獲勝。
解題：
??? 拋開日期操作不說，這是一道很簡單的博弈問題，但由于結(jié)合了日期操作，所以處理較繁瑣。博弈策略是這樣的，對于一個(gè)日期，如果能夠通過日移操作或月移操作達(dá)到一個(gè)必?cái)B(tài)，那么該狀態(tài)就為勝態(tài)，否則就為必?cái)B(tài)。也就是去檢驗(yàn)后一個(gè)月，和后一天的狀態(tài)。這道題的亮點(diǎn)在于，出了任何小差錯(cuò)，就可能導(dǎo)致不能AC。
提升版：
???
ZJUT 1587
代碼：
#include
#include
#include
#include
#include
#define eps 1e-7
using namespace std;
struct date
{
int y,m,d;
};
//日期狀態(tài)
bool status[2016][13][32],flag,sign;
//每月天數(shù)
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//日移操作
date next_day(int y,int m,int d)
{
date tmp;
//如果是12月份，可能會換年，需特殊處理
if(m==12)
{
if(d==31)
tmp.y=y+1,tmp.m=1,tmp.d=1;
else
tmp.y=y,tmp.m=12,tmp.d=d+1;
}
//如果不是2月，一般處理
else if(m!=2)
{
//看是不是該月最后一天，可能會換月，需特殊處理
if(d==month[m])
tmp.y=y,tmp.m=m+1,tmp.d=1;
else
tmp.y=y,tmp.m=m,tmp.d=d+1;
}
//如果是2月，需要看是不是閏年
else
{
if(y%400==0||(y%4==0&&y%100!=0))
{
if(d==29)
tmp.y=y,tmp.m=3,tmp.d=1;
else
tmp.y=y,tmp.m=2,tmp.d=d+1;
}
else
{
if(d==28)
tmp.y=y,tmp.m=3,tmp.d=1;
else
tmp.y=y,tmp.m=2,tmp.d=d+1;
}
}
return tmp;
}
//月移操作
date next_month(int y,int m,int d)
{
date tmp;
//flag為月移是否合法標(biāo)志
flag=true;
//特判12月，可能會跨年
if(m==12)
tmp.y=y+1,tmp.m=1,tmp.d=d;
//特判1、2月
else if((m!=2)&&(m!=1))
{
//到達(dá)月末，換月
if(d>month[m+1])
flag=false;
else
tmp.y=y,tmp.m=m+1,tmp.d=d;
}
//1月，因?yàn)楹笠频?月，要看2月是否在閏年
else if(m==1)
{
if((y%4==0&&y%100!=0)||(y%400==0))
{
if(d>29)
flag=false;
else
tmp.y=y,tmp.m=2,tmp.d=d;
}
else
{
if(d>28)
flag=false;
else
tmp.y=y,tmp.m=2,tmp.d=d;
}
}
//2月最多29天，對于3月都是可以的
else
tmp.y=y,tmp.m=m+1,tmp.d=d;
return tmp;
}
//年移操作，此題不需要
date next_year(int y,int m,int d)
{
//sign為年移是否合法標(biāo)志
sign=true;
date tmp;
//只有2月29號是特殊的
if(m==2&&d==29)
sign=false;
else
tmp.y=y+1,tmp.m=m,tmp.d=d;
return tmp;
}
int main()
{
date tmp,tmp2;
//標(biāo)記11.1-11.4號
for(int i=1;i<=4;i++)
{
if(i%2)
status[2001][11][i]=0;
else
status[2001][11][i]=1;
}
if(status[2001][11][1])
status[2001][10][31]=0;
else
status[2001][10][31]=1;
//10.5-10.30只能日移，不能月移
for(int i=30;i>=5;i--)
{
tmp=next_day(2001,10,i);
//如果后一天是必?cái)B(tài)，那么當(dāng)前就是勝態(tài)
if(status[tmp.y][tmp.m][tmp.d])
status[2001][10][i]=0;
else
status[2001][10][i]=1;
}
//10.1-10.4既可月移也可日移
for(int i=4;i>=1;i--)
{
tmp=next_day(2001,10,i);
tmp2=next_month(2001,10,i);
//如果月移或日移到必?cái)B(tài)，那么當(dāng)前為勝態(tài)，否則為必?cái)B(tài)
if(status[tmp.y][tmp.m][tmp.d]||status[tmp2.y][tmp2.m][tmp2.d])
status[2001][10][i]=0;
else
status[2001][10][i]=1;
}
//2001.1-2001.9既可月移又可日移
for(int i=9;i>=1;i--)
{
for(int j=month[i];j>=1;j--)
{
tmp=next_day(2001,i,j);
if(status[tmp.y][tmp.m][tmp.d])
status[2001][i][j]=0;
else
{
tmp=next_month(2001,i,j);
if(flag)
{
if(status[tmp.y][tmp.m][tmp.d])
status[2001][i][j]=0;
else
status[2001][i][j]=1;
}
else
status[2001][i][j]=1;
}
}
}
//1900-2000，即可月移又可日移
for(int i=2000;i>=1900;i--)
{
for(int j=12;j>=1;j--)
{
int k;
if(j==2&&(i%4==0&&i%100!=0)||(i%400==0))
k=29;
else
k=month[j];
for(;k>=1;k--)
{
tmp=next_day(i,j,k);
if(status[tmp.y][tmp.m][tmp.d])
status[i][j][k]=0;
else
{
tmp=next_month(i,j,k);
if(flag)
{
if(status[tmp.y][tmp.m][tmp.d])
status[i][j][k]=0;
else
status[i][j][k]=1;
}
else
status[i][j][k]=1;
}
}
}
}
//輸入輸出
int yy,mm,dd,T;
cin>>T;
while(T--)
{
cin>>yy>>mm>>dd;
if(status[yy][mm][dd])
cout<<"NOn";
else
cout<<"YESn";
}
return 0;
} 
下載文檔
