先贴个题目:
以及原题链接:466. 回文日期 - AcWing题库https://www.acwing.com/problem/content/468/
这题乍一看有点恶心,如果枚举日期还要判断合法性,然后每个日期再判断是不是回文,即麻烦,时间复杂度又高,
代码我写了一份:
#include <iostream>
using namespace std;int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{int d1, d2;cin >> d1 >> d2;int ans = 0;for (int i = d1; i < d2 + 1; ++i){int x = i, tmp = i, y = 0;x /= 10000;for (int i = 0; i < 4; ++i){y = y * 10 + tmp % 10;tmp /= 10;}int sign = 0;if (y == x){int mouth = i % 10000 / 100;int days = i % 100;if (mouth != 2 && days <= day[mouth] && days > 0)sign = 1;else if (mouth == 2){if ((y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)) && days <= 29 && days > 0)sign = 1;else if (days <= 28 && days > 0)sign = 1;}}if (sign)ans++;}cout << ans;return 0;
}
tle麻了。那有什么办法可以减少计算量呢,我们发现回文的日期就是月日和年回文,而年是从1000-9999,也就是说只要枚举年,找到相应的回文日期,然后判断是不是合法就行了。
代码如下:
#include <iostream>
using namespace std;int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{int d1, d2;cin >> d1 >> d2;int ans = 0;for (int i = 1000; i < 10000; ++i){int x = i, tmp = i, y = 0, sign = 0;while (tmp){y = y * 10 + tmp % 10;tmp /= 10;}x = x * 10000 + y;if (x >= d1 && x <= d2){int month = y / 100;int days = y % 100;int year = x / 10000;if (month > 0 && month < 13 && days > 0){if (month != 2 && days <= day[month])sign = 1;else if (month == 2){if (year % 400 == 0 || year % 100 != 0 && year % 4 == 0)if (days <= 29)sign = 1;else if (days <= 28)sign = 1;}if (sign){ans++;}}}}cout << ans << endl;return 0;
}
就这样吧。
by———2024.2.28刷题记录