日历游戏(博弈论，记忆化搜索)
2 、 日历游戏 （ calendar ,1s, 128 MB ）
问题描述:
moreD 和 moreD 的宠物 CD 正在玩一个日历游戏，开始时，他们从 1900 年 1 月 1 日到 2012
年 12 月 22 日选一个日期开始，依次按照如下规则之一向后跳日期：
1. 跳到日历上的下一天。
2. 跳到日历上的下个月的同一天（如果不存在，则不能这么做）。
要是谁正好到达 2012 年 12 月 22 日那么他就赢了，如果到达这天之后的日期那他就输了
——原因你也懂的。
每次都是 moreD 先走的。
输入 描述: :
输入共 T 行，每行三个整数，Y、M、D，分别表示年、月、日。日期在 1900 年 1 月 1 日到
2012 年 12 月 22 日之间（包含两端）。
输出 描述: :
输入输出样例 1 1
calendar.in
输入输出样例 2 2
calendar.in
数据描述 ：
对于 50%的数据，是 1949 年 1 月 1 日后的日期。 T <= 5；
问题描述:
moreD 和 moreD 的宠物 CD 正在玩一个日历游戏，开始时，他们从 1900 年 1 月 1 日到 2012
年 12 月 22 日选一个日期开始，依次按照如下规则之一向后跳日期：
1. 跳到日历上的下一天。
2. 跳到日历上的下个月的同一天（如果不存在，则不能这么做）。
要是谁正好到达 2012 年 12 月 22 日那么他就赢了，如果到达这天之后的日期那他就输了
——原因你也懂的。
每次都是 moreD 先走的。
现在，给你一个日期，请问 moreD 一定能赢吗？
输入共 T 行，每行三个整数，Y、M、D，分别表示年、月、日。日期在 1900 年 1 月 1 日到
2012 年 12 月 22 日之间（包含两端）。
T 并不在输入数据当中。
要是 moreD 一定能赢，输出一行 YES，否则输出 NO。
calendar.in
2012 12 20
calendar.out
NO
calendar.in
2012 12 21
calendar.out
YES
对于 50%的数据，是 1949 年 1 月 1 日后的日期。 T <= 5；
对于 100%的数据，是 1900 年 1 月 1 日后的日期。T <= 10。
/*
考虑闰年的 2 月？？？
4年一闰，百年不闰，4百年又闰
*/
#include<bits/stdc++.h>
using namespace std;
int T[3000][15];//这个年，月有多少天
void init()
{
for(int i=1900;i<=2020;i++)//打表ing
for(int j=1;j<=12;j++)
{
if(j==1)
T[i][j]=31;
else if(j==2)
T[i][j]=i%4==0?29:28;
else if(j==3)
T[i][j]=31;
else if(j==4)
T[i][j]=30;
else if(j==5)
T[i][j]=31;
else if(j==6)
T[i][j]=30;
else if(j==7)
T[i][j]=31;
else if(j==8)
T[i][j]=31;
else if(j==9)
T[i][j]=30;
else if(j==10)
T[i][j]=31;
else if(j==11)
T[i][j]=30;
else if(j==12)
T[i][j]=31;
}
}
struct oppo{
int n,y,r;
}st;
oppo find_r(oppo rq)//寻找下一天
{
rq.r++;
if(rq.r>T[rq.n][rq.y])
{
rq.r=1;
rq.y++;
}
if(rq.y>12)
{
rq.n++;
rq.y=1;
}
return rq;
}
oppo find_y(oppo rq)//寻找下一个月的同一天
{
rq.y++;
if(rq.y>12)
{
rq.n++;
rq.y=1;
}
if(rq.r>T[rq.n][rq.y])
rq.n=rq.y=rq.r=0;
return rq;
}
bool pd(oppo rq)//判断是否超过日期
{
if(rq.n>2012)
return 1;
if(rq.n==2012&&rq.y==12&&rq.r>22)
return 1;
return 0;
}
int jyh[3000][15][40];
bool dfs(oppo rq)
{
if(jyh[rq.n][rq.y][rq.r]!=-1)
return jyh[rq.n][rq.y][rq.r];
if(rq.n==2012&&rq.y==12&&rq.r==22)
return jyh[rq.n][rq.y][rq.r]=0;
if(pd(rq))
return jyh[rq.n][rq.y][rq.r]=1;
oppo to;
to=find_y(rq);
if(to.n&&to.y&&to.r)
if(dfs(to)==0)
return jyh[rq.n][rq.y][rq.r]=1;
to=find_r(rq);
if(dfs(to)==0)
return jyh[rq.n][rq.y][rq.r]=1;
return 0;
}
int n,y,r;
int main()
{
freopen("calendar.in","r",stdin);
freopen("calendar.out","w",stdout);
memset(jyh,-1,sizeof(jyh));
init();
while(cin>>n>>y>>r)
{
st.n=n;
st.y=y;
st.r=r;
if(dfs(st))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
} 
投递荣耀终端等公司7个岗位 >