线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1974 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/468/ (opens in a new tab)
核心思想:
1、判断是否为回文
2、判断是否为合法的年月日
由于本题中输入数字只有8位,所以即使逐一判断是否为回文,复杂度也只有 ,比较勉强但可以一试。
判断字符串是否回文最简单的方法:
💡
即判断字符串与其 反向 组成的字符串是否相等。
或者先把字符串取反,然后比较。但由于 reverse函数会直接在原字符串上取反
,所以需要把取反前的做一个备份。
使用 reverse() 函数先把字符串取反
string str = to_string(date);
string s = str;
reverse(str.begin(), str.end());
if( str == s )
ans ++;
题解代码:
解法一
#include <bits/stdc++.h>
using namespace std;
int s, e, ans=0; // s 起始,e 结束
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool isLeap(int year) // 判断是否为闰年
{
return ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0);
}
bool check(int date)
{
int year = date / 10000;
int month = (date % 10000) / 100;
int day = date % 100;
if ( month == 0 || month >= 13 || day == 0 ) return false;
if ((month != 2) && (day > months[month])) return false;
if (month == 2)
{ // 闰年不能大于29天,非闰年不能大于28天
if(isLeap(year)) return day > 29 ? false : true;
else return day > 28 ? false : true;
}
return true;
}
void isPalindrome(int date)
{
if(check(date)) // 如果日期正确,则判断是否为回文
{
string str = to_string(date);
if( str == string(str.rbegin(), str.rend()) )
ans ++;
}
}
int main()
{
cin >> s >> e;
for(int i = s; i <= e; i++)
{
isPalindrome(i);
}
cout << ans << endl;
return 0;
}

以上是解法一的运行结果,虽然AC,但是后面几个测试点时间太长了。需要优化。
本题考点:
字符串的回文判断 str == string(str.rbegin(), str.rend()) 或者 先反向构造 回文字符串,再比对 是否在合法的区间范围内
🚫
信奥中有不少题目 如果正向枚举会超时,就尝试先反向构造数据,再枚举 构造后的数据 是否 在 合理范围内。