[NOIP2016 普及组] 回文日期

题目背景

NOIP2016 普及组 T2

题目描述

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

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

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

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

例如：

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

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

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

每一年中都有$12$个月份：

其中，$1,3,5,7,8,10,12$月每个月有$31$天；$4,6,9,11$月每个月有$30$天；而对于$2$月，闰年时有$29$天，平年时有$28$天。

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

1.这个年份是$4$的整数倍，但不是$100$的整数倍；

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

例如：

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

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

输入格式

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

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

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

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

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

输出格式

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

样例 #1

样例输入 #1

20110101
20111231

样例输出 #1

1

样例 #2

样例输入 #2

20000101
20101231

样例输出 #2

2

提示

【样例说明】

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

对于样例2，符合条件的日期是$20011002$和$20100102$。

【子任务】

对于$60\%$的数据，满足$date1 = 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;//将倒序数与原数字进行比较
}

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

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

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

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

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

优化

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

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

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

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

此时时间复杂度为$\Theta(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;
}

---