P4698 回文日期（【基础】）

解题思路

8 位回文日期长成 yyyymmdd 的样子，其中 mmdd 恰好是 yyyy 反过来写的。所以不用一天一天枚举，只要枚举年份 yyyy，把它的数字倒过来拼成月日，就能直接得到这一年唯一的回文日期。下面分五步实现。

**第一步，枚举年份。**读入两个 8 位日期 date1 和 date2，年份就是日期除以 10000：startYear = date1 / 10000，endYear = date2 / 10000，从 startYear 到 endYear 逐个枚举。

**第二步，拼月日。**把年份的数字倒过来：month = (year % 10) × 10 + (year / 10 % 10)，day = (year / 100 % 10) × 10 + (year / 1000)。比如 2020 年，倒过来是 0202，也就是 2 月 2 日。

**第三步，检查范围。**拼出的完整日期 date = year × 10000 + month × 100 + day，必须落在 [date1, date2] 之间（含端点）。

**第四步，检查合法性。**月份要在 1 到 12 之间；日期要在 1 到当月天数之间。2 月还要判断是不是闰年：能被 400 整除，或能被 4 整除但不能被 100 整除，闰年 2 月有 29 天。

**第五步，统计。**三个条件都满足就把 count 加一，最后输出 count。

打个比方：回文日期就像镜子里的日期，看到年份就能猜到月日，年份最多一万个，每个判断都是常数时间，非常快。

边界情况：拼出来的月份可能超过 12（比如 2019 年倒过来是 9102，月份是 91，非法），一定要检查；范围判断含端点，用小于等于。

参考代码

// P4698 回文日期：统计两个日期之间（含端点）有多少个真实存在的回文日期
#include <iostream>
using namespace std;

int main() {
    int date1, date2;
    cin >> date1 >> date2;
    int startYear = date1 / 10000, endYear = date2 / 10000;
    int count = 0;
    for (int year = startYear; year <= endYear; year++) {
        // 回文日期：year的逆序拼成month+day，如 2020 -> 0202（2月2日）
        int month = (year % 10) * 10 + (year / 10 % 10);
        int day = (year / 100 % 10) * 10 + (year / 1000);
        int date = year * 10000 + month * 100 + day;
        if (date < date1 || date > date2) continue;   // 不在给定范围内
        if (month < 1 || month > 12) continue;        // 月份非法
        int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)) days[2] = 29;  // 闰年
        if (day < 1 || day > days[month]) continue;   // 日期非法
        count++;
    }
    cout << count << endl;
    return 0;
}

复杂度分析

枚举年份 y1 到 y2，最多约 9000 年，每年只做常数次判断，时间复杂度 O(年份数)，空间 O(1)。