1.2　回文日期(★)

題目信息

2020 年省賽 - 填空題

● C/C++ A組第7題；C/C++ B組第7題

● Java A組第7題

【問(wèn)題描述】

2020 年春節(jié)期間，有一個(gè)特殊的日期引起了大家的注意：2020 年 2 月 2 日。因?yàn)槿绻麑⑦@個(gè)日期按 "yyyymmdd" 的格式寫成一個(gè) 8 位數(shù)是 20200202，恰好是一個(gè)回文數(shù)。我們稱這樣的日期是回文日期。

有人表示 20200202 是 "千年一遇" 的特殊日子。對(duì)此小明很不認(rèn)同，因?yàn)椴坏?2 年之后就是下一個(gè)回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不僅僅是一個(gè)回文日期，還是一個(gè) ABABBABA 型的回文日期。對(duì)此小明也不認(rèn)同，因?yàn)榇蠹s 100 年后就能遇到下一個(gè) ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 "千年一遇"，頂多算 "千年兩遇"。

給定一個(gè) 8 位數(shù)的日期，請(qǐng)你計(jì)算該日期之后下一個(gè)回文日期和下一個(gè) ABABBABA 型的回文日期各是哪一天。

【輸入格式】

輸入包含一個(gè)八位整數(shù) ，表示日期。

對(duì)于所有評(píng)測(cè)用例， ，保證 是一個(gè)合法日期的8位數(shù)表示。

【輸出格式】

輸出兩行，每行 1 個(gè)八位數(shù)。第一行表示下一個(gè)回文日期，第二行表示下一個(gè) ABABBABA 型的回文日期。

【樣例輸入】

20200202

【樣例輸出】

20211202

21211212

【答案提交】

這是一道結(jié)果填空題，你只需要算出結(jié)果后提交即可。本題的結(jié)果作為一個(gè)整數(shù)，在提交答案時(shí)只填寫這個(gè)整數(shù)，填寫多余的內(nèi)容將無(wú)法得分。

懶人速讀

給定（輸入）一個(gè) 位數(shù)的日期，請(qǐng)找出（輸出）該日期之后的下一個(gè)回文日期以及下一個(gè) ABABBABA 型回文日期。

若給定的日期為 20200202，則會(huì)有下列結(jié)果。

● 下一個(gè)回文日期為20211202。

● 下一個(gè) ABABBABA 型回文日期為21211212。

題目分析

核心考點(diǎn)

● （日期）枚舉

● 合法日期判斷

根據(jù)題意，我們可以將題目拆解為如何判斷回文和如何枚舉日期兩個(gè)部分來(lái)解決。

1．如何判斷回文

對(duì)于一個(gè)8位數(shù)的整型日期，可以通過(guò)除法和取余運(yùn)算來(lái)獲取它的每一位數(shù)字。

舉例說(shuō)明

若整數(shù) date 的值為 20050511，它從高到低的每一數(shù)位上的數(shù)可以通過(guò)下列方法得到。

● data / 10000000 = 2；

● data / 1000000 % 10 = 0；

● data / 100000 % 10 = 0；

● data / 10000 % 10 = 5；

● data / 1000 % 10 = 0；

● data / 100 % 10 = 5；

● data / 10 % 10 = 1；

● data % 10 = 1。

對(duì)于本題，若用 、 、 、 、 、 、 、 分別存儲(chǔ)每一位，則一個(gè)回文日期須滿足:

一個(gè) ABABBABA 型回文日期須滿足以下條件。

對(duì)于一個(gè)日期字符串，可以直接通過(guò)下標(biāo)來(lái)獲取它的每一位數(shù)字。例如， string date ="20050511"，它從高到低的每一位分別可以通過(guò) data[0], data[1], , data[7] 得到。判斷回文日期及ABABBABA 型回文日期的方式和上述方法類似。

不難看出，字符串獲取日期的每一位數(shù)字是要比整型簡(jiǎn)單的，所以在判斷回文日期及ABABBABA 型回文日期時(shí)可以將整型轉(zhuǎn)換為字符串來(lái)操作，如參考代碼1-2-1所示。

參考代碼1-2-1

 1  int date = 20050511;
 2  string s = to_string(date);  將整型轉(zhuǎn)換為字符串, s = "20050511"
 3  
 4  // 判斷回文日期
 5  bool check1(int date){
 6      string s = to_string(date);
 7      if(s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) return true;
 8      return false;
 9  }
10 // 判斷 ABABBABA 型回文日期
11 bool check2(int date){
12     string s = to_string(date);
13     if(s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6]) return true;
14     return false;
15 }

2．如何枚舉日期

對(duì)于一個(gè)整型日期，可以用最簡(jiǎn)單的方式枚舉，即令該日期不斷 +1，直到出現(xiàn)滿足 ABABBABA 型的回文日期。

但這樣存在一個(gè)問(wèn)題：會(huì)枚舉出許多不合法的日期（如 20209999）。為此，我們需要對(duì)日期進(jìn)行合法性判斷：設(shè) 分別表示年、月、日， 表示第 個(gè)月的天數(shù)，那么當(dāng) 或 或 或 時(shí)日期不合法，反之日期合法，如參考代碼1-2-2所示。

