NOPI2016普及组回文日期题解报告

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月份，最后2位代表日期。显然:一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道:在他指定的两个日期之间(包含这两个日期本身)，有多少个真实存在的日期是回文的。

【提示】

一个8位数字是回文的，当且仅当对于所有的i(1<i<8)从左向右数的第i个数字和第9-i个数字(即从右向左数的第i个数字)是相同的。
例如:
·对于2016年11月19日，用8位数字20161119表示，它不是回文的。
·对于2010年1月2日，用8位数字20100102表示，它是回文的。
·对于2010年10月2日，用8位数字20101002表示，它不是回文的。
每一年中都有12个月份: 其中，1, 3, 5, 7, 8, 10, 12月每个月有31天;4, 6, 9, 11月每个月有30天;而对于2月，闰年时有29天，平年时有28天。一个年份是闰年当且仅当它满足下列两种情况其中的一种: 1.这个年份是4的整数倍，但不是100的整数倍; 2.这个年份是400的整数倍。
例如:
·以下几个年份都是闰年:2000 , 2012 , 2016。
·以下几个年份是平年:1900, 2011、2014。

输入

输入包括两行，每行包括一个8位数字。
第一行表示牛牛指定的起始日期dates，第二行表示牛牛指定的终止日期date2。保证dates和date:都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0；保证date一定不晚于date2。

输出

输出一行，包含一个整数，表示在date1和date2之间，有多少个日期是回文的。

样例输入

复制样例数据

20110101
20111231

样例输出

这道题是一个纯粹的模拟题(在我看来)，我们可以观察到一个特征，因为该长度一定为偶数，所以一定是日期一定是与年份镜像对称的日期：

比如说 1234 年，哪一个日期是他的回文日期呢？即1234 4321，把1234反过来就可以，所以我们就有了思路，我们可以把年份拆开，比如1234 拆成 12 34，然而这并不是我们想要的日期，我们再观察一下就可以发现，我们想要的日期：43 21就是把后面那两位数翻转作为月份，把前面两位数作为年份，所以判断一个年份的回文日期，就是这么个步骤(也就是判断当年份为1234年时，43月21号存不存在)，或者确切的说：一个年份的回文日期只有一个。

然后再注意一下细节：

1.在我们判断这个日期存不存在的时候，可能会出现 43 21 即43月21号，我们这个时候需要打一个表（具体看注释）：

void set_table()
{
    memset(run,false,sizeof(run));
    memset(ping,false,sizeof(ping));
    for(int i=1;i<=12;i++)
    {
        if(i==2) continue;//二月单独出来
        for(int k=1;k<=31;k++)
            run[i][k]=ping[i][k]=true;
    }
    for(int i=1;i<=29;i++)
        run[2][i]=ping[2][i]=true;
    ping[2][29]=false;//平年29号不存在
    run[4][31]=ping[4][31]=false;//根据年份31天规律打表
    run[6][31]=ping[6][31]=false;
    run[9][31]=ping[9][31]=false;
    run[11][31]=ping[11][31]=false;
}

打完表之后，我们只需要判断当前年份是不是闰年，当前年份是闰年，并且run[mouth][day]==true，那么我们计数器就可以++了。但是这里需要注意数组开到 100 就够了，因为年份和日期无论怎么翻转最多都是两位数。

2.我们应该把开始年份和最后年份单独判断，因为这两年的日期不是满足run[mouth][day]==true就可以的，还需要比开始年份的日期大，比结束年份的日期小，但是在其中间的年份，因为所有月份都包含，所以我们可以直接判断，但这两个年份我们需要另加判断。

3.还有一种情况如果按 2 中的情况考虑，如果终止年份和开始年份相等，计数器会加两次，所以我们应该再分一种情况，即开始与终止年份相等的情况。

注意完细节，这个题也就可以AC了，总而言之，这个题我的思路有点偏，AC了也算是个大模拟了，后面会附上大佬的思路：

