P4709 黑色星期五（基础）

解题思路

要统计某一年里，13 号恰好是星期五的日子有多少次。一年最多 12 个 13 号，只要知道每个月 13 号是星期几，数一数是星期五的就行。

关键是确定每一天的星期。题目告诉我们：2001 年 1 月 1 日是星期一。星期是每 7 天循环一次的，所以只要算出从 2001 年 1 月 1 日到目标日期一共过了多少天，再用这个天数除以 7 取余数，就能推出星期几。

做法分三步：

1. 先算从 2001 年到目标年的前一年年底一共过了多少天。注意闰年 366 天、平年 365 天。闰年判断：能被 4 整除且不能被 100 整除，或者能被 400 整除。
2. 算出目标年 1 月 1 日是星期几。我把星期用 0~6 表示（0 是周日、1 是周一……6 是周六），2001-01-01 是周一记作 1。
3. 从 1 月到 12 月，每个月"1 号星期 + 12"就是 13 号的星期，判断是否等于 5（星期五）。然后加上当月的天数，得到下个月 1 号的星期，继续判断。

举个例子：2001 年。1 月 13 号是周六，2 月 13 号是周二，4 月 13 号是周五，7 月 13 号也是周五，一共 2 次，和样例一致。

边界情况：闰年的二月有 29 天，会影响后面月份的星期；输入的年份至少是 2001，不会出现更早的年份。

参考代码

// 黑色星期五：统计某年中 13 号恰好是星期五的次数
#include <iostream>
using namespace std;

int main() {
    int y;
    cin >> y;
    int days = 0;
    // 计算 2001 年到目标年的前一年共经过多少天
    for (int i = 2001; i < y; i++) {
        bool leap = (i % 4 == 0 && i % 100 != 0) || i % 400 == 0;
        days += leap ? 366 : 365;
    }
    // 星期用 0~6 表示：0=周日,1=周一,...,6=周六；2001-01-01 是周一
    int wd = (1 + days) % 7; // 目标年 1 月 1 日的星期
    int mon[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    bool leap = (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
    if (leap) mon[2] = 29; // 闰年二月 29 天
    int cnt = 0;
    for (int m = 1; m <= 12; m++) {
        if ((wd + 12) % 7 == 5) cnt++; // 1 号加 12 天是 13 号，5 表示星期五
        wd = (wd + mon[m]) % 7;        // 累加当月天数，得到下个月 1 号星期
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

从 2001 年到目标年，每一年算一次闰年，再对 12 个月各判断一次，时间复杂度 O(年份差)。年份差哪怕有几千年，也只要几万次计算。空间 O(1)。