题目链接：P2010 [NOIP 2016 普及组] 回文日期 - 洛谷

1.题目分析

2.算法原理

策略一:枚举 x~y之间所有的数字，然后判断是否回文。如果回文，那就拆分成年月日，判断是否是合法日期即可

策略二:仅需枚举年份。然后拆分成回文形式的月日，然后判断是否合法即可

针对某一个年份而言，能够构成回文的只有一个，比如当前的年份是2000年，一旦前四个数确定，那他后面的数必定是0002，如果前面是回文日期的话，从前读从后堵都是一样的才能构成回文，也就是确定好一个年份的话，对应的月日只有一个，所以针对某一个年份，只能找出一个月一个日来和它构成回文，可以枚举所有的年份 ，比如2000-2024，此时只要枚举2000到2024的年份，枚举到2023的时候，把2023对应的32月2日，判断是否是一个合法的月日就可以了，刚刚我们需要枚举2e7，现在只枚举年份的话，最多每局2e3，时间复杂度一下就降2e4

策略三:枚举所有的月和日的组合，然后拼接成相应的年份，判断是否合法

月份是一月到12月，日期的日期是一月到31日，我们可以用两层for循环，第一层复循环枚举月，第二层for循环枚举到31，如果枚举是4月的话，第二层枚举到30就可以了，此时就可以把所有的月日组合给枚举出来，当枚举好一个月以及一个日这样的组合之后，我只要把对应的年份还原出来就可以了，比如月日是1231，还原1321的年份就可以了，判断一下这样的日期是否再给定的x-y的范围内就可以了，给定的数字大于等于X且小于等于Y，说明此时的数是一个合法日期，让count++就可以了，如果枚举出来的数字在x左边或y右边，说明虽然这里是一个回文日期，但它不在题目给定的数据范围内，所以此时不让count++就可以了，这个时间复杂度是更低的，撑死就是4e2

如何根据7月21日还原出它所回文的年份，假设枚举的月份数字是 i 枚举的日为 j ，它的数字为0721，最终把它还原成1270，0还原到年份的个位，7还原到年份的十位，2到百位，1到千位，怎么找到千位1，拿刚刚日份对应的数字是 j ，j%10，就会找到1，×1000，就到千位的位置了，拿刚刚的 j，j/10，找到2，×100，就提到百位上了，i%10，找到7，乘10，放到十位，i/10，放到个位，最后把4个数加起来就拼成了1270，假设k=1270，如何拼成12700721，k乘一万，也就是让它后面多四个0，+i × 100 + j，就拿到12700721了，再拿这个数字和xy作比较就可以了

代码（策略二）：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int days[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int main() {
    int x, y;
    cin >> x >> y;

    int count = 0;
    for (int year = 1000; year <= 9999; year++) {
        //翻转年份得回文月日
        string s = to_string(year);
        reverse(s.begin(), s.end());

        //月日
        int md = stoi(s);
        //年月日拼在一起判断合法范围
        int date_num = year * 10000 + md;
        if (date_num < x || date_num > y) continue;

        int yyyy = date_num / 10000;
        int m = md / 100;
        int d = md % 100;

        if (m < 1 || m > 12) continue;
        int max_d = days[m];

        if (d < 1 || d > max_d) continue;

        count++;
    }

    cout << count << endl;
    return 0;
}

代码（策略三）：

#include <iostream>
using namespace std;

int x, y;
//0229可以枚举到对应的92200229
int day[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int main()
{
    cin >> x >> y;

    int ret = 0;

    // 枚举月日的组合
    for (int i = 1; i <= 12; i++)
    {
        for (int j = 1; j <= day[i]; j++)
        {
            int k = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;
            int num = k * 10000 + i * 100 + j;
            if (x <= num && num <= y)
            {
                cout << num << endl;
                ret++;
            }
        }
    }

    cout << ret << endl;

    return 0;
}