我的思路+代码注释：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#include <stdlib.h>
#include <time.h>
#include <sstream>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*坚持不懈，无懈可击*/
bool run[150][150];
bool ping[150][150];
bool check(int x)//判断闰年
{
    if((x%4==0&&x%100!=0)||x%400==0)
        return true;
    return false;
}
void set_table()//日期打表
{
    memset(run,false,sizeof(run));
    memset(ping,false,sizeof(ping));//这个时候不要忘记初始化
    for(int i=1;i<=12;i++)
    {
        if(i==2) continue;
        for(int k=1;k<=31;k++)
            run[i][k]=ping[i][k]=true;
    }
    for(int i=1;i<=29;i++)
        run[2][i]=ping[2][i]=true;
    ping[2][29]=false;
    run[4][31]=ping[4][31]=false;
    run[6][31]=ping[6][31]=false;
    run[9][31]=ping[9][31]=false;
    run[11][31]=ping[11][31]=false;//手写打表可是累死了 QAQ~
}
int main()
{
    set_table();
    int mouth,day;
    int tot=0;
    int sx,ex,sy,ey;
    scanf("%4d%d%4d%d",&sx,&sy,&ex,&ey);//格式化输入年份，方便数字之间的转换即日期大小判断
    mouth=((sx/10)%10)+(sx%10)*10;//将年份翻转成日期
    day=((sx/100)%10)*10+sx/1000;
    if(sx==ex)//开始与终止一样
    {
       // printf("%d ",mouth*100+day);
        if(mouth*100+day>=sy&&mouth*100+day<=ey)
        {
            if(check(sx)==true&&run[mouth][day]==true) tot++;
            if(check(sx)==false&&ping[mouth][day]==true) tot++;
        }
    }
    else
    {
        if(mouth*100+day>=sy)//要大于开始的月份
        {
            if(check(sx)==true&&run[mouth][day]==true) tot++;
            if(check(sx)==false&&ping[mouth][day]==true) tot++;
        }
        int mouth1,day1;
        mouth1=((ex/10)%10)+(ex%10)*10;
        day1=((ex/100)%10)*10+ex/1000;
        if(mouth1*100+day1<=ey)//把终止年份和开始年份，单独考虑
        {
            if(check(ex)==true&&run[mouth1][day1]==true) tot++;
            if(check(ex)==false&&ping[mouth1][day1]==true) tot++;
        }
        for(int i=sx+1;i<ex;i++)//不要考虑终止年份，与开始年份了！
        {
            int m,d;
            m=((i/10)%10)+(i%10)*10;
            d=((i/100)%10)*10+i/1000;
            if(check(i)==true&&run[m][d]==true) tot++;//这个时候不需要判断界限了，这个日期只要存在即可
            if(check(i)==false&&ping[m][d]==true) tot++;
        }
    }
    printf("%d\n",tot);
    return 0;
}

这种思路需要注意的细节挺多的，下面分享一个大佬的思路：

刚开始我们年份局限，只看到了日期对应年份，但是其实反过来想，更容易因为日期是优先的，我们首先对日期打表

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

然后遍历每一个月的每一个日期，把他倒过来看存不存在这个日期，到最后判断一下在不在题目给出的两个年份之间就可以了。

比如说 1031这个日期对应的年份为1301，我们只需要判断1301在不在该两个年份之间可以了。

这里还有一个细节：2月，2月闰年时有29天 0229 对应的日期为 9220 ，9220刚好是闰年，所以我们可以无所顾虑了。直接枚举每一个日期判断就可以了：

#include<iostream> 
#include<cstdio>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector> 
using namespace std;
int i,j,n,m,a,b,c,sum,ans;
int s[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=12;i++)//枚举月和日 
        for (j=1;j<=s[i];j++)
        {
            c=(j%10)*1000+
              (j/10)*100+
              (i%10)*10+
              (i/10);//算出前四位。
            sum=c*10000+i*100+j;//算出整个日期 
            if (sum<n||sum>m) continue;
            ans++;//统计 
        }
    printf("%d",ans);
    return 0;
}

从这一个思路就可以看出自己与别人的差距，所以要更加努力！加油！同时也希望大家一次AC！！