栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > 资讯 > 高等教育 > 考研政策

NOIP 2016 J2 回文日期 解题报告

NOIP 2016 J2 回文日期 解题报告

算法标签:枚举

题目链接: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;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/news/1538963.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号