CSP历年复赛题-P2010 [NOIP2016 普及组] 回文日期

原题链接：https://www.luogu.com.cn/problem/P2010

题意解读：计算两个日期之间有多少个日期是回文。

解题思路：

如果通过枚举两个日期之间的所有日期，然后判断回文，则会有几个问题：

枚举数据规模在10^7级别，再加上对于日期加一天、判断回文等处理，有可能超时，而且对日期进行加一天、判断回文等操作都比较麻烦。

换一种枚举思路：

由于年开头数字不为0，年的范围是1000~9999，如果是回文日期，日期的年部分翻转后就是月日部分

所以只需要枚举年：1000~9999，就可以产生所有的可能的回文日期

但是对于一个年，翻转后生成的日期不一定是一个有效日期（开始日期<=日期<=结束日期，1<=月<=12，1<=日<=年月对应的最大天数）

因此，只需要将所有年进行翻转，然后和年拼接生成一个日期，判断该日期是否有效，如果有效就是一个

100分代码：

#include <bits/stdc++.h>
using namespace std;

int date1, date2;
int ans;

int month_days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

//把整数年y转为string（如果不记得to_string()函数）
string itostr(int y)
{
    string res;
    res += y / 1000 + '0';
    res += (y / 100) % 10 + '0';
    res += (y / 10) % 10 + '0';
    res += y % 10 + '0';
    return res;
}

//把字符串转为整数（如果不记得系统stoi()函数）
int strtoi(string s)
{
    int res = 0;
    for(int i = 0; i < s.size(); i++)
    {
        res = res * 10 + s[i] - '0';
    }
    return res;
}

//判断year是否是闰年
bool isleap(int year)
{
    return year % 100 != 0 && year % 4 == 0 || year % 400 == 0;
}

//获取year年month月的天数
int getdays(int year, int month)
{
    if(isleap(year))
    {
        int days = month_days[month];
        if(month == 2) days++;
        return days;
    }
    else return month_days[month];
}

//检查日期是否有效
bool check(int date)
{
    if(date < date1 || date > date2) return false;
    int year = date / 10000;
    int month = (date / 100) % 100;
    int day = date % 100;
    if(month < 1 || month > 12) return false;
    if(day < 1 || day > getdays(year, month)) return false;
    return true;
}

int main()
{
    cin >> date1 >> date2;
    for(int i = 1000; i <= 9999; i++)
    {
        string year = itostr(i); 
        string date = year;
        for(int i = 3; i >= 0; i--) date += year[i]; //年翻转，拼接 
        int dt = strtoi(date);
        if(check(dt)) ans++;
    }
    cout << ans;

    return 0;
}