题解 P2010 【回文日期】

· · 题解

这个题目已经非常宽容了，如果你掌握了回文数的计算方法，你至少能得 60 分，当然看完这篇文章你就可以得 100 分了。（awa

那就直入主题吧，每个题目都可能有多种解法，你选择的切入点决定了你使用的解法的复杂度。对这个题来说，枚举是免不了的，重点是怎么枚举。

枚举年

区间内的年比较少，对于某一年来说，比如 2019，我们只需要判断 9102 是否是合法的月和日就行了。

在这个思想的指引下，先把两个日期中间的所有年筛选出来，同时求出年份的回文数。 

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

int main()
{
    int date1,date2,year1,year2;
    cin >> date1 >> date2;
    year1 = date1 / 10000;
    year2 = date2 / 10000;
    //遍历范围内的所有年份
    for(int year = year1;year<=year2;year++) {

    }
    return 0;
}

顺着这个思路，主要的任务是根据 year 求出完整的当前year的回文日期，比如命名为 aim_year ,写出的完整代码如下 

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

int main()
{
    //变量着实是有点多
    int date1,date2,year1,year2,fan_year,aim_date,tmp_year,month,day,cnt=0;
    // 2月份直接用 29 天，因为0229反过来9220，9220是闰年，满足题意
    int days[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
    cin >> date1 >> date2;
    year1 = date1 / 10000;
    year2 = date2 / 10000;
    //遍历范围内的所有年份
    for(int year = year1;year<=year2;year++) {
        //生成回文年的时候不能直接修改year，所以用临时变量tmp_year
        tmp_year = year;
        fan_year = 0;
        //先生成年的回文年
        for(int i = 1;i<=4;i++) {
            fan_year = tmp_year%10 + fan_year*10;
            tmp_year /= 10;
        }
        //把回文年拆成月和日
        month = fan_year/100;
        day = fan_year%100;
        //aim_date 是组合出的当前年份的完整回文日期
        aim_date = year*10000+month*100+day;
        //月份得合法,日得合法，同时生成的回文日期得在给定的范围内
        if(month <= 12 && month>=1 && day <= days[month] && aim_date >=date1 && aim_date <= date2){
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}

枚举月和日

另一种方法是直接枚举合法的月和日，组成所有回文日期，判断完整的日期是否在给定的日期范围内即可。 

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

int main()
{
    int date1,date2,fan_year,tmp_year,year,aim_date,cnt=0;
    int days[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
    cin>>date1>>date2;
    //枚举所有合法的月和日
    for (int month=1;month<=12;month++)
        for (int day =1;day<=days[month];day++)
        {
            fan_year= month*100+day;
            tmp_year = fan_year;
            year = 0;
            //根据回文年生成原本的年
            for(int i = 1;i<=4;i++) {
                year = tmp_year%10 + year*10;
                tmp_year /= 10;
            }
            //生成完整的回文日期
            aim_date = year*10000 + fan_year;
            //好处是这次不用判断月和日是否合法了
            if(aim_date >= date1 && aim_date <= date2)
                cnt++;
        }
    cout<<cnt;
    return 0;
}

通过对比可以发现，枚举年的时候只有一层循环，但是判断条件复杂，枚举月日时需要写嵌套循环，但是条件简单。