解决USACO 1.1 - 星期五,第13天与date.h

Question

该USACO 1.1 -周五第十三届问题已经以各种方式解决了很多次.事实上,它已经在StackOverflow上产生了一些问题,并提供了各种解决方案:

• 星期五,第十三届 - USACO
• 我的代码出了什么问题？Usaco:星期五十三号
• usaco:星期五十三错误
• USACO.十五号星期五.我的代码出了什么问题？
• 第十三天发生在哪几天？USACO

问题是:使用现代C++ 11/14日期库(例如我链接到的日期库)的解决方案是什么样的？

它会比其他解决方案简单得多吗？更容易写？更高效？

Answer 1

问题陈述是计算每个月的第13个月在该范围内的给定工作日的频率[1900-01-01, 2300-01-01).

使用date.h可以非常轻松有效地完成这样的操作:

#include "date.h"
#include <iostream>

int
main()
{
    using namespace date;
    unsigned freq[7] = {};
    for (auto ym = 1900_y/jan; ym < 2300_y/jan; ym += months{1})
        freq[unsigned{weekday{ym/13}}]++;
    for (unsigned i = 0; i < 7; ++i)
        std::cout << weekday{i} << " : " << freq[i] << '\n';
}

ym是一个date::year_month对象.您可以将其视为a time_point,但它具有非常粗略的精度months.

你只需循环遍历每年,每年的每个月,并计算当月13日的星期几,并将其weekday投入到unsigned.

高级语法非常简单易读.

引擎盖下的算法是days_from_civil和weekday_from_days.这些低级日期算法中的任何一个都不是迭代的,因此它们非常有效.因此,您可以充分利用这两个方面:可读的高级语法和高性能.

这个简单程序的输出也非常易读:

Sun : 687
Mon : 685
Tue : 685
Wed : 687
Thu : 684
Fri : 688
Sat : 684

事实证明,星期五13日比一周中的其他日子稍微有点可能.

在C++ 1z(我们希望是C++ 17)中,您甚至可以constexpr std::array<unsigned, 7>使用这些结果创建一个(如果由于某种原因在编译时具有这样的数字很重要):

#include "date.h"
#include <array>
#include <iostream>

constexpr
std::array<unsigned, 7>
compute_freq() noexcept
{
    using namespace date;
    decltype(compute_freq()) freq = {};
    for (auto ym = 1900_y/jan; ym < 2300_y/jan; ym += months{1})
        freq[unsigned{weekday{ym/13}}]++;
    return freq;
}

constexpr auto freq = compute_freq();

int
main()
{
    using namespace date::literals;
    static_assert(freq[unsigned{sun}] == 687);
    static_assert(freq[unsigned{mon}] == 685);
    static_assert(freq[unsigned{tue}] == 685);
    static_assert(freq[unsigned{wed}] == 687);
    static_assert(freq[unsigned{thu}] == 684);
    static_assert(freq[unsigned{fri}] == 688);
    static_assert(freq[unsigned{sat}] == 684);
}

生成这个程序集:

_freq:
    .long   687                     ## 0x2af
    .long   685                     ## 0x2ad
    .long   685                     ## 0x2ad
    .long   687                     ## 0x2af
    .long   684                     ## 0x2ac
    .long   688                     ## 0x2b0
    .long   684                     ## 0x2ac

你不能比那更有效率.