题目链接:P8716 [蓝桥杯 2020 省 AB2] 回文日期

这个题我一开始的想法是直接从输入的数字遍历到99999999,然后判断每一个数是不是回文数.但是很明显超时了.虽然是O(n)复杂度,但是几千万次循环也是很多的.

然后我们可以想,对于一个确定的年份,比如2012,那它对应的回文日期肯定是把2012反转后拼接到一起,一个唯一的20122102吧.然后我们判断一下月份和天数是否符合正常的月份和天数.不符合那就是不对,符合那就说明这是一个合法的回文日期了.立马从几千万次的循环,降低到几千次的循环就可以了.

python代码如下:

def check(year,month,day):
    # 下面的判断是int型,传入的数据是str型,要进行转换.
    year=int(year)
    month=int(month)
    day=int(day)
    if month in [1,3,5,7,8,10,12]:
        return 1<=day<=31
    elif month in [4,6,9,11]:
        return 1<=day<=30
    elif month==2:
        # 2月要判断一下是不是闰年.
        if (year%4==0 and year%100!=0) or year%400==0:
            return 1<=day<=29
        else:
            return 1<=day<=28
    return False

# 输入初始数据
a=int(input())
# 获取年份
b=a//10000
# 在找ABABBABA型的回文日期的时候,可能会遇到多个普通的回文日期,但是我们输出最早的一个就行了,做个标记
flag=0
# 直接从b+1年开始遍历
for year in range(b+1,9999):
    temp=str(year)[::-1]
    month=temp[0:2]
    day=temp[2:4]
    # 获取完整的日期,方便打印和判断是否是ABABBABA型回文日期.
    s=str(year)+str(month)+str(day)
    if check(year,month,day):
        if flag==0:
            print(s)
            flag=1
        if  s[0]==s[2]==s[5]==s[7] and s[1]==s[3]==s[4]==s[6] and s[0]!=s[1]:
            print(s)
            break

cpp代码如下:

#include<iostream>
using namespace std;
#include<string>
#include<algorithm>
#include<unordered_set>
#define int long long
bool check(int year, int month, int day)
{
    //利用集合来存储31天和30天的月份
    unordered_set<int> us1{ 1, 3, 5, 7, 8, 10, 12 };
    if (us1.find(month) != us1.end())return day >= 1 && day <= 31;
    unordered_set<int>us2{ 4,6,9,11 };
    if (us2.find(month) != us2.end())return day >= 1 && day <= 30;
    if (month == 2)
    {
        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)return day >= 1 && day <= 29;
        else return day >= 1 && day <= 28;
    }
    return false;
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int a; cin >> a;
    int b = a / 10000;
    bool flag = 1;
    for (int year = b + 1; year < 9999; year++)
    {
        // to_string(),将数字转为字符串,需引入<string>库
        string temp = (to_string(year));
        //reverse(),反转容器,无返回值,需引入<algorithm>库
        reverse(temp.begin(), temp.end());
        //stoi(),将字符串转换为数字,需引入<string>库
        int month = stoi(temp) / 100;
        int day = stoi(temp) % 100;
        string res = to_string(year) + temp;
        if (check(year, month, day))
        {
            if (flag)
            {
                cout << res << endl;
                flag = 0;
            }
            if ((res[0] == res[2] && res[0] == res[5] && res[0] == res[7]) && (res[1] == res[3] && res[1] == res[4] && res[1] == res[6]) && (res[0] != res[1]))
            {
                cout << res << endl;
                break;
            }
        }
    }
}