HDU-6010-Daylight Saving Time

ACM模版

描述

题解

这个题的难点在于题目不好懂,只要读懂了题目,细心一些的人都能做出来。

大致的思路是先预处理出来每年的两个时间节点,也就是每年三月份的第二个星期天和每年十一月份的第一个星期天是多少号,然后直接拿数据进行对比即可。

现在来说重点,预处理的手段不止一种,常规一些的就是按照年往后推,一年 365365 或者 366366 天,让它们模 77 然后进行偏移,感觉这种方法比较容易想,方法也不错,还有一种方法便是,利用基姆拉尔森公式,直接求出来每年的三月一号和十一月一号是星期几,然后往后一推便能得到我们想知道的日期,这个也是比较巧妙的,但是网上几乎没有题解是这样做的,可能这是一个比较冷门的东西吧?但是基姆拉尔森公式在去日期的问题上,真的是一个很牛的东西。

至于怎么进行对比,常规的思路便是年月日时分秒逐个对比,还有一个比较好的方法便是 HASHHASH,我们很容易想到的是可以把年月日时分秒表示成一个 1414 位的整数,高四位代表年份,接着的十位,每两位代表一个信息元素,月、日、时、分、秒。这样的话我们只需要对上述预处理出来的节点进行 HASHHASH,然后对询问也进行 HASHHASH,接着二分查找到对应的位置,几个判断便可以得到结果。

这里只给大家比较常规的解法对应的代码,因为笔者比较懒,所以就不写上述的第二种解法了。

代码

#include <cstdio>

using namespace std;

const int MAXN = 101;

int StoD[MAXN];
int DtoS[MAXN];

struct time
{
    int y, m, d, h, _m, s;

    bool operator < (const time &b) const
    {
        if (y != b.y)
        {
            return y < b.y;
        }
        else if (m != b.m)
        {
            return m < b.m;
        }
        else if (d != b.d)
        {
            return d < b.d;
        }
        else if (h != b.h)
        {
            return h < b.h;
        }
        else if (_m != b._m)
        {
            return _m < b._m;
        }
        else
        {
            return s < b.s;
        }
    }
} da;

void init()
{
    StoD[7] = 11;
    DtoS[7] = 4;
    for (int i = 8; i < MAXN; i++)
    {
        if (i % 4 || i % 100 == 0)
        {
            StoD[i] = StoD[i - 1] - 1;
            if (StoD[i] <= 7)
            {
                StoD[i] += 7;
            }
            DtoS[i] = DtoS[i - 1] - 1;
            if (DtoS[i] < 1)
            {
                DtoS[i] += 7;
            }
        }
        else
        {
            StoD[i] = StoD[i - 1] - 2;
            if (StoD[i] <= 7)
            {
                StoD[i] += 7;
            }
            DtoS[i] = DtoS[i - 1] - 2;
            if (DtoS[i] < 1)
            {
                DtoS[i] += 7;
            }
        }
    }
}

int main()
{
    init();

    int T;
    scanf("%d", &T);

    for (int i = 1; i <= T; i++)
    {
        scanf("%d-%d-%d %d:%d:%d", &da.y, &da.m, &da.d, &da.h, &da._m, &da.s);

        time PN = {da.y, 3, StoD[da.y - 2000], 2, 0, 0};
        time NP = {da.y, 3, StoD[da.y - 2000], 3, 0, 0};
        time PB = {da.y, 11, DtoS[da.y - 2000], 1, 0, 0};
        time BP = {da.y, 11, DtoS[da.y - 2000], 2, 0, 0};

        printf("Case #%d: ", i);
        if (da < PN)
        {
            printf("PST\n");
        }
        else if (da < NP)
        {
            printf("Neither\n");
        }
        else if (da < PB)
        {
            printf("PDT\n");
        }
        else if (da < BP)
        {
            printf("Both\n");
        }
        else
        {
            printf("PST\n");
        }
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏怀英的自我修炼

Java漫谈2

本周我们的Java漫谈从一个段子说起。话说有一个老程序退休了,在家闲着没事便开始学习写毛笔字,焚香,研墨,铺纸。站在薄如蝉翼白似雪的宣纸面前,提笔闭目。只见那人...

34480
来自专栏阿杜的世界

《重构》阅读笔记-代码的坏味道

开发者必须通过实践培养自己的经验和直觉,培养出自己的判断力:学会判断一个类内有多少个实例变量算是太大、学会判断一个函数内有多少行代码才算太长。

8020
来自专栏小樱的经验随笔

SG函数和SG定理【详解】

在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念: P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。...

40670
来自专栏章鱼的慢慢技术路

计蒜客2018 蓝桥杯省赛 B 组模拟赛(一)

38330
来自专栏Phoenix的Android之旅

重构-为什么 if-else 不是好代码

平时开发中if-else用的多吗? 其实这是个再正常不过的coding习惯,当我们代码量小的时候用来做条件判断是再简单不过的了。 但对于优秀程序员来说,这并不是...

19810
来自专栏chafezhou

学习Python,怎能不懂点PEP呢?

作者:豌豆花下猫,某985高校毕业生, 兼具极客思维与人文情怀 。公众号Python猫, 专注python技术、数据科学和深度学习,力图创造一个有趣又有用的学习...

16110
来自专栏哈雷彗星撞地球

设计模式简介

设计模式(Design pattern)是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结。 设计模式代表了最佳的实践,通常被有经验的面向对...

10340
来自专栏追不上乌龟的兔子

LeetCode Weekly 92:867. 回文素数

我当时做的时候是先写了一个生成器找素数,然后判断是不是回文数,素数生成器是这样的:

24050
来自专栏大闲人柴毛毛

三分钟理解“简单工厂模式”——设计模式轻松掌握

实际问题: 由于超市隔三差五就要办促销活动,但每次促销活动的方式不一样,所以需要开发一个软件,营业员只要输入原价再选择活动类型后,就能计算出折扣以后的价钱。 普...

402120
来自专栏nimomeng的自我进阶

探索命名之美(二)

大家在编码或者读代码的过程中,对于什么样的命名是好的命名可能认知不是特别清晰,但是对于什么样的命名是坏的命名应该一目了然,他们包括:

8920

扫码关注云+社区

领取腾讯云代金券