题解 | #回文日期#

题目链接

BGN18 回文日期

题目描述

一个日期用 YYYYMMDD 的8位数字表示。若这8位数字本身是一个回文数，则称该日期为回文日期。给定起始日期 $startDate$ 与终止日期 $endDate$ （均包含在内），请计算区间内真实存在的回文日期数量。

回文数：一个数字从左往右读与从右往左读完全相同。
日期合法性：
- 1, 3, 5, 7, 8, 10, 12 月有 31 天。
- 4, 6, 9, 11 月有 30 天。
- 2 月在闰年有 29 天，平年有 28 天。
闰年判定：能被 4 整除但不能被 100 整除的年份；或能被 400 整除的年份。

输入描述

第一行输入8位整数 $startDate$ ，表示起始日期。第二行输入8位整数 $endDate$ ，表示终止日期。

输出描述

输出一个整数，表示 $[startDate, endDate]$ 区间内回文日期的数量。

样例

输入

20110101
20111231

输出

说明

此例中，回文日期为 20111102。

解题思路

如果暴力地从 $startDate$ 开始，一天一天地增加，直到 $endDate$ ，再判断每一天是不是回文日期，那么计算量会非常大，很容易超时。

高效的方法是利用回文数的结构特性。一个8位的回文日期 YYYYMMDD 必须满足 YYYY 和 MMDD 的数字是镜像对称的。这意味着，只要年份 YYYY 确定了，对应的 MMDD 也就唯一确定了（即 YYYY 的倒序）。

例如，如果年份是 2011，倒序是 1102，那么唯一可能的回文日期就是 20111102，对应的月份是 11，日期是 02。

因此，我们不需要遍历每一天，只需要遍历年份即可。

算法步骤：

读入起始日期 $startDate$ 和终止日期 $endDate$ 。
从 $startDate$ 中提取起始年份 $startY$ ，从 $endDate$ 中提取终止年份 $endY$ 。
初始化计数器 $count = 0$ 。
遍历从 $startY$ 到 $endY$ 的每一年 $y$ ：

a. 将年份 $y$ 转换成4位字符串（不足4位前补0，但根据题目范围 $1000 \le Y$ 实际不需要）。

b. 将年份字符串倒序，得到一个4位字符串。

c. 从倒序后的字符串中解析出月份 $mm$ 和日期 $dd$ 。

d. 将 $y, mm, dd$ 拼接成一个8位的整数 $palindromeDate$ 。

e. 进行剪枝/范围判断：检查 $palindromeDate$ 是否在 $[startDate, endDate]$ 的区间内。如果不在，则无需进行后续的合法性判断。

f. 进行日期合法性判断：
```
i.  月份 $mm$ 是否在 `[1, 12]` 之间。
ii. 日期 $dd$ 对于 $y$ 年 $mm$ 月来说是否合法（例如，2月不能有30号，平年2月不能有29号）。
```
g. 如果范围和合法性都满足，则将 $count$ 加 1。
遍历结束后，输出 $count$ 。

这个方法将原来对天数的遍历，转换为了对年份的遍历，大大降低了计算量。

代码

c++
java
python

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

// 检查日期是否合法
bool isValidDate(int y, int m, int d) {
    if (m < 1 || m > 12 || d < 1) {
        return false;
    }
    int month_days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (isLeap(y)) {
        month_days[2] = 29;
    }
    return d <= month_days[m];
}

int main() {
    int start_date, end_date;
    cin >> start_date >> end_date;

    int start_year = start_date / 10000;
    int end_year = end_date / 10000;
    int count = 0;

    for (int y = start_year; y <= end_year; ++y) {
        string year_str = to_string(y);
        string reversed_year_str = year_str;
        reverse(reversed_year_str.begin(), reversed_year_str.end());

        int m = stoi(reversed_year_str.substr(0, 2));
        int d = stoi(reversed_year_str.substr(2, 2));

        int palindrome_date = y * 10000 + m * 100 + d;
        
        if (palindrome_date >= start_date && palindrome_date <= end_date) {
            if (isValidDate(y, m, d)) {
                count++;
            }
        }
    }

    cout << count << '\n';
    return 0;
}

import java.util.Scanner;

public class Main {
    // 判断是否为闰年
    private static boolean isLeap(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }

    // 检查日期是否合法
    private static boolean isValidDate(int y, int m, int d) {
        if (m < 1 || m > 12 || d < 1) {
            return false;
        }
        int[] month_days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (isLeap(y)) {
            month_days[2] = 29;
        }
        return d <= month_days[m];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int start_date = sc.nextInt();
        int end_date = sc.nextInt();

        int start_year = start_date / 10000;
        int end_year = end_date / 10000;
        int count = 0;

        for (int y = start_year; y <= end_year; y++) {
            String year_str = Integer.toString(y);
            String reversed_year_str = new StringBuilder(year_str).reverse().toString();

            int m = Integer.parseInt(reversed_year_str.substring(0, 2));
            int d = Integer.parseInt(reversed_year_str.substring(2, 4));

            int palindrome_date = y * 10000 + m * 100 + d;

            if (palindrome_date >= start_date && palindrome_date <= end_date) {
                if (isValidDate(y, m, d)) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

# -*- coding: utf-8 -*-
import sys

def is_leap(year):
    # 判断是否为闰年
    return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

def is_valid_date(y, m, d):
    # 检查日期是否合法
    if not (1 <= m <= 12 and 1 <= d <= 31):
        return False
    
    month_days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if is_leap(y):
        month_days[2] = 29
        
    return d <= month_days[m]

start_date_str = input()
end_date_str = input()

start_date = int(start_date_str)
end_date = int(end_date_str)

start_year = int(start_date_str[:4])
end_year = int(end_date_str[:4])

count = 0
for y in range(start_year, end_year + 1):
    year_str = str(y)
    reversed_year_str = year_str[::-1]
    
    m = int(reversed_year_str[:2])
    d = int(reversed_year_str[2:])
    
    palindrome_date_str = year_str + reversed_year_str
    palindrome_date = int(palindrome_date_str)
    
    if start_date <= palindrome_date <= end_date:
        if is_valid_date(y, m, d):
            count += 1
            
print(count)

算法及复杂度

算法：枚举、模拟
时间复杂度：设起始年份为 $Y_{start}$ ，终止年份为 $Y_{end}$ 。我们遍历从 $Y_{start}$ 到 $Y_{end}$ 的所有年份。对于每一年，我们都执行常数次字符串操作、类型转换和合法性检查。因此，总时间复杂度为 $O(Y_{end} - Y_{start})$ 。
空间复杂度：我们只使用了少数变量来存储日期和年份，以及一个固定大小的数组存储每月天数，因此空间复杂度为 $O(1)$ 。