[NOIP 2016 普及组] 回文日期

GitHub 跳转原题关系图返回列表

利用回文日期的结构直接由年份反推月份和日期，再判断是否为真实日期并检查是否落在区间内。

OJ: luogu

题目 ID: P2010

难度:普及-

标签:枚举模拟

日期: 2026-06-19 00:55

题意

给定两个 8 位日期 date1 和 date2，要求统计闭区间 [date1, date2] 中有多少个真实存在的回文日期。

这里的“真实存在”指：

月份必须在 1..12
日期必须在当月的合法范围内
2 月还要区分平年和闰年

思路

先看一个最直接的朴素做法：

从 date1 开始一天一天往后推到 date2，每遇到一个真实日期，就判断它的 8 位表示是否回文。

这个做法很好理解，也方便拿来对拍：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99// brute.cpp：按天递增枚举区间里的每一个真实日期，直接判断是否回文。
#include <bits/stdc++.h>
using namespace std;

string left_date, right_date;

bool is_leap(int year) {
    if (year % 400 == 0) {
        return true;
    }
    if (year % 100 == 0) {
        return false;
    }
    return year % 4 == 0;
}

int days_in_month(int year, int month) {
    if (month == 1 || month == 3 || month == 5 || month == 7 ||
        month == 8 || month == 10 || month == 12) {
        return 31;
    }
    if (month == 4 || month == 6 || month == 9 || month == 11) {
        return 30;
    }
    if (month == 2) {
        if (is_leap(year)) {
            return 29;
        }
        return 28;
    }
    return 0;
}

void split_date(const string &s, int &year, int &month, int &day) {
    year = stoi(s.substr(0, 4));
    month = stoi(s.substr(4, 2));
    day = stoi(s.substr(6, 2));
}

string format_date(int year, int month, int day) {
    char buf[16];
    snprintf(buf, sizeof(buf), "%04d%02d%02d", year, month, day);
    return string(buf);
}

bool is_palindrome(const string &s) {
    for (int i = 0; i < 4; i++) {
        if (s[i] != s[7 - i]) {
            return false;
        }
    }
    return true;
}

void next_day(int &year, int &month, int &day) {
    day++;
    if (day <= days_in_month(year, month)) {
        return;
    }

    day = 1;
    month++;
    if (month <= 12) {
        return;
    }

    month = 1;
    year++;
}

void solve() {
    int year, month, day;
    int ans = 0;

    split_date(left_date, year, month, day);

    while (true) {
        string cur = format_date(year, month, day);
        if (is_palindrome(cur)) {
            ans++;
        }
        if (cur == right_date) {
            break;
        }
        next_day(year, month, day);
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> left_date >> right_date;
    solve();

    return 0;
}

但这题还有一个更关键的结构性质：

如果一个日期写成

yyyy mm dd

并且整个 8 位串是回文，那么它一定长成：

abcd dc ba

也就是说：

年份确定后，月份就被唯一确定为 dc
日期也被唯一确定为 ba

所以我们没必要在区间里把每一天都试一遍，只要枚举区间涉及到的每一个年份：

用年份反推出对应的 mm 和 dd
判断这个年月日是不是真实日期
再判断这个回文日期是否落在给定区间内

这样每年最多检查一次，复杂度就很小了。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#include <bits/stdc++.h>
using namespace std;

string left_date, right_date;

bool is_leap(int year) {
    if (year % 400 == 0) {
        return true;
    }
    if (year % 100 == 0) {
        return false;
    }
    return year % 4 == 0;
}

int days_in_month(int year, int month) {
    if (month == 1 || month == 3 || month == 5 || month == 7 ||
        month == 8 || month == 10 || month == 12) {
        return 31;
    }
    if (month == 4 || month == 6 || month == 9 || month == 11) {
        return 30;
    }
    if (month == 2) {
        if (is_leap(year)) {
            return 29;
        }
        return 28;
    }
    return 0;
}

bool is_valid_date(int year, int month, int day) {
    if (month < 1 || month > 12) {
        return false;
    }
    if (day < 1 || day > days_in_month(year, month)) {
        return false;
    }
    return true;
}

string format_date(int year, int month, int day) {
    char buf[16];
    snprintf(buf, sizeof(buf), "%04d%02d%02d", year, month, day);
    return string(buf);
}

void solve() {
    int start_year = stoi(left_date.substr(0, 4));
    int end_year = stoi(right_date.substr(0, 4));
    int ans = 0;

    for (int year = start_year; year <= end_year; year++) {
        // 回文日期一定形如 abcd dc ba。
        int month = (year % 10) * 10 + (year / 10) % 10;
        int day = (year / 100 % 10) * 10 + year / 1000;

        if (!is_valid_date(year, month, day)) {
            continue;
        }

        string cur = format_date(year, month, day);
        if (cur >= left_date && cur <= right_date) {
            ans++;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> left_date >> right_date;
    solve();

    return 0;
}

复杂度

设左右端点的年份分别是 Y1 和 Y2。

时间复杂度是 $O(Y2 - Y1 + 1)$ ，空间复杂度是 $O(1)$ 。

总结

这题的关键不是日期模拟本身，而是先看出“回文日期由年份唯一决定后四位”这个结构。

先利用结构把搜索空间大幅缩小，再做合法性判断，会比按天枚举更自然。

P2010 [NOIP 2016 普及组] 回文日期

题目背景

NOIP2016 普及组 T2

题目描述

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

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

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

一个 $8$ 位数字是回文的，当且仅当对于所有的 $i$ （ $1 \le i \le 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$ 天。

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

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

例如：

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

输入格式

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

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

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

保证 $\mathit{date}_1$ 和 $\mathit{date}_2$ 都是真实存在的日期，且年份部分一定为 $4$ 位数字，且首位数字不为 $0$ 。

保证 $\mathit{date}_1$ 一定不晚于 $\mathit{date}_2$ 。

输出格式

一个整数，表示在 $\mathit{date}_1$ 和 $\mathit{date}_2$ 之间，有多少个日期是回文的。

输入输出样例 #1

输入 #1

text

1
220110101
20111231

输出 #1

text

输入输出样例 #2

输入 #2

text

1
220000101
20101231

输出 #2

text

说明/提示

【样例说明】

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

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

【子任务】

对于 $60 \%$ 的数据，满足 $\mathit{date}_1 = \mathit{date}_2$ 。

[NOIP 2016 普及组] 回文日期

目录

题意

思路

代码

复杂度

总结