前言

这次要讲解的题从本质上说就是一个简单的模拟题,模拟题在竞赛中是一类简单而复杂的问题,简单是因为不需要太过高深的算法就能够解决,而复杂指的是,你需要准确地掌握题目中的每一个条件,用最简单明快的方式去实现

题意

[Friday the Thirteenth]

已知1900年1月1日是星期一,4,6,11和9月有30天,其他月份除了2月都有31天。年份可以被400整除的世纪年或者被4整除的非世纪年是闰年,世纪年指的是年份为100整数的年

写一个程序来计算从1900年起,在n年里13日落在星期六,星期日,星期一,……星期五的次数

分析与代码

首先用一个常量来记录1900这个年份数字

1
const int base = 1900;

每年各个月份的天数其实也是一个常量,我们用一个数组来将其记录下来,方便查询

1
int months[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

这里我只记录了非闰年的情况,为了清晰起见,闰年也可以通过这种方式记录

之后的基本思路就是每个月的天数不断累加,判断那个月的13号是星期几即可

因为题目中要求的是依次输出周六到周五,所以我们用数组下标为0的位置存周六的次数,下标为1的位置存周日的次数,以此类推

1900年的1月1日是周一,也就是前一天是周日,所以我们建立我们的天数累加变量day值为1,来表示要计算的第一天的前一天

闰年的判断直接按照题目描述的进行计算即可

1
2
3
4
5
6
bool isLeap = 0;
if ((base + i) % 100 == 0) {
if ((base + i) % 400 == 0) isLeap = 1;
} else if ((base + i) % 4 == 0) {
isLeap = 1;
}

然后逐年逐月计算日期对应星期几即可

1
2
3
4
5
for (int j = 0; j < 12; j++) {
count[(day + 13) % 7]++;
day += months[j];
if (j==1 && isLeap) day++;
}

这样,直接模拟,这题就可以处理完毕了

除此之外,希望大家通过这题顺便学习一下蔡勒公式,其作用是根据给定的年月日直接通过式子算出是星期几,当然这个公式有一定的限制(自行搜索了解),对于这题来说是没有问题的

那么如果有了蔡勒公式,这个题的结构就可以变得更简单,直接枚举年月日,计算对应星期几记录即可

整体代码

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
30
31
32
#include <bits/stdc++.h>
using namespace std;
// 1900年
const int base = 1900;

int main() {
int n;
scanf("%d", &n);
vector<int> count(7, 0); // [星期六 - 星期五]
int months[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 非闰年
int day = 1; // 公元元年1月1日前一天是星期日

for (int i = 0; i < n; i++) {
// 对每年是否为闰年进行计算
bool isLeap = 0;
if ((base + i) % 100 == 0) {
if ((base + i) % 400 == 0) isLeap = 1;
} else if ((base + i) % 4 == 0) {
isLeap = 1;
}
// 计算每个月的13号对应星期几
for (int j = 0; j < 12; j++) {
count[(day + 13) % 7]++;
day += months[j];
if (j==1 && isLeap) day++;
}
}
for (int i = 0; i < 7; i++)
printf("%d%c", count[i], " \n"[i == 6]);
return 0;
}

Accept

蔡勒公式的代码非常简单,请大家自行学习实现

任务清单

  • 用简单清楚的方式实现这道题
  • 学习蔡勒公式,完成此题,将蔡勒公式整理进自己的模板