【题解】 [NOIP2016 普及组] 回文日期
【题解】 [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.