LUOGU P1512 伊甸园日历游戏

题目描述

Adam和Eve玩一个游戏，他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作：

1 ：把日期的天数加1，例如1900.1.1变到1900.1.2

2 ：把月份加1，例如：1900.1.1变到1900.2.1

其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候，如果有这样的日期：1900.1.31，则变成了1900.2.31，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。

谁先将日期变到2001.11.4谁就赢了。

每次游戏都是Adam先操作，问他有没有必胜策略？

输入输出格式

输入格式：

一个测试点。多组数据。

第一行为数据组数。

接下来一行X Y Z表示X年Y月Z日

输出格式：

输出“YES”or“NO”表示亚当是否有必胜策略。

输入输出样例

输入样例#1：复制

3

2001 11 3

2001 11 2

2001 10 3

输出样例#1：复制

YES

NO

NO

说明

建议先把所有情况都算出来^_^

解题思路

记忆化搜索+博弈论。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int f[2005][15][35];

int month[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};

bool vis[2005][15][35];

int T;

inline bool pd(int y,int m,int d){

    if(y<2001) return true;

    if(y==2001 && m<11) return true;

    if(y==2001 && m==11 && d<4) return true;

    return false;

} 

inline int dfs(int y,int m,int d){

    if((y%4!=0 || y==1900) && m==2 && d==29) return 1;

    if(d>month[m]) {m++;d=1;}

    if(m==13) y++,m=1;

    if(vis[y][m][d]) return f[y][m][d];vis[y][m][d]=1;

    if(month[m+1]>=d && pd(y,m+1,d))  f[y][m][d]=((dfs(y,m+1,d))^1);

    if(pd(y,m,d+1)) f[y][m][d]|=((dfs(y,m,d+1)^1));

    return f[y][m][d];

}

int main(){

    f[2001][11][3]=f[2001][10][4]=1;

    dfs(1900,1,1);

//  for(register int i=1900;i<=2001;i++)

//      for(register int j=1;j<=12;j++)

//          for(register int k=1;k<=31;k++)

//              printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);

    scanf("%d",&T);int x,y,z;

    while(T--){

        scanf("%d%d%d",&x,&y,&z);

        puts(f[x][y][z]?"YES":"NO");

    }

    return 0;

}

巴特西

LUOGU P1512 伊甸园日历游戏

解题思路

代码

最新文章

热门文章