POJ_1082

    最近没学英语了，一开始把November当成了12月，囧了。

    这个题目想象成一开始在(yy,mm,dd)这个点有一个棋子，每人然后可以沿合法的位置移动一步，最后当棋子到达(2001,11,4)这个点时就算游戏结束。这样就把这个问题化归到有向无环图上的游戏了，于是用SG函数就可以解决了。

    另外推荐一个讲SG函数入门知识的博客：。

#include
     
       #include
      
        #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; }