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

1 题目阐明

2 题目分析

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

1. #include<iostream>
2. #include<string>
3. using namespace std;
5. int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
7. // 判断日期是否有效
8. bool valid(int date){
9.         int year=date/10000;
10.         int month=date%10000/100;
11.         int day=date%100;
12.         // 判断闰年
13.         if(year%400==0||year%4==0&&year%100!=0) m[2]=29;
14.         else m[2]=28;
15.     // 判断month和day是否在范围内
16.         if(month<=12&&month>0&&day<=m[month]&&day>0) return true;
17.         return false;
18. }
20. // 判断是否是回文日期
21. bool isPalindrome(string d){
22.         for(int i=0;i<8;i++)
23.         if(d[i]!=d[7-i]) return false;
24.         return true;
25. }
27. // 判断是否为ABABBABA型日期
28. bool isABABBABA(string d){
29.         // 判断回文在判断ABABBABA之前，只需要证明该回文日期的前半部分符合ABAB就行。
30.         if(d[0]==d[2]&&d[1]==d[3]) return true;
31.         return false;
32. }
34. int main(){
35.         int n;
36.         cin>>n;
37.         int flag=0;
38.         for(int i=n+1;;i++)
39.                 if(valid(i)&&isPalindrome(to_string(i))){
40.                         if(!flag){
41.                                 cout<<i<<endl;
42.                                 flag=1;
43.                         }
44.                         if(isABABBABA(to_string(i))){
45.                                 cout<<i;
46.                                 break;
47.                         }
48.                 }
49. }

复制代码