POJ_1082
最近没学英语了，一开始把November当成了12月，囧了。
这个题目想象成一开始在(yy,mm,dd)这个点有一个棋子，每人然后可以沿合法的位置移动一步，最后当棋子到达(2001,11,4)这个点时就算游戏结束。这样就把这个问题化归到有向无环图上的游戏了，于是用SG函数就可以解决了。
另外推荐一个讲SG函数入门知识的博客：http://www.cnblogs.com/Knuth/archive/2009/09/05/1561007.html。
#include<stdio.h>
#include<string.h>
#define Y 1900
int mdays[][15] = {{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
int sg[110][15][35];
void prepare()
{
memset(sg, -1, sizeof(sg));
sg[101][11][4] = 0;
}
int isleap(int yy)
{
return yy % 400 == 0 || (yy % 4 == 0 && yy % 100 != 0);
}
int getnextd(int yy, int mm, int dd, int &nexty, int &nextm, int &nextd)
{
int i, j, k, t1, t2;
if(yy == 2001 && mm == 11 && dd == 4)
return 0;
t1 = isleap(yy);
if(mm == 12 && dd == 31)
nexty = yy + 1, nextm = 1, nextd = 1;
else if(dd == mdays[t1][mm])
nexty = yy, nextm = mm + 1, nextd = 1;
else
nexty = yy, nextm = mm, nextd = dd + 1;
return 1;
}
int getnextm(int yy, int mm, int dd, int &nexty, int &nextm, int &nextd)
{
int i, j, k, t1, t2;
if(yy == 2001 && mm == 11)
return 0;
t1 = isleap(yy);
if(yy == 2001 && mm == 10 && dd > 4)
return 0;
if(mm == 12)
nexty = yy + 1, nextm = 1, nextd = dd;
else
{
nexty = yy, nextm = mm + 1, nextd = dd;
if(nextd > mdays[t1][nextm])
return 0;
}
return 1;
}
int dp(int yy, int mm, int dd)
{
if(sg[yy - Y][mm][dd] != -1)
return sg[yy - Y][mm][dd];
int i, j, k, nexty, nextm, nextd, h[5];
memset(h, 0, sizeof(h));
if(getnextd(yy, mm, dd, nexty, nextm, nextd))
h[dp(nexty, nextm, nextd)] = 1;
if(getnextm(yy, mm, dd, nexty, nextm, nextd))
h[dp(nexty, nextm, nextd)] = 1;
for(i = 0; h[i]; i ++);
return sg[yy - Y][mm][dd] = i;
}
void solve()
{
int i, j, k, yy, dd, mm;
scanf("%d%d%d", &yy, &mm, &dd);
if(dp(yy, mm, dd) == 0)
printf("NO\n");
else
printf("YES\n");
}
int main()
{
int t;
prepare();
scanf("%d", &t);
while(t --)
{
solve();
}
return 0;
}