相关的题目
AcWing 1364. 序言页码
AcWing 1568. 中文读数字
AcWing 698. 读电话号码
AcWing 436. 立体图
LeetCode 273.
题目描述
十三号星期五真的很不常见吗?
每个月的十三号是星期五的频率是否比一周中的其他几天低?
请编写一个程序,计算 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年是闰年。
样例
输入样例:
20
输出样例:
36 33 34 33 35 35 34
算法1
(暴力枚举) $O(n^2)$
因为1900-1-1是星期一, 可以枚举月份, 然后计算当前月的19xx-x-1距离1900-1-1多少天, 计算出来为days,
那么13号为(day + 12) % 7
就是所求的星期几。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int weekend[7];
int n;
int main(){
cin >> n;
int day = 0;
for (int year = 1900; year < 1900 + n; year ++ )
for (int i = 1; i <= 12; i ++ ){
weekend[(day + 12) % 7] ++;
if (i == 2)
if (year % 4 == 0 && year % 100 || year % 400 == 0 ) day ++;
day += month[i];
}
for (int i = 5, j = 0; j < 7; i = (i + 1) % 7, j ++) cout << weekend[i] << ' ';
cout << endl;
return 0;
}