P8716【蓝桥杯 2020 省 AB2】回文日期
1. 从暴力枚举开始
这道题给出了一个八位数表示的日期，要求找到该日期之后：
- 第一个普通回文日期。
- 第一个
ABABBABA型的回文日期。
所谓回文日期，就是按照 yyyymmdd 格式表示时，从左往右和从右往左读取的数字完全相同。
例如 20200202，反转后仍然是 20200202，因此它是一个回文日期。
我一开始采用的是最直接的暴力枚举：从输入的日期开始，一直枚举到 99999999，判断每个数字是否满足回文条件。
不过，实际测试时这种写法超时了。
问题在于枚举范围太大。即使每次判断只需要很少的操作，几千万次循环累积起来，仍然会产生不小的时间开销。
那么，有没有办法不再逐个枚举日期，而是直接构造出可能满足条件的回文数呢？
2. 利用年份构造回文日期
观察八位回文日期的结构，可以发现一个规律：
只要确定了前四位年份，后四位就必须是年份的倒序。
例如，假设年份为 2012：
年份：2012
反转：2102
拼接后：20122102按照 yyyymmdd 的格式拆分：
2012 | 21 | 02
年份 月 日虽然 20122102 是一个八位回文数，但月份为 21，显然不是合法日期。
因此，构造出回文数只是第一步，还需要检查它能否表示一个真实日期。
对于任意一个四位年份，能够构造出的八位回文候选只有一个。
这样，我们就不需要从头到尾枚举所有八位整数，只需依次枚举年份，再将年份反转，拼接成对应的回文日期即可。
枚举范围从几千万个整数缩小到了几千个年份，效率自然会提高不少。
3. 判断日期是否合法
得到回文候选后，需要检查其中的月份和日期。
主要分为三种情况：
- 大月：1、3、5、7、8、10、12 月，每月最多 31 天。
- 小月：4、6、9、11 月，每月最多 30 天。
- 2 月：平年最多 28 天，闰年最多 29 天。
其中，闰年的判断条件为：
或者：
也就是说，年份能够被 4 整除但不能被 100 整除，或者能够被 400 整除，就属于闰年。
在代码中，我将日期合法性判断单独封装成 check() 函数。
这样，主循环只负责枚举年份、构造候选日期，再调用函数判断是否合法，整体逻辑会更加清晰。
4. 判断 ABABBABA 型回文日期
除了普通回文日期，题目还要求找出下一个 ABABBABA 型回文日期。
这种日期不仅需要满足回文条件，数字排列还必须符合下面的形式：
位置： 1 2 3 4 5 6 7 8
数字： A B A B B A B A其中，A 和 B 必须是两个不同的数字。
例如：
20200202其中 A = 2，B = 0，符合 ABABBABA 的排列规律。
因此，可以通过检查字符串中对应位置的字符是否相等，来判断一个合法回文日期是否属于这种特殊类型。
需要注意的是，ABABBABA 型日期本身也是普通回文日期。
所以，在枚举过程中，可以先记录遇到的第一个合法回文日期，然后继续寻找第一个符合 ABABBABA 条件的日期。
代码中的 flag 就是用来标记普通回文日期是否已经输出，避免后续重复输出。
如果遇到的第一个回文日期恰好也是 ABABBABA 型，那么它会同时作为两种答案输出。
5. 代码实现
Python 代码：
def check(year,month,day):
# 下面的判断是int型,传入的数据是str型,要进行转换.
year=int(year)
month=int(month)
day=int(day)
if month in [1,3,5,7,8,10,12]:
return 1<=day<=31
elif month in [4,6,9,11]:
return 1<=day<=30
elif month==2:
# 2月要判断一下是不是闰年.
if (year%4==0 and year%100!=0) or year%400==0:
return 1<=day<=29
else:
return 1<=day<=28
return False
# 输入初始数据
a=int(input())
# 获取年份
b=a//10000
# 在找ABABBABA型的回文日期的时候,可能会遇到多个普通的回文日期,但是我们输出最早的一个就行了,做个标记
flag=0
# 直接从b+1年开始遍历
for year in range(b+1,9999):
temp=str(year)[::-1]
month=temp[0:2]
day=temp[2:4]
# 获取完整的日期,方便打印和判断是否是ABABBABA型回文日期.
s=str(year)+str(month)+str(day)
if check(year,month,day):
if flag==0:
print(s)
flag=1
if s[0]==s[2]==s[5]==s[7] and s[1]==s[3]==s[4]==s[6] and s[0]!=s[1]:
print(s)
breakC++ 代码：
#include<iostream>
using namespace std;
#include<string>
#include<algorithm>
#include<unordered_set>
#define int long long
bool check(int year, int month, int day)
{
//利用集合来存储31天和30天的月份
unordered_set<int> us1{ 1, 3, 5, 7, 8, 10, 12 };
if (us1.find(month) != us1.end())return day >= 1 && day <= 31;
unordered_set<int>us2{ 4,6,9,11 };
if (us2.find(month) != us2.end())return day >= 1 && day <= 30;
if (month == 2)
{
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)return day >= 1 && day <= 29;
else return day >= 1 && day <= 28;
}
return false;
}
signed main()
{
ios::sync_with_stdio;
cin.tie();
int a; cin >> a;
int b = a / 10000;
bool flag = 1;
for (int year = b + 1; year < 9999; year++)
{
// to_string(),将数字转为字符串,需引入<string>库
string temp = (to_string(year));
//reverse(),反转容器,无返回值,需引入<algorithm>库
reverse(temp.begin(), temp.end());
//stoi(),将字符串转换为数字,需引入<string>库
int month = stoi(temp) / 100;
int day = stoi(temp) % 100;
string res = to_string(year) + temp;
if (check(year, month, day))
{
if (flag)
{
cout << res << endl;
flag = 0;
}
if ((res[0] == res[2] && res[0] == res[5] && res[0] == res[7]) && (res[1] == res[3] && res[1] == res[4] && res[1] == res[6]) && (res[0] != res[1]))
{
cout << res << endl;
break;
}
}
}
}两份代码的实现思路基本一致，只是在字符串处理上有所区别。
Python 可以直接通过切片 [::-1] 反转年份字符串，再利用切片提取月份和日期。
C++ 则使用了几个标准库提供的功能：
to_string()：将年份转换成字符串。reverse()：原地反转字符串中的字符。stoi()：将数字字符串转换成整数。unordered_set：存储大小月对应的月份，方便判断月份是否合法。
两份代码都通过一个标记变量记录是否已经输出第一个普通回文日期，随后继续寻找符合 ABABBABA 条件的日期。
6. 复杂度分析
假设需要枚举的年份数量为 Y。
对于每个年份，我们只需要完成字符串反转、日期合法性判断以及特殊回文格式检查。这些操作处理的都是固定长度的数据，因此单次检查的时间复杂度为 O(1)。
整个算法的时间复杂度为：
额外空间复杂度为 O(1)。
这道题的优化关键并不是让单次判断变得更快，而是利用回文数的结构，减少需要枚举的候选数量。
从逐个检查八位整数，改为只枚举年份并构造回文候选，避免了大量不可能满足条件的数字判断。
聊两句
评论审核后显示有疑问、补充，或者想交流一下，都可以写在这里。
评论区将在滚动到这里时加载。