洛谷 NOIP2016 普及组 回文日期

这道题目本来是不难想思路的。。。。。。

然而我第一次做的时候改了蛮久才把代码完全改对，主要感觉还是不够细心，敲的时候也没注意见检查一些小错误，那么接下来不说废话，请看题干：

接下来请看输入输出的样例以及数据范围：

?

我提供两个方法去做这个题，第一个思路是：

首先我们分析容易看出输入的日期其实当作两个八位数处理即可，然后直接循环，从起始日期到截止日期，如果是回文日期，直接ans++即可，只是我们需要思考如何来让日期进行正确的进位，所以这时候我考虑使用函数来达到目的的功能，接下来请看代码：

#include<bits/stdc++.h>
using namespace std;
int d1,d2,ans;
int getday(int y,int m){
	//y年m月有多少天
	if(m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12)
	return 31;
	if(m==4 || m==6 || m==9 || m==11)
    return 30;
    //判断闰年
    if(( !(y%4) && y%100) || !(y%400))
    return 29;
    else 
	return 28;
}
int nextday(int x){
	//x的下一天  表示为八位整数
	int y=x/10000;
	int m=x/100%100;
	int d=x%100;
	if(d != getday(y,m))
	++d;
	else if(m!=12){
		++m;
		d=1;
	}
	else {
		y+=1;
		m=1;
		d=1;
	}
	return 10000*y+100*m+d;
}
int rev(int x){
	int ans=0;
	while(x){
		ans=ans*10+x%10;
		x/=10;
	}
	return ans;
}
int main(){
	scanf("%d%d",&d1,&d2);
	for(int d=d1;d<=d2;d=nextday(d)){
		if(d == rev(d)) ans++;
	}
    printf("%d\n",ans);
	return 0;
}

?看起来很长其实也并不复杂，写了几个函数，第一个函数是判断对应的月份有多少天，第二个是判断循环中的下一天的日期，第三个循环判断翻转数字是否与一开始的一样，也就是判断回文数，然后就是很简单的输入和枚举，相信不必进行解释了。

接下来我就在思考，很明显一开始的方法还是进行了很多不必要的循环，两个回文日期的间隔一般是比较大的，所以有很多不必要的循环，也就是我考虑如何降低循环的次数，同时也能降低时间复杂度，接下来请看代码：

#include<bits/stdc++.h>
using namespace std;
int d1,d2,ans;
int getday(int y,int m){
	//y年m月有多少天
	if(m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12)
	return 31;
	if(m==4 || m==6 || m==9 || m==11)
    return 30;
    //判断闰年
    if(( !(y%4) && y%100) || !(y%400))
    return 29;
    else 
	return 28;
}
int nextday(int x){
	//x的下一天  表示为八位整数
	int y=x/10000;
	int m=x/100%100;
	int d=x%100;
	if(d != getday(y,m))
	++d;
	else if(m!=12){
		++m;
		d=1;
	}
	else {
		y+=1;
		m=1;
		d=1;
	}
	return 10000*y+100*m+d;
}
int rev(int x){
	int ans=0;
	while(x){
		ans=ans*10+x%10;
		x/=10;
	}
	return ans;
}
int main(){
	scanf("%d%d",&d1,&d2);
    for(int y=1000;y<=9999;y++){
    	int revy=rev(y);
    	int m=revy/100;
    	int d=revy%100;
    	if(m>=1 && m<=12 && d>=1 && d<=getday(y,m)){
    		int x=y*10000+revy;
    		if(x>=d1 && x<=d2) ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

这个方法就是将年份进行了循环，从1000循环到9999年，每次循环先判断出是否是回文年份并且这个回文年份是否在输入的起始日期和截止日期之间，如果在，那么就可以ans++，这是因为我们可以发现日期是一个八位数字，并且由于年份、月份和日子都不可以为0，所以我们其实可以把年份看成特殊进位的数字，进而只需要循环一万次不到就可以得到结果。