P8716 [蓝桥杯 2020 省 AB2] 回文日期

1 题目说明

2 题目分析

暴力不会超时，O(n)的时间复杂度，$<10^8$。分析见代码：

#include<iostream>
#include<string>
using namespace std;int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};// 判断日期是否有效 
bool valid(int date){int year=date/10000;int month=date%10000/100;int day=date%100;// 判断闰年 if(year%400==0||year%4==0&&year%100!=0) m[2]=29;else m[2]=28;// 判断month和day是否在范围内if(month<=12&&month>0&&day<=m[month]&&day>0) return true;return false;
}// 判断是否是回文日期 
bool isPalindrome(string d){for(int i=0;i<8;i++)if(d[i]!=d[7-i]) return false;return true;
}// 判断是否为ABABBABA型日期 
bool isABABBABA(string d){// 判断回文在判断ABABBABA之前，只需要证明该回文日期的前半部分符合ABAB就行。if(d[0]==d[2]&&d[1]==d[3]) return true;return false;
}int main(){int n;cin>>n;int flag=0;for(int i=n+1;;i++)if(valid(i)&&isPalindrome(to_string(i))){if(!flag){cout<<i<<endl;flag=1;}if(isABABBABA(to_string(i))){cout<<i;break;}}
}