题目描述

直接思路就是两重循环枚举这两个年份之间的每天是否为回文日期，然后因为是日期问题，我们总会想到要不要判断闰年和平年，如果是闰年，就要遍历到29，如果是平年，就不要遍历到29，所以需要一个判断闰年的函数（这个问题学校教C语言的都学过，就不说了）.
然而实际上，我们是不需要判断闰年和平年的.理由如下：
首先，平2月的回文日期是82200228，闰2月的回文日期是92200229。如果两个日期之间要存在这么一个闰/平的回文日期，我们至多可以82200227开始，而82200228 和 92200229 两个日期都是大于左开区间82200227的，第二重循环遍历2月的日期从1开始，不考虑闰年判断的情况下，到29结束，
我们在遍历的过程中一定会经过这平月的82200228，这是不用判断平年的原因.
其次，因为回文日期是一个定值，年份定了月份也会定，只有92200229这个日期才会是闰的回文日期，不会说存在一个开区间，左平，右平，然后中间一个数符合92200229但又不是9220这一年..（我也不知道我自己在讲什么了..）

所以我们甚至连回文日期都不用去判断，我们构造出一个回文日期，如果这个日期在两个端点以内（不包括端点）就好了.
->打表 or 枚举

算法1

(打表) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
int date[400];
int main(){
    date[1]=10011001;
    date[2]=10100101;
    date[3]=10111101;
    date[4]=10200201;
    date[5]=10211201;
    date[6]=10300301;
    date[7]=10400401;
    date[8]=10500501;
    date[9]=10600601;
    date[10]=10700701;
    date[11]=10800801;
    date[12]=10900901;
    date[13]=11011011;
    date[14]=11100111;
    date[15]=11111111;
    date[16]=11200211;
    date[17]=11211211;
    date[18]=11300311;
    date[19]=11400411;
    date[20]=11500511;
    date[21]=11600611;
    date[22]=11700711;
    date[23]=11800811;
    date[24]=11900911;
    date[25]=12011021;
    date[26]=12100121;
    date[27]=12111121;
    date[28]=12200221;
    date[29]=12211221;
    date[30]=12300321;
    date[31]=12400421;
    date[32]=12500521;
    date[33]=12600621;
    date[34]=12700721;
    date[35]=12800821;
    date[36]=12900921;
    date[37]=13011031;
    date[38]=13100131;
    date[39]=13211231;
    date[40]=13300331;
    date[41]=13500531;
    date[42]=13700731;
    date[43]=13800831;
    date[44]=20011002;
    date[45]=20100102;
    date[46]=20111102;
    date[47]=20200202;
    date[48]=20211202;
    date[49]=20300302;
    date[50]=20400402;
    date[51]=20500502;
    date[52]=20600602;
    date[53]=20700702;
    date[54]=20800802;
    date[55]=20900902;
    date[56]=21011012;
    date[57]=21100112;
    date[58]=21111112;
    date[59]=21200212;
    date[60]=21211212;
    date[61]=21300312;
    date[62]=21400412;
    date[63]=21500512;
    date[64]=21600612;
    date[65]=21700712;
    date[66]=21800812;
    date[67]=21900912;
    date[68]=22011022;
    date[69]=22100122;
    date[70]=22111122;
    date[71]=22200222;
    date[72]=22211222;
    date[73]=22300322;
    date[74]=22400422;
    date[75]=22500522;
    date[76]=22600622;
    date[77]=22700722;
    date[78]=22800822;
    date[79]=22900922;
    date[80]=30011003;
    date[81]=30100103;
    date[82]=30111103;
    date[83]=30200203;
    date[84]=30211203;
    date[85]=30300303;
    date[86]=30400403;
    date[87]=30500503;
    date[88]=30600603;
    date[89]=30700703;
    date[90]=30800803;
    date[91]=30900903;
    date[92]=31011013;
    date[93]=31100113;
    date[94]=31111113;
    date[95]=31200213;
    date[96]=31211213;
    date[97]=31300313;
    date[98]=31400413;
    date[99]=31500513;
    date[100]=31600613;
    date[101]=31700713;
    date[102]=31800813;
    date[103]=31900913;
    date[104]=32011023;
    date[105]=32100123;
    date[106]=32111123;
    date[107]=32200223;
    date[108]=32211223;
    date[109]=32300323;
    date[110]=32400423;
    date[111]=32500523;
    date[112]=32600623;
    date[113]=32700723;
    date[114]=32800823;
    date[115]=32900923;
    date[116]=40011004;
    date[117]=40100104;
    date[118]=40111104;
    date[119]=40200204;
    date[120]=40211204;
    date[121]=40300304;
    date[122]=40400404;
    date[123]=40500504;
    date[124]=40600604;
    date[125]=40700704;
    date[126]=40800804;
    date[127]=40900904;
    date[128]=41011014;
    date[129]=41100114;
    date[130]=41111114;
    date[131]=41200214;
    date[132]=41211214;
    date[133]=41300314;
    date[134]=41400414;
    date[135]=41500514;
    date[136]=41600614;
    date[137]=41700714;
    date[138]=41800814;
    date[139]=41900914;
    date[140]=42011024;
    date[141]=42100124;
    date[142]=42111124;
    date[143]=42200224;
    date[144]=42211224;
    date[145]=42300324;
    date[146]=42400424;
    date[147]=42500524;
    date[148]=42600624;
    date[149]=42700724;
    date[150]=42800824;
    date[151]=42900924;
    date[152]=50011005;
    date[153]=50100105;
    date[154]=50111105;
    date[155]=50200205;
    date[156]=50211205;
    date[157]=50300305;
    date[158]=50400405;
    date[159]=50500505;
    date[160]=50600605;
    date[161]=50700705;
    date[162]=50800805;
    date[163]=50900905;
    date[164]=51011015;
    date[165]=51100115;
    date[166]=51111115;
    date[167]=51200215;
    date[168]=51211215;
    date[169]=51300315;
    date[170]=51400415;
    date[171]=51500515;
    date[172]=51600615;
    date[173]=51700715;
    date[174]=51800815;
    date[175]=51900915;
    date[176]=52011025;
    date[177]=52100125;
    date[178]=52111125;
    date[179]=52200225;
    date[180]=52211225;
    date[181]=52300325;
    date[182]=52400425;
    date[183]=52500525;
    date[184]=52600625;
    date[185]=52700725;
    date[186]=52800825;
    date[187]=52900925;
    date[188]=60011006;
    date[189]=60100106;
    date[190]=60111106;
    date[191]=60200206;
    date[192]=60211206;
    date[193]=60300306;
    date[194]=60400406;
    date[195]=60500506;
    date[196]=60600606;
    date[197]=60700706;
    date[198]=60800806;
    date[199]=60900906;
    date[200]=61011016;
    date[201]=61100116;
    date[202]=61111116;
    date[203]=61200216;
    date[204]=61211216;
    date[205]=61300316;
    date[206]=61400416;
    date[207]=61500516;
    date[208]=61600616;
    date[209]=61700716;
    date[210]=61800816;
    date[211]=61900916;
    date[212]=62011026;
    date[213]=62100126;
    date[214]=62111126;
    date[215]=62200226;
    date[216]=62211226;
    date[217]=62300326;
    date[218]=62400426;
    date[219]=62500526;
    date[220]=62600626;
    date[221]=62700726;
    date[222]=62800826;
    date[223]=62900926;
    date[224]=70011007;
    date[225]=70100107;
    date[226]=70111107;
    date[227]=70200207;
    date[228]=70211207;
    date[229]=70300307;
    date[230]=70400407;
    date[231]=70500507;
    date[232]=70600607;
    date[233]=70700707;
    date[234]=70800807;
    date[235]=70900907;
    date[236]=71011017;
    date[237]=71100117;
    date[238]=71111117;
    date[239]=71200217;
    date[240]=71211217;
    date[241]=71300317;
    date[242]=71400417;
    date[243]=71500517;
    date[244]=71600617;
    date[245]=71700717;
    date[246]=71800817;
    date[247]=71900917;
    date[248]=72011027;
    date[249]=72100127;
    date[250]=72111127;
    date[251]=72200227;
    date[252]=72211227;
    date[253]=72300327;
    date[254]=72400427;
    date[255]=72500527;
    date[256]=72600627;
    date[257]=72700727;
    date[258]=72800827;
    date[259]=72900927;
    date[260]=80011008;
    date[261]=80100108;
    date[262]=80111108;
    date[263]=80200208;
    date[264]=80211208;
    date[265]=80300308;
    date[266]=80400408;
    date[267]=80500508;
    date[268]=80600608;
    date[269]=80700708;
    date[270]=80800808;
    date[271]=80900908;
    date[272]=81011018;
    date[273]=81100118;
    date[274]=81111118;
    date[275]=81200218;
    date[276]=81211218;
    date[277]=81300318;
    date[278]=81400418;
    date[279]=81500518;
    date[280]=81600618;
    date[281]=81700718;
    date[282]=81800818;
    date[283]=81900918;
    date[284]=82011028;
    date[285]=82100128;
    date[286]=82111128;
    date[287]=82200228;
    date[288]=82211228;
    date[289]=82300328;
    date[290]=82400428;
    date[291]=82500528;
    date[292]=82600628;
    date[293]=82700728;
    date[294]=82800828;
    date[295]=82900928;
    date[296]=90011009;
    date[297]=90100109;
    date[298]=90111109;
    date[299]=90200209;
    date[300]=90211209;
    date[301]=90300309;
    date[302]=90400409;
    date[303]=90500509;
    date[304]=90600609;
    date[305]=90700709;
    date[306]=90800809;
    date[307]=90900909;
    date[308]=91011019;
    date[309]=91100119;
    date[310]=91111119;
    date[311]=91200219;
    date[312]=91211219;
    date[313]=91300319;
    date[314]=91400419;
    date[315]=91500519;
    date[316]=91600619;
    date[317]=91700719;
    date[318]=91800819;
    date[319]=91900919;
    date[320]=92011029;
    date[321]=92100129;
    date[322]=92111129;
    date[323]=92200229;
    date[324]=92211229;
    date[325]=92300329;
    date[326]=92400429;
    date[327]=92500529;
    date[328]=92600629;
    date[329]=92700729;
    date[330]=92800829;
    date[331]=92900929;
    int day1,day2,ans=0;
    cin>>day1>>day2;
    for(int i=1;i<=331;i++){
        if(day2>=date[i]&&day1<=date[i]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

作者：熠丶
链接：https://www.acwing.com/solution/AcWing/content/7628/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法2

(暴力枚举) $O(n^2)$

C++ 代码

/*日期问题要注意闰2月和平2月,如果是平月，只能是82200228，如果是闰月只能是92200229 如果
闰月和平月的回文日期是确定的
另外 由以上结论也知道 回文也是个幌子 如果月日确定了回文日期也就只能是唯一的，或者说年确定了，月日也只能是确定的
那么，给两个date,只要构造一个回文日期，去看是否在两个日期之间，是，就加1，不是就继续枚举
做题积累 一般把题目的区间看为开区间 
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>

using namespace std;

int d[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int n,m;
int res;

int main(){
    int ans;//回文日期
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= 12; i++){//月
        for(int j = 1; j <= d[i]; j++){//日
            ans = i * 100 + j + j % 10 * 10000000 + j / 10 * 1000000 + i % 10 * 100000 + i / 10 * 10000;
            //举一个特例就能找到怎么构造回文日期这个公式 例如10100101
            if(ans < n || ans > m) continue;
            res ++;
        }
    }

    printf("%d",res);
    return 0;
}