AcWing 466. 回文日期

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 466. 回文日期原题链接简单

作者：

yxc , 2019-08-15 23:37:53 , 所有人可见 , 阅读 12736

110

39

算法

(枚举,模拟) $O(10^4)$

由于只有八位数，而且回文串左右对称，因此可以只枚举左半边，这样只需枚举 $0 \sim 9999$ 总共一万个数，然后判断：

整个八位数构成的日期是否合法；
是否在范围内

时间复杂度

一共枚举 $10^4$ 个数，判断每个数是否合法的计算量是常数级别的，因此总计算量是 $O(10^4)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;

    int res = 0;
    for (int i = 0; i < 10000; i ++ )
    {
        int x = i, r = i;
        for (int j = 0; j < 4; j ++ ) r = r * 10 + x % 10, x /= 10;

        if (r >= date1 && r <= date2 && check(r)) res ++ ;
    }

    printf("%d\n", res);
    return 0;
}

40 评论

AkTtt 2023-02-08 16:14

屌

Anohkx 2023-10-09 20:16

2023-10-08 09-29-50屏幕截图.png

Donga5 7个月前

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
/**
 * 466回文日期
 * 由于是回文数，只需要枚举左半边年份即可。根据年份构造出一个回文数来，
然后判断
- 该数是否是一个正常的日期
- 将日期转化成数字，比较看是否在开始和结束日期范围内即可。
*/
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int st,ed;

bool is_leap_year(int y)
{
    return (y%4==0&&y%100!=0)||(y%400==0);
}

int main()
{
    cin>>st>>ed;
    int res=0;
    int y1=st/1e4,y2=ed/1e4;
    int m1=st/1e4/100,m2=ed/1e4/100;
    int d1=st%100,d2=st%100;

    for(int i=y1;i<=y2;i++)
    {
        mon[2]=28;
        if(is_leap_year(i))mon[2]=29;
        int m=i%10*10+i%100/10;
        int d=i/100%10*10+i/1000;
        if(m>=1&&m<=12&&d>=1&&d<=mon[m])
        {
            int t=i*1e4+m*100+d;
            if(t>=st&&t<=ed)res++;
        }
    }
    cout<<res<<endl;
    return 0;
}