算法 - 星期几模拟

2020-12-29 13:10:32

题目：ACwing1341. 十三号星期五

题目来源：https://www.acwing.com/problem/content/1343/

描述：

十三号星期五真的很不常见吗？

每个月的十三号是星期五的频率是否比一周中的其他几天低？

请编写一个程序，计算 N 年内每个月的 13 号是星期日，星期一，星期二，星期三，星期四，星期五和星期六的频率。

测试的时间段将会开始于 1900 年 1 月 1 日，结束于 1900+N−1 年 12 月 31日。

一些有助于你解题的额外信息：

1900 年 1 月 1 日是星期一。
在一年中，4 月、6 月、9 月、11 月每个月 30 天，2 月平年 28 天，闰年 29 天，其他月份每个月31天。
公历年份是 4 的倍数且不是 100 的倍数的年份为闰年，例如 1992 年是闰年，1990 年不是闰年。
公历年份是整百数并且是 400 的倍数的也是闰年，例如1700年，1800年，1900年，2100年不是闰年，2000年是闰年。

输入格式
共一行，包含一个整数 N。

输出格式
共一行，包含七个整数，整数之间用一个空格隔开，依次表示星期六，星期日，星期一，星期二，星期三，星期四，星期五在十三号出现的次数。

数据范围
$1≤N≤400,$

输入样例：

1
20

输出样例：

1
36 33 34 33 35 35 34

算法1：$O(n)$

按照每个月来进行模拟一共12个月；每个月的13号，为这个月过了12天。
需要进行一个闰年的判断：

如果能被4整除并且不是整百年
或者是400的倍数

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
#include <iostream>

using namespace std;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int weekdays[7];
int n;

int main()
{
    cin >> n;
    int year = 1900, days = 0;
    while(n--)
    {
        for(int i = 1; i <= 12; i++)
        {
            // 表示过了12天之后是星期几
            weekdays[(days + 12) % 7 + 0] ++;
            days += month[i];
            if (i == 2)
            {
                if (year % 4 == 0 && year % 100 || year % 400 == 0)
                    days++;
            }
        }
        year ++;
    }
    for(int i = 5, j = 0; j < 7; j++, i++) cout << weekdays[i % 7] << ' ';
    return 0;
}