蓝桥杯 回文日期

原题目链接

📅 回文日期与 ABABBABA 日期查找题解

🧩 题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人说 20200202 是“千年一遇”的特殊日子。但其实，不到两年之后就有下一个回文日期：20211202。

更进一步，20200202 还是一种特殊结构的回文数——ABABBABA 型。例如：

• A：第 1、3、6、8 位
• B：第 2、4、5、7 位

即满足模式：ABABBABA

这种日期的下一个出现是在 21211212。

输入格式

一个 8 位整数 $N$，表示合法日期，范围满足：

10000101 ≤ N ≤ 89991231

输出格式

输出两行，每行一个 8 位数。

• 第一行为 $N$ 之后的下一个回文日期。
• 第二行为 $N$ 之后的下一个 ABABBABA 型的回文日期。

示例

输入：

20200202

输出：

20211202
21211212

🔍 思路解析

本题需要从给定日期 $N$ 出发，一天一天模拟：

1. 将日期按 yyyymmdd 转换成字符串，判断是否是回文。
2. 判断是否满足 ABABBABA 模式。
3. 一旦满足条件就记录结果并继续查找，直到找到两个目标为止。

🔧 算法解析

• 日期有效性处理：使用常规的闰年判断和每月天数表来保证日期合法。
• 字符串判断：
  • 回文判断：直接反转字符串并比对。
  • ABABBABA 判断：检查字符串各位置是否符合该模式。
• 模拟日期递增：
  • 按天递增，如果天数超过当月最大天数，就进位到下一个月。
  • 如果月数进位超过 12，则年份 +1，月份重置为 1。

💻 完整 C++ 实现

#include<bits/stdc++.h>

using namespace std;

int year, month, day;
vector<int> months = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 判断是否闰年
bool isrun(int year) {
    return ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));
}

// 判断是否是回文字符串
bool ishui(string str) {
    string mid = str;
    reverse(str.begin(), str.end());
    return str == mid;
}

// 判断是否是 ABABBABA 型
bool isABABBABA(string str) {
    char a = str[0], b = str[1];
    return str[2] == a && str[3] == b && str[4] == b &&
           str[5] == a && str[6] == b && str[7] == a;
}

// 计算下一天
void next_day() {
    bool leap = isrun(year);
    if (leap) months[2]++;
    day++;
    if (day > months[month]) {
        day = 1;
        month++;
        if (month == 13) {
            month = 1;
            year++;
        }
    }
    if (leap) months[2]--;  // 恢复2月为28天
}

int main() {
    string str;
    char buffer[100] = {0};
    cin >> str;
    year = stoi(str.substr(0, 4));
    month = stoi(str.substr(4, 2));
    day = stoi(str.substr(6));

    string res1 = "", res2 = "";
    while (res1 == "" || res2 == "") {
        next_day();
        sprintf(buffer, "%04d%02d%02d", year, month, day);
        str = buffer;
        if (res1 == "" && ishui(str)) res1 = str;
        if (res2 == "" && isABABBABA(str)) res2 = str;
    }
    cout << res1 << endl << res2;
    return 0;
}

🧠 时间与空间复杂度分析

• 时间复杂度：
  • 最坏情况下需要遍历数万天，复杂度约为 $O(\text{天数})$。
• 空间复杂度：
  • 常数空间 $O(1)$，仅使用若干变量。

✅ 总结

本题考察了：

• 时间模拟与日期处理
• 字符串模式匹配
• 基本的回文检测

虽然是模拟题，但涉及多个细节（如闰年判断、字符串操作等），非常适合作为练习细节实现与思维清晰度的综合题目。