[关闭]
@ysner 2018-06-08T09:29:32.000000Z 字数 1653 阅读 1782

日历游戏

记忆化搜索 博弈论


题面

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

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

解析

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

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1024;
  14. int n,dp[2015][15][35];
  15. int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  16. il int check(re int y)
  17. {
  18. if(y==1900) return 0;
  19. if(y%4==0) return 1;
  20. return 0;
  21. }
  22. il void task1(re int &y,re int &m,re int &d)
  23. {
  24. if(m==2) mon[2]+=check(y);
  25. ++d;
  26. if(d>mon[m]) ++m,d=1;
  27. if(m>12) ++y,m=1;
  28. mon[2]=28;
  29. }
  30. il void task2(re int &y,re int &m,re int &d)
  31. {
  32. if(m==2) mon[2]+=check(y);
  33. ++m;
  34. if(m>12) ++y,m=1;
  35. if(d>mon[m]) y=2013;
  36. mon[2]=28;
  37. }
  38. il int die(re int y,re int m,re int d)
  39. {
  40. if(y>2012||(y==2012&&m==12&&d>22)) return 1;
  41. return 0;
  42. }
  43. il int dfs(re int y,re int m,re int d)
  44. {
  45. if(y==2012&&m==12&&d==22) return dp[y][m][d]=0;
  46. if(dp[y][m][d]!=-1) return dp[y][m][d];
  47. if(die(y,m,d)) return dp[y][m][d]=1;
  48. re int yy=y,mm=m,dd=d;
  49. task1(y,m,d);if(!dfs(y,m,d)) return dp[yy][mm][dd]=1;
  50. y=yy;m=mm;d=dd;
  51. task2(y,m,d);if(!dfs(y,m,d)) return dp[yy][mm][dd]=1;
  52. return dp[yy][mm][dd]=0;
  53. }
  54. int main()
  55. {
  56. freopen("calendar.in","r",stdin);
  57. freopen("calendar.out","w",stdout);
  58. re int y,m,d;
  59. memset(dp,-1,sizeof(dp));
  60. while(~scanf("%d%d%d",&y,&m,&d))
  61. {
  62. if(dfs(y,m,d)) puts("YES");
  63. else puts("NO");
  64. }
  65. fclose(stdin);
  66. fclose(stdout);
  67. return 0;
  68. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注