题解：洛谷 P1202 [USACO1.1] 黑色星期五Friday the Thirteenth

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1202 [USACO1.1] 黑色星期五Friday the Thirteenth - 洛谷【题目描述】13 号又是一个星期五那么 13号在星期五比在其他日子少吗为了回答这个问题写一个程序要求计算每个月的十三号落在周一到周日的次数。给出n年的一个周期要求计算 1900 年 1 月 1 日至 1900n−1 年 12 月 31 日中十三号落在周一到周日的次数。这里有一些你要知道的1900 年 11 月 11 日是星期一。4,6,11 和 9 月有 30 天其他月份除了 2 月都有 31 天闰年 2 月有 29 天平年 2 月有 28 天。年份可以被 4 整除的为闰年19924×498 所以 1992 年是闰年但是 1990 年不是闰年。以上规则不适合于世纪年。可以被 400 整除的世纪年为闰年否则为平年。所以1700,1800,1900,2100 年是平年而 2000 年是闰年。【输入】一个正整数n。【输出】依次输出周六、日、一、二、三、四、五在 13 日出现的次数。【输入样例】20【输出样例】36 33 34 33 35 35 34【核心思想】问题分析给定n nn年周期1900 年至1900 n − 1 1900n-11900n−1年需要统计每个月 13 号落在周六、日、一、二、三、四、五的次数。关键在于确定每个月 13 号是星期几而星期几由该月 13 号距离某个已知星期几的基准日的天数决定。算法选择日期递推以 1900 年 1 月 1 日为起点逐月累加天数利用模 7 运算确定星期几闰年判断根据规则判断每年是否为闰年选择对应月份天数偏移量计算每个月 13 号的星期 ( 该月1号距离基准日的天数 12 ) m o d 7 (\text{该月1号距离基准日的天数} 12) \bmod 7(该月1号距离基准日的天数12)mod7代码中用(day 13) % 7day为当月 1 号距离 1900 年 1 月 1 日的天数加 13 等价于加 12 偏移到 13 号关键步骤初始化day 0表示 1900 年 1 月 1 日距离自身的偏移为 0 天闰年判断函数f(n)若n m o d 4 0 n \bmod 4 0nmod40且n m o d 100 ≠ 0 n \bmod 100 \neq 0nmod1000或n m o d 400 0 n \bmod 400 0nmod4000则为闰年逐月遍历外层年份i ii内层月份j jj计算当月 13 号的星期索引c[(day 13) % 7]更新day加上当月总天数闰年用m 2 [ j ] m2[j]m2[j]平年用m 1 [ j ] m1[j]m1[j]使day变为下月 1 号的偏移量输出按周六(c [ 6 ] c[6]c[6])、日(c [ 0 ] c[0]c[0])、一(c [ 1 ] c[1]c[1])…五(c [ 5 ] c[5]c[5]) 的顺序输出时间/空间复杂度时间复杂度O ( 12 n ) O(12n)O(12n)遍历n nn年每年 12 个月闰年判断O ( 1 ) O(1)O(1)空间复杂度O ( 1 ) O(1)O(1)仅需常数级数组存储月份天数和计数日期递推的核心思想基准日锚定以已知星期几的日期1900 年 1 月 1 日星期一为基准所有日期通过天数偏移量确定星期模 7 周期性星期每 7 天循环一次因此( 偏移天数 ) m o d 7 (\text{偏移天数}) \bmod 7(偏移天数)mod7即可得到星期索引逐月累加而非逐日不需要遍历每一天只需记录每月 1 号的偏移量加 12 即得 13 号偏移量再加当月天数即得下月 1 号偏移量闰年规则精确建模世纪年需被 400 整除才为闰年单独处理 2 月天数适用于固定周期内日期星期统计、日历生成等问题【解题思路】【算法标签】#普及- #数学【代码详解】#includebits/stdc.husingnamespacestd;boolf(intn)// 定义闰年判断函数{if(n%40n%100!0||n%4000){// 模板背下来returntrue;}returnfalse;}intm1[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};// 定义平年和闰年的每个月日子数intm2[13]{0,31,29,31,30,31,30,31,31,30,31,30,31};intc[10]{0};// 定义c数组统计周一-周日的计数intn,day0;intmain(){cinn;// 输入nfor(inti1900;i1900n-1;i){//从1900年遍历至1900n-1年for(intj1;j12;j){// 依次遍历每个月if(f(i)){// 如果为闰年c[(day13)%7];// 先计算余数并自增daydaym2[j];// 再增加天数2月要加31天3月要加29年。到了下一年的1月则是加上前一年的12月31天}else{//平年的计算过程同上c[(day13)%7];daydaym1[j];}}}coutc[6] c[0] c[1] c[2] c[3] c[4] c[5]endl;// 因为没有遍历的规律所以按要求依次输出周六、日、一、二、三、四、五的计数return0;}【运行结果】20 36 33 34 33 35 35 34