自动搬运

查看原文

来自洛谷，原作者为

	_Luminous “在坚冰还盖着北海的时候，我看到了怒放的梅花。”

搬运于2025-08-24 21:25:54，当前版本为作者最后更新于2020-10-25 23:46:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

· 题意

有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;
}

• 方法二：DP + 逆推

#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;
}