♐ CSP_J 组真题
2016年
2. 回文日期

线上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位,所以即使逐一判断是否为回文,复杂度也只有 O(108)O(10^8),比较勉强但可以一试。

判断字符串是否回文最简单的方法:

💡

str==string(str.rbegin(),str.rend())str == string(str.rbegin(), str.rend())

即判断字符串与其 反向 组成的字符串是否相等。

或者先把字符串取反,然后比较。但由于 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()) 或者 先反向构造 回文字符串,再比对 是否在合法的区间范围内

🚫

信奥中有不少题目 如果正向枚举会超时,就尝试先反向构造数据再枚举 构造后的数据 是否合理范围内。