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

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

我一开始想从输入的日期数字一直枚举到 99999999，再检查每个数是否回文，但这种写法超时了。即使每轮判断很短，几千万次循环的开销也不小。

可以改为枚举年份。对于一个确定的四位年份，把它反转后拼在后面，就得到唯一的八位回文候选。例如 2012 对应 20122102，但月份 21 不合法，不能作为答案。因此还需要检查月份、各月天数和闰年；合法后，再判断它是否符合 ABABBABA 型。这样枚举对象从几千万个整数缩小为几千个年份。

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

C++ 代码如下：

#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;
            }
        }
    }
}