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

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

小鱼干 128 2022-09-28

[NOIP2016 普及组] 回文日期

题目背景

NOIP2016 普及组 T2

题目描述

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

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

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

一个88位数字是回文的,当且仅当对于所有的i(1i8)i ( 1 \le i \le 8)从左向右数的第i个 数字和第9i9-i个数字(即从右向左数的第ii个数字)是相同的。

例如:

•对于2016年11月19日,用88位数字2016111920161119表示,它不是回文的。

•对于2010年1月2日,用88位数字2010010220100102表示,它是回文的。

•对于2010年10月2日,用88位数字2010100220101002表示,它不是回文的。

每一年中都有1212个月份:

其中,1,3,5,7,8,10,121,3,5,7,8,10,12月每个月有3131天;4,6,9,114,6,9,11月每个月有3030天;而对于22月,闰年时有2929天,平年时有2828天。

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

1.这个年份是44的整数倍,但不是100100的整数倍;

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

例如:

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

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

输入格式

两行,每行包括一个88位数字。

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

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

保证$ date_i $和都是真实存在的日期,且年份部分一定为44位数字,且首位数字不为00

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

输出格式

一个整数,表示在date1date1date2date2之间,有多少个日期是回文的。

样例 #1

样例输入 #1

20110101
20111231

样例输出 #1

1

样例 #2

样例输入 #2

20000101
20101231

样例输出 #2

2

提示

【样例说明】

对于样例1,符合条件的日期是2011110220111102

对于样例2,符合条件的日期是20011002200110022010010220100102

【子任务】

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

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

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

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

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

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

image-20220928110434960

优化

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

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

  • 日期在 date1date1date1 \sim date1 之间
  • 月份 满足 1121\sim 12
  • 天数 满足 1months[月份]1\sim months[月份]
for(i:date1/10000 ~ date2/10000){
    if(判断i是否是合法日期){
        cnt++;
    }
}

此时时间复杂度为Θ(n)\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;
}