參考代碼1-2-2

  1   int month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};
  2   bool check(int date){
  3       string s = to_string(date);
  4       // stoi -> 將字符串轉(zhuǎn)為整型
  5       int y = stoi(s.substr(0, 4)), m = stoi(s.substr(4, 2)), d = stoi(s.substr(6, 2));
  6       if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;
  7       else month[2] = 28;
  8       if(m < 1 || m > 12 || d < 1 || d > month[m]) return false;
  9       return true;
 10   }
 11   for(int i = date + 1 ; ; i ++){
 12       if(!check(i)) continue ;
 13       ...
14   }

不過(guò)這樣的枚舉量是相當(dāng)大的，要在比賽中完成本題要求的所有測(cè)試數(shù)據(jù)不太現(xiàn)實(shí)。

那么，還有什么枚舉方法呢?

可以直接枚舉合法日期。枚舉合法日期只需模擬日期的變化規(guī)律即可，對(duì)應(yīng)參考代碼如下所示。

參考代碼1-2-3

  1  int month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};
  2  ...
  3  int date = 20050511;
  4  int y = date / 10000 , m = date / 100 % 100 , d = date % 100;
  5  // date = y * 10000 + m * 100 + d;
  6  
  7  for(int i = y ; ; i ++){
  8      if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29; // 閏年2月有29天
  9      else month[2] = 28;
 10      int j = (i == y) ? m : 1; // 如果是 i = y，則月份從 m 開始枚舉，否則 m 從 1 開始枚舉
 11      for(; j <= 12 ; j ++){
 12          int k = (i == y && j == m) ? d : 1;  // 如果 i = y 并且 j = m，則日從 d 開始枚舉，否則 d 從 1 開始枚舉
 13          for(; k <= month[j] ; k ++){
 14              // date = i * 10000 + j * 100 + k
 15              ...
 16          }
 17      }
18  }

我們還可以只枚舉年份。因?yàn)榇鸢敢欢ㄊ莻€(gè)回文日期（即回文串），所以枚舉年份 ，再將其翻轉(zhuǎn)得到 ，得到的 就一定是個(gè)回文串，如下頁(yè)圖所示。接著再對(duì)該串所對(duì)應(yīng)的日期進(jìn)行合法判斷、 ABABBABA 型回文判斷即可。

參考代碼1-2-4　【枚舉合法日期】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
 4 int date, ans1, ans2;
 5 // 判斷日期是否為回文
 6 bool check1(int date){
 7     string s = to_string(date);
 8     if(s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) return true;
 9     return false;
10 }
11 // 判斷日期是否滿足 ABABBABA 型回文
12 bool check2(int date)
13 {
14     string s = to_string(date);
15     if(s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6]) return true;
16     return false;
17 }
18 signed main()
19 {
20     cin >> date;
21     int y = date / 10000, m = date / 100 % 100, d = date % 100;
22     for(int i = y ; ; i ++) {
23         if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29;
24         else month[2] = 28;
25         int j = (i == y) ? m : 1;
26         for(; j <= 12 ; j ++) {
27             int k = (i == y && j == m) ? d + 1 : 1;
28             for(; k <= month[j] ; k ++) {
29                 int date = i * 10000 + j * 100 + k;
30                 if(check1(date) && ans1 == 0) ans1 = date;
31                 if(check2(date)) return cout << ans1 << '\n' << date << '\n', 0; // 當(dāng)找到了 ABABBABA 型回文日期時(shí)，結(jié)束程序
32             }
33         }
34     }
35     return 0;
36 }

參考代碼1-2-5　【枚舉年份】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 // month[1 ~ 12] 分別記錄 1 ~ 12 月每月的天數(shù)
 4 int date , month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};
 5 // 判斷日期是否合法
 6 string check(int date){
 7     string s = to_string(date) , t = to_string(date); // 將整型轉(zhuǎn)換為字符串
 8     reverse(t.begin() , t.end()); // 翻轉(zhuǎn)
 9     s += t; // 將 s 翻轉(zhuǎn)后再與 s 拼接，拼接后的字符串一定會(huì)是個(gè)回文串
10     int y = stoi(s.substr(0 , 4)), m = stoi(s.substr(4 , 2)), d = stoi(s.substr(6 , 2));
11     if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;
12     else month[2] = 28;
13     if(m < 1 || m > 12 || d < 1 || d > month[m]) return "-1";
14     return s;
15 }
16 // 判斷日期是否是 ABABBABA 型回文
17 string check2(int date){
18     string s = to_string(date) , t = to_string(date);
19     reverse(t.begin() , t.end()); // 翻轉(zhuǎn)
20     s += t;
21     if(s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] &&  s[1] == s[4] && s[1] == s[6]) return s;
22     return "-1";
23 }
24 signed main()
25 {
26     cin >> date;
27     string ans1 = "";
28     for(int i = date / 10000 ; ; i ++){
29         // 注意：date（輸入的日期）不能作為答案
30         if(check(i) == "-1" || check(i) == to_string(date)) continue ;
31         if(ans1 == "") ans1 = check(i);
32         if(check2(i) != "-1") return cout << ans1 << '\n' << check2(i) << '\n' , 0;
33     }
34     return 0;
35 }