算法标签:枚举
题目链接:OpenJudge - 044:j162 回文日期【问题描述】 在日常生活中,通过年、月、日这三个要素可以表示出一个唯一确定的日期。 牛牛习惯用 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。【输入格式】从文件 date.in 中读入数据。输入包括两行,每行包括一个 8 位数字。第一行表示牛牛指定的起始日期 date1。第二行表示牛牛指定的终止日期 date2。保证 date1 和 date2 都是真实存在的日期,且年份部分一定为 4 位数字,且首位数字不为 0。保证 date1 一定不晚于 date2。【输出格式】输出一行,包含一个整数,表示在 date1 和 date2 之间,有多少个日期是回文的。【样例 1 输入】2011010120111231【样例 1 输出】1【样例 2 输入】2000010120101231【样例 2 输出】2【样例说明】对于样例1,符合条件的日期是 20111102。对于样例2,符合条件的日期是 20011002 和20100102。【子任务】对于 60% 的数据,满足 date1=date2。解法一:30分代码由于有 60% 的数据 date1=date2,即判断这一天是否是回文数,若是,则输出 1,若不是,则输出 0。如果概率均等,则本题直接输出 0 或 1 可以拿 30 分。解法二:60分代码(根据题目最后说明,有 60% 的数据 date1=date2,故只需判断date1是否回文数即可)
#include<iostream>using namespace std;int d1,d2,d;int main() { cin>>d1>>d2; while (d1>0) { //将 date1 反转存入变量 d 中 d=d*10+d1%10; d1/=10; } if (d==d2) cout<<1; else cout<<0; return 0;}解法三:枚举 date1 至 date2 之间的所有年份
#include<iostream>using namespace std;int d1,d2,t,ans;bool rn(int y){ //判断闰年 if (y%4==0 && y%100!=0 || y%400==0) return 1; return 0;}bool ch(int s) { //判断8位数字的日期是否合法 int m,d; m=s/100%100;d=s%100; //提取这个日期的月份和日期,下面分大月、小月和 2 月 3 种情况讨论 if ((m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12) && d<32) return 1; if ((m==4 || m==6 || m==9 || m==11) && d<31) return 1; if (m==2 && (d<29 || rn(s/10000) && d<30)) return 1; return 0; //如果月份不是介于1至12之间,则不合法}bool hw(int r) { t=r*10000+r%10*1000+r%100/10*100+r/100%10*10+r/1000; //通过将年份反转,构造出1个8位数字的日期 if (t>=d1 && t<=d2 && ch(t)) return 1; //判断这个日期是否在d1、d2范围内,且合法 return 0;}int main() { cin>>d1>>d2; //每个年份反转后对应的日期只有一天,下面从d1对应的年份枚举到d2对应的年份一一判断 for (int i=d1/10000;i<=d2/10000;i++) if (hw(i)) ans++; cout<<ans; return 0;}解法四:枚举日期,由一年中的所有日期反转来构造8位数PS:0229对应该的年份为9220,是闰年,所以不需要再另外判断闰月
#include<iostream>using namespace std;int d1,d2,t,ans;int s[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};int main() { cin>>d1>>d2; for (int i=1;i<=12;i++) for (int j=1;j<=s[i];j++) { //枚举一年当中的每一天 t=(j%10)*10000000+(j/10)*1000000+(i%10)*100000+(i/10)*10000+i*100+j; if (t<=d2 && t>=d1) ans++; } cout<<ans; return 0;}


