P4714 2001年的黑色星期五（入门）

解题思路

"黑色星期五"是指某个月的 13 号正好是星期五。题目要我们统计 2001 年一年里一共出现了多少次黑色星期五。

题目给了两个关键信息：

1. 2001 年 1 月 1 日是星期一。
2. 2001 年是平年，2 月有 28 天，全年一共 365 天。

这道题没有输入，只需要在程序里模拟出 2001 年的每一天。

做法就像翻日历一样，一天一天往后翻：

• 用一个变量 wd 记录"今天是星期几"。我们规定 1 表示星期一，2 表示星期二，……，5 表示星期五，6 表示星期六，7 表示星期日。
• 每过一天，星期几就往后推一天。推的规则是：wd = wd % 7 + 1。当 wd 是 7（星期日）时，wd%7 得 0，再加 1 就变回 1（星期一），正好完成一周的循环。
• 同时，把每个月的天数先存进数组：1月31天、2月28天、3月31天、4月30天、5月31天、6月30天、7月31天、8月31天、9月30天、10月31天、11月30天、12月31天。
• 用两层循环遍历 12 个月、每个月里的每一天。每遇到"今天日期 d 等于 13，并且 wd 等于 5"，就说明今天是一个黑色星期五，答案加一。

模拟完这 365 天，所有月份的 13 号都被检查到了，一个都不会漏。

参考代码

// 2001年的黑色星期五：统计2001年中13号是星期五的天数
#include <iostream>
using namespace std;
int main() {
    int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int wd = 1; // 2001年1月1日是星期一，记1=周一 ... 5=周五 ... 7=周日
    int ans = 0;
    for (int m = 0; m < 12; m++) {
        for (int d = 1; d <= days[m]; d++) {
            if (d == 13 && wd == 5) ans++;
            wd = wd % 7 + 1; // 星期几往后推一天
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

程序模拟了整整一年的 365 天，每一天只做常数次操作（判断日期、更新星期几），所以时间复杂度是 O(365)，可以看作 O(1)。

空间方面，只用了一个长度为 12 的数组存每个月的天数，以及几个 int 变量记录答案和当前星期几，空间复杂度是 O(1)，非常节省。