B3737 [信息与未来 2018] 双十一

· · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考察递推、数学。

一年有 365（平年）或者 366（闰年）天。对数字较为敏感的同学会发现，365\div 7=52 \dots 1，366\div 7=52\dots 2。也就是说，如果我们知道了 1900 年的 11 月 11 日是星期几，那么 1901 年的双十一就是这个星期数 +1。而 1904 年的双十一则是 1903 年双十一的星期数 +2。问题就变为了如何求出 1900 年的双十一是星期几了。

这个也很好办，给出一种不用计算的做法：已知 1900 年是平年，打开电脑上的日历，观察 2025 年（是个平年）的日历，会发现 2025 年 1 月 1 日是星期三，而 11 月 11 日是星期二，也就是说对于 1900 年的 11 月 11 日，其星期应当是 1 月 1 日（星期一）的前一天——也就是星期日。

因此，我们就可以根据 1900 年的 11 月 11 日的星期，一路进行递推，则可得到正确的结果。

bool leap(int x) {
    return (x % 4 == 0 && x % 100 != 0) || (x % 400 == 0);
}

a[1900] = 6;
//为了星期数可以简单地使用模运算，这里规定 a[i] = 0 为星期一，a[i] = 1 为星期二，以此类推，a[i] = 6 为星期日
for (int i = 1901; i <= y; i++) {
    if (leap(i)) // 判断是否为闰年
        a[i] = (a[i - 1] + 2) % 7;
    else
        a[i] = (a[i - 1] + 1) % 7;
}
for (int i = x; i <= y; i++) {
    if (a[i] == 5 || a[i] == 6) // 判断是否是周末
        ans++;
}