tag: 枚举

思路1

根据年份，构造回文日期，用check函数判断。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<int, int> mp = {{1, 31}, {3, 31}, {4, 30}, {5, 31}, {6, 30}, 
                              {7, 31}, {8, 31}, {9, 30}, {10, 31}, {11, 30},
                              {12, 31}};

string a, b;
int ay, am, ad, by, bm, bd;

// 按符合题意的条件以及日期构造常识判断
bool check(int y, int m, int d) {
    if (m > 12 || m == 0) return false;
    if (d == 0 || d > 31) return false;
    if (y == ay) {
        if (am > m) return false;
        else if (am == m && d < ad) return false;  
    }
    if (y == by) {
        if (m > bm) return false;
        else if (bm == m && d > bd) return false;
    }
    if (m == 2) {
        return (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) ? d <= 29 : d <= 28;
    } else {
        return d <= mp[m];
    }
    return true;
}

int main() {
    cin >> a >> b;
    ay = stoi(a.substr(0, 4)), am = stoi(a.substr(4, 2)), ad = stoi(a.substr(6, 2));
    by = stoi(b.substr(0, 4)), bm = stoi(b.substr(4, 2)), bd = stoi(b.substr(6, 2));
    int ans = 0;
    for (int y = ay; y <= by; y ++ ) {
        string t = to_string(y);
        reverse(t.begin(), t.end());
        int m = stoi(t.substr(0, 2)), d = stoi(t.substr(2));
        if (check(y, m, d)) ans ++ ;
    }
    cout << ans << endl;
    return 0;
}

思路2

可以看出，通过年份来构造日期，还要判断日期超出范围和年份为闰年等，十分复杂。而通过月日构造回文日期，可以避免复杂的合法日期的判断，操作数大概为12*31，满足题目时间要求。

注意到，当m=2时，02回文构造为20，显然是4的整数倍，不是100的整数倍，所以构造的一定是闰年，m[2]可以直接写29。

#include <iostream>
using namespace std;
 
int m[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31};

int main() {
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = 1; i <= 12; i ++ )
        for (int j = 1; j <= m[i]; j ++ ) {
            int x = (j % 10) * 1e7 + (j / 10) * 1e6 + (i % 10) * 1e5 + (i / 10) * 1e4 + 
                i * 100 + j;
            if (x >= a && x <= b) cnt ++ ;
        }
    cout << cnt << endl;
}