博弈

1、Calendar Game HDU - 1079

　　题意：两个游戏，Adam先手，每次将当前日期+1天或+1个月份（前提是加完后日期有效），谁先走到2001.11.4谁赢。现在给出一个起始日期（在1900.1.1~2001.11.4之间），问Adam能否赢。

　　思路：从最后一天2001.11.4向前枚举，确定必胜态和必败态。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 const int maxy = 2001;
  6 const int maxm = 13;
  7 const int maxd = 32;
  8 int days[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
  9 bool win[maxy][maxm][maxd];
 10 int cur_y = 2001, cur_m = 11, cur_d = 4;
 11 bool isLeap(int year=cur_y)
 12 {
 13     if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) return true;
 14     else return false;
 15 }
 16 void sub()
 17 {
 18     cur_d--;
 19     if (cur_d == 0)
 20     {
 21         cur_m--;
 22         if (cur_m) cur_d = days[cur_m];
 23         else
 24         {
 25             cur_m = 12;
 26             cur_y--;
 27             if (isLeap()) days[2] = 29;
 28             else days[2] = 28;
 29             cur_d = days[cur_m];
 30         }
 31     }
 32 }
 33 bool can_nextM()
 34 {
 35     int ty = cur_y, tm = cur_m;
 36     tm++;
 37     if (tm > 12) ty++, tm = 1;
 38     if (ty > 2001) return false;
 39     else if (ty == 2001)
 40     {
 41         if (tm > 11 || (tm == 11 && cur_d > 4)) return false;
 42         else if (tm == 11 && cur_d <= 4) return true;
 43         else
 44         {
 45             if (tm != 2)
 46             {
 47                 if (cur_d > days[tm]) return false;
 48                 else return true;
 49             }
 50             else
 51             {
 52                 int max_td = (isLeap(ty) ? 29 : 28);
 53                 if (cur_d > max_td) return false;
 54                 else return true;
 55             }
 56         }
 57     }
 58     else
 59     {
 60         if (tm != 2)
 61         {
 62             if (cur_d > days[tm]) return false;
 63             else return true;
 64         }
 65         else
 66         {
 67             int max_td = (isLeap(ty) ? 29 : 28);
 68             if (cur_d > max_td) return false;
 69             else return true;
 70         }
 71     }
 72 }
 73 void solve()
 74 {
 75     bool pre=win[cur_y][cur_m][cur_d] = false;
 76     while (cur_y != 1900 || cur_m != 1 || cur_d != 1)
 77     {
 78         sub();
 79         if (can_nextM())
 80         {
 81             int ty = cur_y, tm = cur_m;
 82             tm++;
 83             if (tm > 12) ty++, tm = 1;
 84             if (!pre || !win[ty][tm][cur_d]) pre = win[cur_y][cur_m][cur_d] = true;
 85             else pre = win[cur_y][cur_m][cur_d] = false;
 86         }
 87         else
 88         {
 89             if (pre) pre = win[cur_y][cur_m][cur_d] = false;
 90             else pre = win[cur_y][cur_m][cur_d] = true;
 91         }
 92     }
 93 }
 94 int main()
 95 {
 96     solve();
 97     int t;
 98     scanf("%d", &t);
 99     while (t--)
100     {
101         int y, m, d;
102         scanf("%d%d%d", &y, &m, &d);
103         if (win[y][m][d]) printf("YES
");
104         else printf("NO
");
105     }
106     return 0;
107 }

View Code