【题解】 [NOIP2016 普及组] 回文日期

[NOIP2016 普及组] 回文日期

题目背景

NOIP2016 普及组 T2

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用888位数字表示一个日期，其中，前444位代表年份，接下来222位代表月份，最后222位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现 在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存 在的日期是回文的。

一个888位数字是回文的，当且仅当对于所有的i(1≤i≤8)i ( 1 \le i \le 8)i(1≤i≤8)从左向右数的第i个 数字和第9−i9-i9−i个数字（即从右向左数的第iii个数字）是相同的。

例如：

•对于2016年11月19日，用888位数字201611192016111920161119表示，它不是回文的。

•对于2010年1月2日，用888位数字201001022010010220100102表示，它是回文的。

•对于2010年10月2日，用888位数字201010022010100220101002表示，它不是回文的。

每一年中都有121212个月份：

其中，1,3,5,7,8,10,121,3,5,7,8,10,121,3,5,7,8,10,12月每个月有313131天；4,6,9,114,6,9,114,6,9,11月每个月有303030天；而对于222月，闰年时有292929天，平年时有282828天。

一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1.这个年份是444的整数倍，但不是100100100的整数倍；

2.这个年份是400400400的整数倍。

例如：

•以下几个年份都是闰年：2000,2012,20162000,2012,20162000,2012,2016。

•以下几个年份是平年：1900,2011,20141900,2011,20141900,2011,2014。

输入格式

两行，每行包括一个888位数字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的终止日期。

保证 date_i 和都是真实存在的日期，且年份部分一定为444位数字，且首位数字不为000。

保证 date 1 —定不晚于 date 2 。

输出格式

一个整数，表示在date1date1date1和date2date2date2之间，有多少个日期是回文的。

样例 #1

样例输入 #1

20110101
20111231

样例输出 #1

1

样例 #2

样例输入 #2

20000101
20101231

样例输出 #2

2

提示

【样例说明】

对于样例1，符合条件的日期是201111022011110220111102。

对于样例2，符合条件的日期是200110022001100220011002和201001022010010220100102。

【子任务】

对于60%60\%60%的数据，满足date1=date2date1 = date2date1=date2。

题目分析

阅读题目，可发现题目要求的是在起止日期之间，统计回文日期的个数。

在范围内统计满足条件的元素个数，可以联想到使用枚举法进行处理。

for(i:开始日期 ~ 结束日期){
    if(i是否是回文日期){
        统计个数
    }
}

此时，先解决第一个问题，如何判断一个日期是回文日期？根据题面信息可知回文日期表示这个日期的8位数字是回文的。所以只要能判断回文数就可以了。回文数的判断则可以通过求出数字的倒序数，倒序数与原数字相同则是回文数，不相同则属于非回文数。

bool isHw(int date){//判断回文数
    int num=date,_date=0;
    while(num){
        _date=_date*10+num%10;
        num/=10;
    }
    return _date==date;//将倒序数与原数字进行比较
}

过程中需要注意一个问题，若起止日期为201901012019010120190101 和202012122020121220201212 ，遍历这两个数的所有数字的话忙着遍历到数字201991022019910220199102 该数字为两数之间的回文数，但是却不是一个合法的日期。所以，我们除了需要对8位数是否是回文数进行判断以外，还需要判断日期是否是真实存在的日期。

对于日期是否真实存在，主要是在于月份和天数这两块地方。月份的范围是 1∼121\sim 121∼12 ，天数的范围是 1∼该月最大天数1\sim 该月最大天数1∼该月最大天数 。

可以通过%100 来获取天数；通过/100%100 来获取月份。过程中可以提前构建months[] 数组，用于快速确定月份对应的天数。需要注意闰平年对2月天数的影响。

for(i:开始日期 ~ 结束日期){
    if(i是否是合法的回文日期){
        统计个数
    }
}

此时，时间复杂度为Θ(n)\Theta(n)Θ(n) 。日期为8位数，比较勉强。

优化

回文日期的特征是八位数字是回文的，前4位是年份，后2位是月份，最后2位是天数。那么前四位与后四位就是对应的，也就是说，通过前四位的年份可以推测出整个八位的回文数，举例：2010 - 20100102 ，2011 - 20111102 等。

那么，我们只需遍历起止日期的年份，即可找出每个年份对应的八位回文数，只需判断该回文数是否合法即可。

• 日期在 date1∼date1date1 \sim date1date1∼date1 之间
• 月份 满足 1∼121\sim 121∼12
• 天数 满足 1∼months[月份]1\sim months[月份]1∼months[月份]

for(i:date1/10000 ~ date2/10000){
    if(判断i是否是合法日期){
        cnt++;
    }
}

此时时间复杂度为Θ(n)\Theta(n)Θ(n)，此时n为四位的年份。满足时间要求。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int date1,date2;
int hwDate(int y){
	//根据年份构建回文日期
	int date=y;
	while(y){
		date=date*10+y%10;
		y/=10;
	}
	return date;
}

bool isLeap(int y){
	//判断闰年
	if((y%4==0&&y%100!=0) || y%400==0) return true;
	return false;
}
bool isTrue(int date){
	//判断日期是否合法
	//根据闰平年修改二月天数
	if(isLeap(date/10000)) m[2]=29;
	else m[2]=28;
	int mon=date/100%100;
	int d=date%100;
	//在起止日期之间 月份和天数合法
	if((date1<=date && date<=date2) && mon<=12 && d<=m[mon])
		return true;
	return false;
}
int main(){
	int cnt=0;
	cin>>date1>>date2;
	//遍历起始日期之间的年份
	for(int i=date1/10000;i<=date2/10000;i++){
		int date=hwDate(i);//根据年份构造回文日期
		if(isTrue(date)) cnt++;//统计回文日期数量
	}
	cout<<cnt;
	return 0;
}

Q.E.D.