题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。

因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。

我们称这样的日期是回文日期。

有人表示 20200202 是“千年一遇” 的特殊日子。

对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。

对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。

算不上“千年一遇”，顶多算“千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int check(int x)
{
    int year,month,day;
    year = x/10000;
    month = x/100%100;
    day = x%100;
    if(month<=0||month>12)  return 0;
    if(month!=2&&day<=0||day>days[month])   return 0;
    if(month==2)
    {
        int c;
        c = year%4==0&&year%100!=0||year%400==0;
        if(day>days[month]+c)
            return 0;
    }
    return 1;
}
int check2(int n)
{
    int a,b,c,d,e;
    e = n/10000;
    a = e/1000;
    b = e/100%10;
    c = e/10%10;
    d = e%10;
    if(a==c&&b==d&&a!=b)
        return 1;
    return 0;
} 
int main()
{
    int n,m;
    int flag=1;
    cin>>n;
    m=n/10000;
    for(int i = 1;i <= 9999;i++)
    {
        int a=i,b=i;
        for(int j = 1;j <= 4;j++)
            a=a*10+b%10,b=b/10;
        if(check(a)&&flag==1&&a>n)
        {
            cout<<a<<endl;
            flag=0;
        }
        if(check(a)&&check2(a)&&flag==0&&a>n)
        {
            cout<<a<<endl;
            break;
        }
    }
    return 0;
 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla