蓝桥杯2020年第十一届省赛真题-回文日期python两种方法题解（贪心+datetime）

题目

原题链接：回文日期 - 蓝桥云课 (lanqiao.cn)

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入描述

输入包含一个八位整数 N，表示日期。

对于所有评测用例，10000101≤N≤89991231，保证 N 是一个合法日期的 8 位数表示。

输出描述

输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

输入输出样例

示例

20200202

20211202
21211212

 datetime遍历

使用python标准库中的datetime库可以很方便地处理有关日期类问题的遍历。

import datetime

N=input()
year=int(N[:4])
month=int(N[4:6])
day=int(N[6:])

cur_date=datetime.date(year,month,day)
had_print_once=False # 已输出回文日期
while True:
    cur_date=cur_date+datetime.timedelta(days=1)
    str_date=str(cur_date).replace('-','')
    if str_date==str_date[::-1]:
        if not had_print_once:
            had_print_once=True
            print(str_date)
        if str_date[0]==str_date[2] and str_date[1]==str_date[3]:
            print(str_date)
            break
        

贪心

此方法求出的局部最优解就是全局最优解，复杂度为O（1），比赛的时候不推荐使用，把简单的问题复杂化了，不过平时玩玩图一乐挺好。

代码主要由分成两部分：找下一个回文日期和找下一个ABABBABA 型的回文日期。

先说下一个ABABBABA 型的回文日期，这个比较简单。通过观察可以发现，由于受月份限制，BA的组合一共有十二个，分别为01到12。把这些组合里的数字倒序，之后对这些组合进行排序得到AB的有序组合。对AB有序组合里的元素进行遍历，可求出目标回文日期。

再说找下一个回文日期。程序简图如图1：

图1

其中贪心策略求最小年份的过程见图2。其中第一次判倒转日是否修改使用的是>31这个条件，所以后续判断月是否要修改的时候，无论月有没有改变使日要”进位“,都需要通过已确定的月份用新的约束判断日是否需要修改。

再者说，二月份的天数限制定为28是可行的。为什么呢？首先，题目给了N≤89991231，所以不会出现倒转后天数的个位数为9的情况。会出现倒转后天数为9的情况，只有当日的个位数为8，又不是合法日期的情况，此时日变为”09“，不可能出现29。所以，二月份天数限制为28是可行的。

图2 

def gen_ABABBABA(AB):
    return AB+AB+AB[::-1]+AB[::-1]

N=input()
li=list(N)#列表是可变类型，通过列表储存N的各位

# 输入的N是回文数，需要使它变成最小的非回文数，此时不需要考虑合法性
if li[:4]==li[-1:3:-1]:
    li[-1]=str(int(li[-1])+1)

# 寻找下一个最小的回文数

# 判断N前四位倒转后是否比后四位大
if int("".join(li[:4]))<int("".join(li[-1:3:-1])):
    li[3]=str(int(li[3])+1)

# 判断合法
had_change=False
rev_first_four=li[:4]
rev_first_four.reverse()
# 先判断倒转后的日
raw_bound_day=31
if int("".join(rev_first_four[2:4]))>raw_bound_day:
    rev_first_four[2]='0'
    rev_first_four[3]=str(int(rev_first_four[3])+1)
    had_change=True
if had_change:
    rev_first_four[0]='1'
    rev_first_four[1]='0'
else:
    if int("".join(rev_first_four[0:2]))>12:
        rev_first_four[0]='0'
        rev_first_four[1]=str(int(rev_first_four[1])+1)
        if int(rev_first_four[1])==10:
            rev_first_four[1]='0'
            rev_first_four[2]=str(int(rev_first_four[2])+1)
    if int("".join(rev_first_four[0:2]))==0:
        rev_first_four[0]='1'

    days=[0,31,28,31,30,31,30,31,31,30,31,30,31] # 每月天数
    bound_day=days[int("".join(rev_first_four[0:2]))]# 当前月天数限制
    if int(rev_first_four[2])==10:
        rev_first_four[2]='0'
        rev_first_four[3]=str(int(rev_first_four[3])+1)
    if int("".join(rev_first_four[2:4]))>bound_day:
        rev_first_four[2]='0'
        rev_first_four[3]=str(int(rev_first_four[3])+1)

print("".join(rev_first_four[::-1])+"".join(rev_first_four[:]))

# 寻找下一个ABABBABA型的回文日期
BA=[str(i).zfill(2) for i in range(1,13)];
AB=[i[::-1] for i in BA]
AB.sort()
raw_year_first_two=int("".join(li[:2]))
for snum in AB:
    if int(snum)<raw_year_first_two:
        continue
    if int(snum)==raw_year_first_two:
        if int(gen_ABABBABA(snum))>int("".join(li)):
            print(gen_ABABBABA(snum))
            break
    else:
        print(gen_ABABBABA(snum))
        break