算法
枚举,模拟
因为回文日期前后对称,所以我们只需枚举0~9999这10000个数的年日期,根据回文特征计算出该年份对应的回文日期为多少,例如:2021对应20211202,2012对应20122102。然后写个check函数来判断每个枚举的年日期所对应的回文日期是否合法,并用res来记录合法的个数。
时间复杂度
一共枚举$10^4$个数,判断每个数是否合法的计算量是常数级别的,因此总计算量是 $O(10^4)$
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int date1,date2;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int date){
int year=date/10000,month=date%10000/100,day=date%100;
if(month==0||month>12) return false;
if(day==0) return false;
if(month!=2){
if(day>days[month]) return false;
}
else
{
int leap=year%100&&year%4==0||year%400==0;
if(day>28+leap) return false;
}
return true;
}
int main(){
cin>>date1>>date2;
int res=0;
for(int i=1;i<=9999;i++){
int date=i,r=i,l;
for(int j=1;j<5;j++){
l=r%10;
r/=10;
date=date*10+l;
}
if(check(date)&&date>=date1&&date<=date2) res++;
}
cout<<res<<endl;
return 0;
}
`