坑爹一题

伊甸园日历游戏

【题目描述】
Adam和Eve玩一个游戏，他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作：
1：把日期的天数加1，例如1900.1.1变到1900.1.2；
2：把月份加1，例如：1900.1.1变到1900.2.1。
其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候，如果有这样的日期：1900.1.31，则变成了1900.2.31，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。
谁先将日期变到2001.11.4谁就赢了。
每次游戏都是Adam先操作，问他有没有必胜策略？

【输入格式】
本题仅一个测试点，有多组数据。
第一行为数据组数N。
接下来每一行有3个整数X、Y、Z，表示X年Y月Z日。

【输出格式】
输出“YES”or“NO”（不包括引号），表示亚当是否有必胜策略。

【样例输入】
3
2001 11 3
2001 11 2
2001 10 3

【样例输出】
YES
NO
NO

【注释】
建议先把所有情况都算出来。

【题目来源】
Vijos

题目分析

【关键算法】
记忆化搜索、纯模拟或者数学方法。

【分析】
这里说说博弈论：博弈一个重要的定义：一个状态它的孩子状态全是必胜状态，则它就一定是必败状态。如果有孩子状态有一个为必败状态，则它就是必胜状态了。
2001.11.4是一个必败状态，所以我们可以从2001.11.4递推到1900.1.1，将所有状态的情况都给计算出来，这样读入数据直接写即可。

最后送上某大神写的代码：
[cpp]
#include
using std::cin;
using std::cout;
int n, y, m, d;
int main(void) {
cin >> n;
for (int i = 1; i <= n; ++i) { cin >> y >> m >> d;
if ((d == 30 && (m == 11 || m == 9)) || ((m + d) % 2 == 0)) {
cout << "YES"; } else { cout << "NO"; } cout << endl ; } return 0; } [/cpp]

以下是这个算法的解释（Link）

这是这个算法的解释：伊甸园日历游戏其实是游戏论的内容，这是所谓的平等组合游戏。
什么是“平等组合游戏”？

•  两人游戏。
• 有一个状态集，而且通常是有限的。
• 规定哪些状态转移是允许的。
• 所有规定对于两人来说是一样的。
• 两人轮流走步。
• 有一个终止状态，到达终止状态后游戏即告终止。
• 游戏可以在有限步内终止。

P状态和N状态：
就像第一是刚才走步的人的必胜状态，我们称之为P状态；而1，2，3，5，6，7，……都是下一个走步的人的必胜状态，我们称之为N状态。我们可以从终止状态出发，推出每一个状态，指出它是P状态还是N状态。就拿第一个游戏举例：
步骤一 将所有终止状态设为P状态。
步骤二 将所有一步之内可以到达一个P状态的状态设为N状态。
步骤三 如果一个状态，不管怎么走都只能走到N状态，那么就将这个状态设为P状态。
步骤四 返回步骤二。
如果能够走到P状态，就能获胜。因为安照上面的定义，对手不管如何选择，只可能走到N状态。接下来总存在一个P状态你可以走到。这样一直走到终止状态，你获胜。当然这里所说得都是指对于最后走步的人获胜的游戏。
我们严格的来定义P状态和N状态

• 所有的终止状态都是P状态；
• 对于任何的N状态，肯定存在一种方式可以一步转到一个P状态；
• 对于任何的P状态，不管怎么走步，都只能转到N状态。

而对于最后走步的人失败的游戏，只要将所有终止状态改成N状态，然后开始倒推就可以了。当然，必胜状态是N状态。也就是说，如果想胜利，就希望面对N状态，转移到P状态。
2001.11.4 n
2001.11.3 2001.10.4 p
2001.11.2 2001.10.3 2001.09.4 n
2001.11.1 2001.10.2 2001.09.3 2001.08.4 p
2001.10.31 2001.10.1 2001.09.2 2001.08.3 2001.07.4 n
2001.10.30 2001.09.30 2001.09.1 2001.08.2 2001.07.3 2001.06.4 p
由此看出 当month+day mod 2=0 then p状态
若month=9 day=30 then p状态