算法练习题23---蓝桥杯2020省赛“回文日期”_[蓝桥杯2020初赛] 回文日期c++

---

前言

蓝桥杯2020省赛，编程题（C++）

一、题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入描述

输入包含一个八位整数 N，表示日期。

对于所有评测用例，10000101≤N≤89991231，保证 N 是一个合法日期的 8 位数表示。

输出描述

输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

输入输出样例

示例

输入

20200202
1

输出

20211202
21211212
1
2

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

二、思路

这个题对于8位数的处理，我采用的是字符串的方式，而不是变成整数型变量。个人感觉如果用整数型变量去累加会造成超时的情况。

对于8位数，可以拆成前四位的年份和后四位的日期。从年份去累加，再反过来判断月份和日期是否符合情况，这样循环的时间复杂度是绝对在最大运行时间允许范围内的，最多不超过10000次。对于累加的每一个年份，反过来去构造回文串，然后再判断月份和日期是否合法，这样就能找到下一个回文日期和ABABBABA 型的。

大体的思路基本上是这样的，另外有几点需要注意：

• 对于输入的那一年，要先去判断一次，再累加，例如输入10100000，下一次回文串是10100101，恰好也是ABABBABA型，注意不要跳过输入的年份
• 月份和日期的对应上，2月份天数与闰年（29天），非闰年（28天）的对应关系，以及30天的月份和31天的月份

关注好以上两点，基本上就没有问题了！

三、具体代码

#include<bits/stdc++.h>
using namespace std;
bool check(string s) //检查月份和日期是否合法
{
    int yue=0;
    int ri=0;
    yue=(s[4]-'0')*10;
    yue+=(s[5]-'0');
    ri=(s[6]-'0')*10;
    ri+=(s[7]-'0');
    if(yue<=0||yue>12)  
    {
        return false;
    }
    //月份合法，检查日期
    if(ri<=0||ri>31)
    {
        return false;
    }
    if(yue==4||yue==6||yue==9||yue==11)  //31天的月份
    {
        if(ri>=31)
        {
            return false;
        }
    }
    else if(yue==2)  //2月特殊
    {
        int year=0;
        year+=(s[0]-'0')*1000;
        year+=(s[1]-'0')*100;
        year+=(s[2]-'0')*10;
        year+=(s[3]-'0');
        if((year%4==0&&year%100!=0)||year%400==0)  //闰年
        {
            if(ri>29)
            {
                return false;
            }
        }
        else  //非闰年
        {
            if(ri>28)
            {
                return false;
            }
        }
    }
    return true;
}

bool check_AB(string s)
{
    for(int i=0;i<8;i++)
    {
        if(s[i]!=s[7-i])
        {
            return false;
        }
    }
    if(s[0]==s[2]&&s[1]==s[3]&&s[0]!=s[1])  //检查ABAB型
    {
        return true;
    }
    return false;
}
string add(string s) //往下搜索
{
    int num=0;
    num+=(s[0]-'0')*1000;
    num+=(s[1]-'0')*100;
    num+=(s[2]-'0')*10;
    num+=(s[3]-'0');
    num++;
    string temp2=to_string(num);
    temp2+=temp2[3];
    temp2+=temp2[2];
    temp2+=temp2[1];
    temp2+=temp2[0];
    return temp2;
}
int main()
{
    string s;
    cin>>s;
    string temp=s;
    int flag=0;
    string ans1;
    string ans2;
    int poi=0; //检查是否已经找到下一次的回文日期
    int flag2=0;
    temp[4]=temp[3];
    temp[5]=temp[2];
    temp[6]=temp[1];
    temp[7]=temp[0];
    if(temp>s&&check(temp))  //先检查在输入的年份内，是否存在回文串
    {
        ans1=temp;
        poi=1;
        if(temp[0]==temp[2]&&temp[1]==temp[3]&&temp[0]!=temp[1]) //检查ABAB型
        {
            ans2=temp;
            cout<<ans1<<endl;
            cout<<ans2<<endl;
            return 0;
        }
    }
    else
    {
        temp=s;
    }
    while(1) //找到下一次的回文日期和ABABBABA型的日期，增加规则为按照年份增加
    {
        temp=add(temp);  //实现temp自增
        if(check(temp))
        {
            if(poi==0)
            {
                ans1=temp;  //日期合法，为下一次回文日期
                poi=1;
            }
            if(check_AB(temp)) //检查是否为ABABBABA型日期
            {
                ans2=temp;
                break;
            }
        }
    }
    cout<<ans1<<endl;
    cout<<ans2<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132