【题意】两个人玩游戏。游戏规则是，给定一个年份，你有两种操作：把当前的日期变成第二天，比如说1999.12.31那么第二天就是2000.1.1；或者把当前日期变成下一个月的同一天，比如1998.02.04，可以变成1998.03.04，但是如果下一个月没有这一天就不能执行这个操作。比如说1998.1.31，下一个月没有31号，就只能执行第一个操作，变成1998.2.1。游戏胜利的规则是恰好把某一天变成了2001.11.4，超过这一天也算输。 （数据规模，从1900.1.1到2001.11.4） 【分析】这算是很简单的博弈了，也不用找什么公式，不用求sg函数，用搜索就可以解决了。具体方法是用三维数组f[2000][20][50],表示某一天f[i][j][k]是必胜态还是必败态，g[i][j][k]表示这个日期是不是访问过。搜索的时候，当f[i][j][k]的后继状态有至少有一个必败态的时候当前状态就是必胜态，否则就是必败态。虽然这是多组数据但是状态数组不用每次都清零，因为一个状态是不是必胜态是确定的，所以搜过之后直接调用就好了。找后继状态还是比较麻烦的，我写好就交了一发试试，竟然一次AC了。
#include<cstdio> using namespace std; int f[2000][20][50]; int g[2000][20][50]; const int years [2][13]= {{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}}; struct p{ int y, m, d; }; int isleap(int y){//判断是不是闰年 return ((y % 400) == 0 || (y % 100) && (y % 4) == 0); } p nextd(p a){ p b = a; b.d ++; if(b.d > years[isleap(b.y)][b.m]) { b.m++; b.d = 1; if(b.m > 12) { b.m = 1; b.y ++; } } return b; } p nextm(p a){ p b = a; b.m ++; if(b.d > years[isleap(b.y)][b.m]) {//如果下个月的这一天不存在的话这种操作就不能执行，调用第一种操作 return nextd(a); } return b; } int dfs(p a){ if(a.y == 2001 && a.m == 11 && a.d == 4) return 0; if(a.y > 2001 || a.y == 2001 && a.m > 11 || a.y == 2001 && a.m == 11 && a.d > 4) return 1; if(g[a.y][a.m][a.d]) return f[a.y][a.m][a.d]; g[a.y][a.m][a.d] = 1; f[a.y][a.m][a.d] = 0; if(dfs(nextd(a)) == 0 || dfs(nextm(a)) == 0) f[a.y][a.m][a.d] = 1; return f[a.y][a.m][a.d]; } int main(){ int T; int yy, mm, dd; p a; scanf("%d", &T); while(T--){ scanf("%d%d%d", &a.y, &a.m, &a.d); puts(dfs(a) ? "YES" : "NO"); } }