题解 P1512 【伊甸园日历游戏　】

· · 题解

· 题意

有t组数据，每次给定一个日期，两个人轮流对这个日期进行操作：天数+1或月份+1。先到达2006.11.4者赢。

· 解题思路 & 方法

提示是个好东西：

说明/提示
建议先把所有情况都算出来^_^

因此，我们可以用记搜来求出所有的情况——

#include <iostream>
#include <cstdio>
using namespace std;
int t,x,y,z,f[2007][15][35],m[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
//，m数组存储每个月有多少天
bool vis[2007][15][35];
bool check(int year,int month,int day){//判断是否超过目标日期
    if(year<2006)
        return true;
    if(year==2006 && month<11)
        return true;
    if(year==2006 && month==11 && day<4)
        return true;
    return false;
}
int dfs(int year,int month,int day){
    if((year%4!=0 || year==1900) && month==2 && day==29)
        return 1;
    if(day>m[month])//若天数超过当前月的，则说明到了下一个月
        month++,day=1;//月份++，从1号重新开始
    if(month>12)//若已经超过了12个月，说明到了下一年
        year++,month=1;//年份++，从1月重新开始
    //说句闲话：相当于进位（？）
    if(vis[year][month][day])//如果已经查找过直接返回结果即可
        return f[year][month][day];
    vis[year][month][day]=1;//标记为已查找
    if(day<=m[month+1] && check(year,month+1,day))//注意，这里有个小细节：如果要改变月份，应先判断一下当前天数是否下一个月的天数（因为每个月的天数不一样）
        f[year][month][day]=((dfs(year,month+1,day))^1);//^1相当于取反，若是为1则返回0，若是为0则返回1
    if(check(year,month,day+1))
        f[year][month][day]|=((dfs(year,month,day+1)^1));
    return f[year][month][day];
}

int main(){
    f[2006][11][3]=1;
    dfs(1900,1,1);//从1900年1月1日开始搜索
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&x,&y,&z);
        if(f[x][y][z])
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
#include <iostream>
#include <cstdio>
using namespace std;
int t,x,y,z,f[2007][13][32],m[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
void dp(){
    int year=2006,month=11,day=4;//从目标日期开始逆推
    f[2006][11][4]=1;//注意，这里要赋值为1，不然会玄学WA（别问我咋知道的
    while(!(year==1900 && month==1 && day==1)){
        int y1=year,m1=month,d1=day;
        day--;
        if(day==0){//说明这一个月已经推完了
            month--;//继续倒着推上一个月
            if(month==0)//若是这一年都推完了
                month=12,year--;//（同理）
            day=m[month];
            if(((year%4==0 && year%100!=0) || year%400==0) && month==2)
                day++;//若是闰年的二月份，天数++
        } 
        if(f[y1][m1][d1]==1){//如果当前这个日期不满足
            f[year][month][day]=2;//则说明上一个（因为是逆推）日期满足
            continue;         //因为是这两个人轮流进行操作
        }
        y1=year;m1=month+1;d1=day;
        if(m1==13)//（进位~）
            y1++,m1=1;
        if(f[y1][m1][d1]==1)//同上
            f[year][month][day]=2;
        else
            f[year][month][day]=1;
    } 
}
int main(){
    dp();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&x,&y,&z);
        if(f[x][y][z]==2)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0; 
}

首先不看年份，每次操作必定会使日期和月份的和的奇偶性发生变化。目标日期11.4（11+4=15）是奇数。而天数或月份+1都会导致其和的奇偶性发生改变。

但是要注意两个特殊的日期 ：9月30日(日+1为10.1，月+1为10.30)和11月30日（日+1为12.1，月+1为12.30），奇偶性可能是保持不变的，但是因为Adam足够聪明（），所以可以通过加月份来避开这一天，因此若是日期一开始是偶数或者是这两天，先者赢，否则后者赢。

#include <iostream>
#include <cstdio>
using namespace std;
int t,x,y,z;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&x,&y,&z);
        if((y==9 && z==30) || (y==11 && z==30) || (y+z)%2==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}