日历游戏

记忆化搜索 博弈论

题面

$xzy$和$lzx$正在玩一个日历游戏。
开始时,他们从$1900.1.1$到$2012.12.22$中选一个日期开始,依次按照如下规则之一向后跳日期:

• 跳到日历上的下一天。
• 跳到日历上的下个月的同一天(如果不存在,则不能这么做)。

要是谁正好到达$2012.12.22$那么他就赢了,如果到达这天之后的日期那他就输了。
每次都是$xzy$先走的。
现在,给你一个日期,请问$xzy$一定能赢吗?

解析

看到博弈懵逼系列。。。好像我没用过对抗搜索似的。
发现复杂度最大为$O(112*12*30)$即$O(5*10^4)$，状态量很少，可以使用记忆化搜索。
如何判断一个状态是必胜态还是必败态?
首先不合法状态都是必败态。
如果一个状态后面的状态都是必胜态，其就是必败态。
而如果一个状态后面的状态有一个为必败态，其就是必胜态。（有胜利的策略)
于是对每种策略进行$DFS$即可。
特别注意，由于不合法状态都是由必败态走来的，为保证12.22为必败态，所以其为必胜态

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1024;
int n,dp[2015][15][35];
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
il int check(re int y)
{
  if(y==1900) return 0;
  if(y%4==0) return 1;
  return 0;
}
il void task1(re int &y,re int &m,re int &d)
{
  if(m==2) mon[2]+=check(y);
  ++d;
  if(d>mon[m]) ++m,d=1;
  if(m>12) ++y,m=1;
  mon[2]=28;
}
il void task2(re int &y,re int &m,re int &d)
{
  if(m==2) mon[2]+=check(y);
  ++m;
  if(m>12) ++y,m=1;
  if(d>mon[m]) y=2013;
  mon[2]=28;
}
il int die(re int y,re int m,re int d)
{
  if(y>2012||(y==2012&&m==12&&d>22)) return 1;
  return 0;
}
il int dfs(re int y,re int m,re int d)
{
  if(y==2012&&m==12&&d==22) return dp[y][m][d]=0;
  if(dp[y][m][d]!=-1) return dp[y][m][d];
  if(die(y,m,d)) return dp[y][m][d]=1;
  re int yy=y,mm=m,dd=d;
  task1(y,m,d);if(!dfs(y,m,d)) return dp[yy][mm][dd]=1;
  y=yy;m=mm;d=dd;
  task2(y,m,d);if(!dfs(y,m,d)) return dp[yy][mm][dd]=1;
  return dp[yy][mm][dd]=0;
}
int main()
{
  freopen("calendar.in","r",stdin);
  freopen("calendar.out","w",stdout);
  re int y,m,d;
  memset(dp,-1,sizeof(dp));
  while(~scanf("%d%d%d",&y,&m,&d))
    {
      if(dfs(y,m,d)) puts("YES");
      else puts("NO");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}