描述
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先操作，问他有没有必胜策略？
题目链接
输入格式
一个测试点。多组数据。
第一行为数据组数。
接下来一行X Y Z表示X年Y月Z日
输出格式
输出“YES”or“NO”表示亚当是否有必胜策略。
样例输入
3
2001 11 3
2001 11 2
2001 10 3
样例输出
YES
NO
NO
提示
建议先把所有情况都算出来^_^
题目分析
动态规划（记忆化搜索）
首先，我们将某一天存在必胜策略称为这一天必胜。
对于某一天 X ，下一步有两种情况，月份加一或者日期加一。如果下一步的两种情况都是必胜的，那么 X 不必胜，因为无论转移到哪种情况，对手都是有必胜的策略的；如果两种情况至少有一种是不必胜的，那么 X 必胜，因为可以转移到不必胜的情况，让对手失败。
当然，如果月份加一是不合法的，下一步就只能令日期加一。这时，如果日期加一必胜，则 X 不必胜；反之则 X 必胜。
X 是否必胜，取决于 X+1 天和 X+1 月是否必胜。
因此，只要从 2001.11.4 往前推，将所有日期的答案都计算出来即可。临界条件是：2001.11.4 是必败的；大于 2001.11.4 的日期都是必胜的，因为谁先转移到超过 2001.11.4 的日期谁就失败，相当于谁当前是大于 2001.11.4 的日期，谁就必胜。
找规律
设年 x，月 y，日 z
当 (y+z)%2 == 0 时，必胜；反之必败。
特殊情况：9月30日和11月30日，必胜。
对于这个规律，网上很多大牛进行了分析。不过我并没看懂。
或许是我太菜了。
当然，先按照上一种方法计算所有答案，然后输出，也能找出这个规律。
题目本意应该就是让记忆化搜索。
AC代码1
#include <bits/stdc++.h>
using namespace std;
int ans[3000][13][32] = {0};
int num[] = {31, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //每月的天数，0月份和12月份一样，方便程序
int x2, y2, z2;
void convert(int x, int y, int z) //将xyz转化成正常的年月日并保存在变量x2 y2 z2中
{
x2 = x, y2 = y, z2 = z;
if (z2 == 0) //日期减一的情况
{
if (!(((x2 % 4 == 0 && x2 % 100 != 0) || (x2 % 400 == 0)) && y2 == 3 && z2 == 0)) //不是闰年3月0日
{
y2 = y2 - 1;
if (y2 == 0)
{
x2--;
y2 = 12;
}
z2 = num[y2];
}
else
{
y2 = 2;
z2 = 29;
}
}
if (!(((x2 % 4 == 0 && x2 % 100 != 0) || (x2 % 400 == 0)) && y2 == 2 && z2 == 29)) //不是闰年2月29日
{
if (z2 > num[y2])
{
y2 = y2 + 1;
z2 = 1;
}
}
if (y2 == 13)
{
y2 = 1;
x2 = x2 + 1;
}
}
int f(int x, int y, int z) //返回是否必胜，1为必胜，-1为不必胜
{
if (x > 2001 || (x == 2001 && y > 11) || (x == 2001 && y == 11 && z > 4)) //超过 2001.11.4 则返回1，因为谁先出界谁就输
return 1;
if (x == 2001 && y == 11 && z == 4)
return -1;
int t1, t2; //两种转换的结果
//日期加一
convert(x, y, z + 1);
t1 = ans[x2][y2][z2];
//月份加一，不能用convert函数，因为不是每个月份加1都是合法的
y++;
if (y == 13)
{
x++;
y = 1;
}
x2 = x, y2 = y, z2 = z;
t2 = ans[x2][y2][z2]; //如果日期不合法则t2=0
if (t1 == 1 && t2 == 1)
return -1;
if (t1 == 1 && t2 == 0) // t2等于0且t1==1，此时日期是不合法的。
return -1;
return 1;
}
int main()
{
int t, x, y, z;
x = 2001, y = 12, z = 4; //从2001年12月开始搜索，而不是2001年
while (!(x == 1899 && y == 12 && z == 31))
{
ans[x][y][z] = f(x, y, z);
convert(x, y, z - 1); //日期减一
x = x2, y = y2, z = z2;
}
cin >> t;
while (t--)
{
cin >> x >> y >> z;
if (ans[x][y][z] == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
AC代码2
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int x, y, z;
cin >> x >> y >> z;
if ((y == 9 && z == 30) || (y == 11 && z == 30))//特殊情况
cout << "YES" << endl;
else if ((y + z) % 2 == 0)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}