一、题目背景
本题为2020年省赛填空题
- C/C++A组第7题
- C/C++B组第7题
- Java A组第7题
二、题目描述
1.问题描述
2020 年春节期间，有一个特殊的日期引起了大家的注意: 2020 年 2 月 2日。因为如果将这个日期按“yyyymmdd”的格式写成一个8 位数是20200202,恰好是一个回文数。我们称这样的日期是回文日期。
有人表示 20200202 是“千年一遇”的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期: 20211202 即 2021年12月2日
也有人表示20200202 并不仅仅是一个回文日期，还是一个 ABABBABA型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个ABABBABA型的回文日期: 21211212即 2121 年12月12日。算不上“千年一遇”，顶多算“千年两遇”。
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA 型的回文日期冬是哪一天。
2.输入格式
输入包含一个八位整数 N，表示日期。
3.输出格式
输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下个 ABABBABA 型的回文日期。
4.一个例子
下面是一个样例 输入：
20200202
输出：
20211202
21211212
5. 评测用例规模与约定
对于所有评测用例，10000101 ≤ N ≤ 89991231，保证 N 是一个合法日期的8位数表示。
运行限制
- 最大运行时间：
1s - 最大运行内存:
256M
三、题目分析
和2021省赛的卡片题目一样，如果我们有办法将所有回文日期的八位数全部枚举出来，是不是就可以解决问题了呢？现在问题就转化为：怎样枚举和怎样检查。
我们仔细观察一下两种回文日期的格式。
第一种：20211202
第二种：21211212
我们可以设置下标从0~7的数组，代表日期的每一位数字的大小。
那么对于第一种回文日期，只需要满足如下条件
a[0]==a[7];
a[1]==a[6];
a[2]==a[5];
a[3]==a[4];
对于第二种回文日期（ABABBABA型），只需要满足如下条件
a[0]==a[2]==a[5]==a[7];
a[1]==a[3]==a[4]==a[6];
1.获取位数
利用取余的方法获取每一位的位数，如果不会的可以看下2021省赛-卡片。
//获取日期每一位的位数
void digit(int date, int a[],int N)
{
for (int i = 0; i < N; i++)
{
a[N - 1 - i] = date % 10;
date = date / 10;
}
}
2.回文检查
依旧以C语言写回文日期的检查代码。 注意：C语言中没有bool类型和String类型。 C++代码也会放在后面，但是整体思路一样。
检查第一种回文日期
int check_1(int a[])
{
if (a[0] == a[7] && a[1] == a[6] &&
a[2] == a[5] && a[3] == a[4])
return 1 ;
return 0;
}
检查第二种回文日期
int check_2(int a[])
{
if (a[0] == a[2]&& a[0] == a[5] && a[0] == a[7] &&
a[1] == a[3]&& a[1] == a[4] && a[1] == a[6])
return 1 ;
return 0;
}
3.枚举限制
可能会有很多人写出下面的枚举情况
int input;
scanf("%8d",&input);
for (int i = input; i <= 89991231; i++)
{
digit(i, a，8);
if (check_1(a) || check_2(a))
printf("%d\n",i);
}
其实这样确实可以枚举出答案，但是，这样枚举不符合题目的标准。并且也会枚举出大量不是日期但符合回文标准的数字。
所以，我们应该对枚举的数也进行检查，要求限制它必须为有效的年月日。
进行日期限制
一年只有12个月，每个月的天数都不同，所以可以用12个数组来模拟每一个月的天数，这样只需要判断月份是不是属于1~12，天数是不是符合当前月份的天数。 但是，这里 有个小坑，那就是闰年！闰年的二月天数是29天，而不是28天。
int check_3(int a[])
{
int day[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 }; //(1)
int y = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3]; //(2)
int m = a[4] * 10 + a[5]; //(3)
int d = a[6] * 10 + a[7]; //(4)
if ((0 == y % 4 && y % 100 != 0) || (0 == y % 400)) //(5)
{
day[1] = 29; //(6)
}
else
{
day[1] = 28; //(7)
}
if ( m>12||m< 1 || d<1 || d>day[m]) //(8)
return 0;
return 1;
}
- （1）定义每个月的天数
- （2）计算年份
- （3）计算月份
- （4）计算第几天
- （5）判断是不是闰年
- （6）闰年二月天数为29
- （7）非闰年二月天数为28
- （8）判断是不是符合日期标准
四、代码汇总
1.C语言代码
#include <stdio.h>
//获取日期的位数
void digit(int date, int a[], int N)
{
for (int i = 0; i < N; i++)
{
a[N - 1 - i] = date % 10;
date = date / 10;
}
}
int check_1(int a[])
{
if (a[0] == a[7] && a[1] == a[6] && a[2] == a[5] && a[3] == a[4])
return 1;
return 0;
}
int check_2(int a[])
{
if (a[0] == a[2] && a[0] == a[5] && a[0] == a[7] && a[1] == a[3] && a[1] == a[4] && a[1] == a[6])
return 1;
return 0;
}
int check_3(int a[])
{
int day[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 };
int y = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
int m = a[4] * 10 + a[5];
int d = a[6] * 10 + a[7];
if ((0 == y % 4 && y % 100 != 0) || (0 == y % 400))
{
day[1] = 29;
}
else
{
day[1] = 28;
}
if (m > 12 || m < 1 || d<1 || d>day[m])
return 0;
return 1;
}
int main()
{
int a[8];
int input, a1 = 0, a2 = 0;
scanf("%8d", &input);
int i = input + 1;
for (int i = input + 1; i <= 89991231; i++)
{
digit(i, a,8);
if (check_1(a) && check_3(a))
{
a1 = i;
break;
}
}
for (int i = input + 1; i <= 89991231; i++)
{
digit(i, a,8);
if (check_2(a) && check_3(a))
{
a2 = i;
break;
}
}
printf("%d\n%d", a1, a2);
return 0;
}
2. C++代码
C++里面有很多C语言没有的东西。 比如： string类型 有了这个类型，玩的花样就多了不少。 同时 to_string 可以将数字常量转换为字符串，返回值为转换完毕的字符串。
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
bool check_1(int date)
{
string a = to_string(date);
if (a[0] == a[7] && a[1] == a[6] && a[2] == a[5] && a[3] == a[4])
return true;
return false;
}
bool check_2(int date)
{
string a = to_string(date);
if (a[0] == a[2] && a[0] == a[5] && a[0] == a[7] &&
a[1] == a[3] && a[1] == a[4] && a[1] == a[6])
return true;
return false;
}
bool check_3(int date)
{
int day[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 };
int y = date / 10000, m = date / 100 % 100, d = date % 100;
if ((0 == y % 4 && y % 100 != 0) || (0 == y % 400))
{
day[1] = 29;
}
else
{
day[1] = 28;
}
if (m > 12 || m < 1 || d<1 || d>day[m])
return false;
return true;
}
int main()
{
int day[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 };
int date, a1, a2;
scanf("%8d", &date);
for (int i = date + 1; i <= 89991231; i++)
{
if (check_1(i) && check_3(i))
{
a1 = i;
break;
}
}
for (int i = date + 1; i <= 89991231; i++)
{
if (check_2(i) && check_3(i))
{
a2 = i;
break;
}
}
cout << a1 << endl << a2;
return 0;
}
五、总结
1.回文判断
回文都是对称结构，只需要让对称的部分相等就行了。
打个比方：人人为我我为人人
这句话就是对称的。
如果对称的部分相等，那么就满足了回文的要求。
bool check_1(int date)
{
string a = to_string(date);
if (a[0] == a[7] && a[1] == a[6] &&
a[2] == a[5] && a[3] == a[4])
return true;
return false;
}
2.日期判断
注意：判断是不是合法日期有个小坑，那就是闰年！ 闰年的二月天数是29天，而不是28天。 此时就涉及到了，闰年的判断方法。 对于日期的判断，我们可以记住下面这段代码。
bool check_3(int date)
{
int day[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 };
int y = date / 10000, m = date / 100 % 100, d = date % 100;
if ((0 == y % 4 && y % 100 != 0) || (0 == y % 400))
{
day[1] = 29;
}
else
{
day[1] = 28;
}
if (m > 12 || m < 1 || d<1 || d>day[m])
return false;
return true;
}