BISHI20　回文日期¶

简单通过率 38.57%python3样例通过牛客 AC

讲解章节：模拟、回文

一句话

统计 [a,b] 内 YYYYMMDD 形式的回文日期个数。

解题思路¶

这题考什么¶

换一个枚举对象，把规模从「按天枚举」压到「按年枚举」。 8 位数是回文，等价于后四位必须是前四位的逆序；而前四位就是年份。所以一个年份最多只能产生一个回文日期：年份 y 写成 y1y2y3y4，唯一可能的回文日期就是 y1y2y3y4y4y3y2y1，即月份 MM = y4y3、日期 DD = y2y1。

年份只有 1000..9999 共 9000 个，逐个构造出候选日期，再检查「是否落在 [a,b] 内」「月份是否合法」「日期是否超过当月天数」即可。对照按天枚举的 9000 * 365 ≈ 330 万次判断，这里只有 9000 次，而且省掉了「日期加一天」这种最容易写错的逻辑。回文的更多写法见 72-回文。

数据规模与复杂度¶

O(9000)，与输入的区间大小无关，常数级。枚举上界固定写成 1000..9999 而不是从 a、b 推：8 位日期的年份必然是 4 位数，直接覆盖全部可能，再用区间判断过滤，比推导边界更不容易出错。

坑在哪¶

构造出来的月份可能根本不存在。年份 2000 构造出 20000002，月份是 00；年份 2002 构造出 20022002，月份是 20。必须显式判 1 <= m <= 12，再判 1 <= day <= 当月天数，两个都不能少；
闰年 2 月有 29 天，判定是「能被 4 整除且不能被 100 整除，或能被 400 整除」。四位年份里只有 9220 会构造出 2 月 29 日（92200229），9220 恰好是闰年，把 2 月一律按 28 天处理就会把它漏掉——这一个日期就足以让答案偏小；
区间是闭区间，两端都算，所以过滤条件写 d < a or d > b 才对，写成 <= 会漏掉恰好落在端点上的回文日期；
DAYS 表的下标从 1 开始（第 0 位填了占位的 0），直接用月份 m 取值即可，不要再 -1；
题面示例 2 的说明里写的 "20010002" 不是合法日期（月份为 00），该区间内真正的两个回文日期是 20011002 与 20100102。以输出的数字 2 为准。

样例复核¶

区间 [20110101, 20111231]：年份 2011 构造出 20111102，月份 11、日期 02 均合法且落在区间内，其余年份构造出的日期都不在区间内，答案 1，与样例一致。

参考实现¶

solutions/BISHI20.py
import sys

data = sys.stdin.buffer.read().split()
a, b = int(data[0]), int(data[1])

# DAYS[m] = 平年第 m 个月的天数，下标 0 是占位，使月份可以直接当下标用
DAYS = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

ans = 0
for y in range(1000, 10000):      # 8 位日期的年份必然是四位数，全部枚举一遍
    s = str(y)
    d = int(s + s[::-1])          # 唯一可能的回文日期
    if d < a or d > b:            # 闭区间，两端都要保留
        continue
    m, day = d // 100 % 100, d % 100      # 从 8 位数里切出月份和日期
    if not 1 <= m <= 12:          # 逆序拼出来的月份可能是 00、13..99
        continue
    lim = DAYS[m]
    if m == 2 and ((y % 4 == 0 and y % 100 != 0) or y % 400 == 0):
        lim = 29                  # 闰年 2 月多一天
    if 1 <= day <= lim:
        ans += 1
print(ans)

BISHI20 回文日期¶