题解 P1202 【[USACO1.1]黑色星期五Friday the Thirteenth】

HEIGE · 2019-12-29 01:19:18 · 题解

基姆拉尔森计算公式秒解法

不知道为什么大家都写了这么暴力的代码，这里提供一个更容易的基于数学的方法。

题意分析

题目要求我们计算从1900年1月1日至1990+n-1年12月31日中13号落在周一到周日的次数。非常简单而又朴素的想法是枚举各年各月的13号，并通过一个函数week\_day(year, month, day)将该日期转换成星期，并用一个数组count[7]进行储存。

关键日期转星期函数的编写

有关于Kim larsen calculation formula的百度百科。该公式可以直接通过年月日求出当天星期。还有一个相似的Zeller's formular，均为秒杀日期模拟题的利器。

基姆拉尔森计算公式：

其中[num]表示取整，实际中直接用int除就完事了QwQ。需要注意的是，该公式将每年的1月与2月份作为前一年的13与14月份进行计算，所以需要在代码中进行一个小小的特判即可完成。若详细的证明可以自己尝试一下，或者随手一搜也有一大堆/以后也有可能开另一篇文章讲一下/？

int week_day(int year, int month, int day)  //the function which converts date to week *will return 0 for Sunday
{
    if (month == 1 || month == 2) month += 12, year--;  //process the special cases for Jan and Feb
    return (day + 2 * month + 3 * (month + 1) / 5 + year + year / 4 - year / 100 + year / 400 + 1) % 7; //the Kim larsen calculation formula!
}

根据数学原理，以上就是该日期转星期函数在C++中的写法。

AC代码

#include <iostream> //pure C++ writer!
using namespace std;    //just using it! 
int week_day(int year, int month, int day)  //the function which converts date to week *will return 0 for Sunday
{
    if (month == 1 || month == 2) month += 12, year--;  //process the special cases for Jan and Feb
    return (day + 2 * month + 3 * (month + 1) / 5 + year + year / 4 - year / 100 + year / 400 + 1) % 7; //the Kim larsen calculation formula!
}
int main()
{
    int year_len = 0;
    cin >> year_len;
    int count[7] = {0}; //what else can I explain/.
    for (int current_year = 1900; current_year < 1900 + year_len; current_year++)
        for (int current_month = 1; current_month <= 12; current_month++)
            count[week_day(current_year, current_month, 13)]++;
    cout << count[6] << " "<<count[0]<< " "<<count[1]<< " "<<count[2]<< " "<<count[3]<< " "<<count[4]<< " "<<count[5];  //remember to pay attention to the cout format
    return 0;
}

写在最后

不过竞赛环境下也不能指望把这个如此丑陋的公式背下来（所以学习一些更加丑的暴力算法大概还有一点用/大雾/）。