「NOIP模拟赛」日历游戏

2014年11月2日2,4970

「问题描述」

moreDmoreD的宠物CD正在玩一个日历游戏,开始时,他们从190011日到20121222日(你懂的……)选一个日期开始,依次按照如下规则之一向后跳日期:

  1. 1. 跳到日历上的下一天。
  2. 2. 跳到日历上的下个月的同一天(如果不存在,则不能这么做)。

要是谁正好到达20121222日那么他就赢了,如果到达这天之后的日期那他就输了——原因你也懂的。

每次都是moreD先走的。

现在,给你一个日期,请问moreD一定能赢吗?

「输入」

输入共T行,每行三个整数,Y、M、D,分别表示年、月、日。日期在190011日到20121222日之间(包含两端)。

T并不在输入数据当中。

「输出」

要是moreD一定能赢,输出一行YES,否则输出NO

「输入输出样例一」

calendar.in

calendar.out

2012 12 20

NO

「输入输出样例二」

calendar.in

calendar.out

2012 12 21

YES

「数据描述」

对于50%的数据,是194911日后的日期。 T <= 5

对于100%的数据,是190011日后的日期。T <= 10

题解

对于日期直接的关系是一棵二叉树,然后用记忆化搜索解决

具体可以递推或者用sg函数

为了防止爆栈可以先分成几棵子树处理

 

说点什么

提醒
avatar