每日算法打卡：回文日期

算法
824 words

原题链接

466. 回文日期

题目难度：简单

题目来源：NOIP2016普及组

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 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 表示，它不是回文的。

输入格式

输入包括两行，每行包括一个 8 位数字。

第一行表示牛牛指定的起始日期 $date_1$，第二行表示牛牛指定的终止日期 $date_2$。保证 $date_1$ 和 $date_2$ 都是真实存在的日期，且年份部分一定为 4 位数字，且首位数字不为 0。

保证 $date_1$ 一定不晚于 $date_2$。

输出格式

输出共一行，包含一个整数，表示在 $date_1$ 和 $date_2$ 之间，有多少个日期是回文的。

输入样例：

1
2
20110101
20111231

输出样例：

1
1

题目分析

这道题目的意思是很清楚的，这里可以大概分为两步，第一步是枚举，第二步是判断，这道题的难点就在于如何枚举

如果暴力枚举每一天的话，基本上也没有问题，但是对于日期的进位要写的话是会比较复杂的

有没有更好的枚举方法呢，其实是有的，我们可以调整一下顺序，暴力的做法是先枚举每一天，再判断是否是回文，调整顺序之后就变成了，先枚举回文串，再判断是否在日期范围内的，最后判断一下日期是否合法即可。

那么问题就是我们如何枚举回文呢，其实只需要枚举年份，前四位确定之后，翻转一下就知道后四位了

示例代码

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
#include<iostream>
using namespace std;
using ll = long long;
int main()
{
    ll date1, date2;
    cin >> date1 >> date2;
    
    // 获取年份
    int year1 = date1 / 10000;
    int year2 = date2 / 10000;
    
    // 计数
    int cnt = 0;
    
    // 枚举回文串
    for (int i = year1; i <= year2; i++)
    {
        int monthday[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
        int year = i;
        int tmp = i;
        int month = tmp % 10;
        tmp /= 10;
        month = month * 10 + tmp % 10;
        tmp /= 10;
        int day = tmp % 10;
        tmp /= 10;
        day = day * 10 + tmp % 10;

		// 判断范围
        if (year * 10000 + month * 100 + day > date2 || year * 10000 + month * 100 + day < date1)
            continue;
		
        // 判断合法  
        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
            monthday[1] = 29;
        else
            monthday[1] = 28;

        if (month >= 1 && month <= 12 && day <= monthday[month - 1] && day >= 1)
            cnt++;

    }
    cout << cnt << '\n';
    return 0;
}
Comments