题目网址：
https://www.luogu.com.cn/problem/P2010

题目背景

NOIP2016 普及组 T2

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 8 位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 8 位数字是回文的，当且仅当对于所有的 i（1≤i≤8）从左向右数的第 i 个数字和第 9-i 个数字（即从右向左数的第 i 个数字）是相同的。

例如：

• 对于 2016 年 11 月 19 日，用 8 位数字 20161119 表示，它不是回文的。
• 对于 2010 年 1 月 2 日，用 8 位数字 20100102 表示，它是回文的。
• 对于 2010 年 10 月 2 日，用 8 位数字 20101002 表示，它不是回文的。

每一年中都有 12 个月份：

其中，1,3,5,7,8,10,12 月每个月有 31 天；4,6,9,11 月每个月有 30 天；而对于 2 月，闰年时有 29 天，平年时有 28 天。

一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1. 这个年份是 4 的整数倍，但不是 100 的整数倍；
2. 这个年份是 400 的整数倍。

例如：

• 以下几个年份都是闰年：2000,2012,2016。
• 以下几个年份是平年：1900,2011,2014。

输入格式

两行，每行包括一个 8 位数字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的终止日期。

保证 date1 和 date2 都是真实存在的日期，且年份部分一定为 4 位数字，且首位数字不为 0。

保证 date1 一定不晚于 date2。

输出格式

一个整数，表示在 date1 和 date2 之间，有多少个日期是回文的。

输入输出样例

输入 #1复制

20110101
20111231

输出 #1

1

输入 #2

20000101
20101231

输出 #2

2

说明/提示

【样例说明】

对于样例 1，符合条件的日期是 20111102。

对于样例 2，符合条件的日期是 20011002 和 20100102。

【子任务】

对于 60% 的数据，满足 date1=date2。

题解：

算法思路：枚举优化

核心性质

回文结构：日期格式为 YYYYMMDD，回文要求：

优化策略：枚举年份（1000-9999），通过年份生成回文日期：

对年份 Y反转得到 M1M2D1D2

组合日期：Y+ 反转(Y)→ YYYY M1M2 D1D2

日期验证

验证生成的日期是否：

1. 月份在 1-12 范围内
2. 日期在当月有效（考虑闰年2月）

代码详细注释

#include <iostream>
using namespace std;

// 检查8位日期是否有效
bool isdate(int x) {
    int y = x / 10000;        // 提取年份
    int m = (x % 10000) / 100; // 提取月份
    int d = x % 100;           // 提取日期

    // 月份检查
    if (m < 1 || m > 12) 
        return false;

    // 根据月份确定最大天数
    int max_day;
    if (m == 2) {  // 2月特殊处理
        // 闰年判断：能被4整除且不被100整除，或能被400整除
        if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) 
            max_day = 29;  // 闰年29天
        else 
            max_day = 28;  // 平年28天
    } 
    // 小月（4、6、9、11月）
    else if (m == 4 || m == 6 || m == 9 || m == 11) 
        max_day = 30;
    // 大月
    else 
        max_day = 31;
    
    // 日期有效性检查
    return (d >= 1 && d <= max_day);
}

// 通过年份生成回文日期
int makepal(int year) {
    int rev = 0, t = year;
    // 反转年份：生成后4位（月份+日期）
    for (int i = 0; i < 4; i++) {
        rev = rev * 10 + t % 10;  // 取末位加入反转数
        t /= 10;                 // 移除末位
    }
    return year * 10000 + rev;  // 组合成8位日期
}

int main() {
    int a, b;
    cin >> a >> b;  // 输入起始和结束日期

    // 提取年份范围
    int st = a / 10000;  // 起始年份
    int ed = b / 10000;  // 结束年份
    int ans = 0;

    // 枚举年份并验证回文日期
    for (int year = st; year <= ed; year++) {
        int date = makepal(year);  // 生成回文日期
        // 检查是否在 [a, b] 区间且日期有效
        if (date < a || date > b) continue;
        if (isdate(date)) ans++;
    }

    cout << ans << endl;
    return 0;
}

关键步骤图解

1. 回文日期生成

• 映射关系：
• YYYY→ Y1Y2Y3Y4MMDD→ Y4Y3Y2Y1

2. 日期验证流程

3. 运行示例

输入：20000101 20100101

生成与验证：

输出：2

复杂度分析

• 时间复杂度：O(9000)=O(1)
• 仅枚举9000个年份，每个年份 O(1)生成和验证
• 空间复杂度：O(1)
• 仅用常数级变量存储