1. 这题到底在考什么——UVa 158 Calendar的题意与隐藏考点UVa 158 Calendar单看名字平平无奇就是日历两个字。但在UVa题库里混过的老选手都知道题号158这个位置的题目基本都是算法竞赛入门阶段的经典模拟题属于那种不做一遍觉得简单做起来全是细节的类型。这道题的实际内容是给定一个年份范围是1到9999要求输出该年12个月的日历每个月的格式要精确到每一行的空格位置月份表头、星期表头、日期数字全部对齐。为什么说这道题是必刷的因为它在UVa所有日期类题目里属于地基级别的存在。后面你可能会碰到UVa 893、UVa 11329这些更复杂的日期题它们都会用到这里面的基础能力闰年判断、月份天数表、已知某天是星期几反推另一天是星期几。如果你把158彻底搞懂了后面那些题至少能少走一半弯路。先看题目要求的具体输出格式。每个月的日历需要三部分第一行是月份名称用英文缩写比如Jan.、Feb.注意末尾有个点然后是一个空行接着是星期表头格式是固定的Sun Mon Tue Wed Thu Fri Sat最后是日历本体每个日期占3个字符宽度右对齐每行7个日期最后一行不一定满7个但也要按照同样的宽度补齐空格。最要命的是每个月之间要用一个空行隔开但最后一个月的末尾不能再多输出空行——这种空白字符的控制恰恰是OJ判题最容易出Presentation Error的地方。我当年做这道题的时候第一次提交就吃了一个PEPresentation Error原因是最后一个月的末尾多打了一个换行。这种问题在本地编译器里根本看不出来因为终端不会把行尾空格给你标出来只有OJ的判题系统会把你的输出和标准答案逐字节比对任何多余的空格或空行都会被揪出来。所以这道题的第一个隐藏考点其实是输出格式的控制能力。很多新手会栽在这里不是因为不会算日历而是因为不会控制字符串输出。除了输出格式核心算法考点有两个。第一是闰年判断能被4整除但不能被100整除或者能被400整除的年份是闰年闰年二月有29天否则28天。这个规则背下来容易用的时候经常有人搞混尤其是1900年这种能被100整除但不能被400整除的年份它不是闰年。第二是星期推算给定年份你要知道这一年1月1日是星期几然后才能排日历。题目允许你用任何已知的基准日期最常见的做法是拿一个已知日期当锚点比如1900年1月1日是星期一或者2000年1月1日是星期六然后算出目标年份1月1日到基准日期的天数差对7取模就能得到星期几。很多人会问为什么不能直接用计算机系统自带的日历函数因为OJ环境不允许你调系统库就算允许不同平台的mktime行为也可能有差异判题结果会不可控。所以标准解法永远是纯手写日期推算这也是这类题训练的核心价值——不依赖任何平台能力用最原始的数学和逻辑解决问题。2. 思路选型与反直觉细节——为什么推荐逐月模拟而不是暴力展开2.1 两种主流解法怎么选UVa 158的常见解法有兩条路一条是逐月模拟另一条是整年展开后一次性打印。逐月模拟的思路是先算出1月1日是星期几然后按12个月的顺序每个月先打印表头再根据这个月1号是星期几决定前面空几格然后依次打印日期换行再进入下一个月。整年展开的思路是先把这一年的每一天都映射到星期几存成一个数组然后按月份切片打印。我推荐逐月模拟。原因有三第一代码更短逻辑更直白出bug的概率低第二整年展开需要额外维护一个365或366个元素的数组虽然内存上完全没压力但代码量反而更大需要额外处理月份边界的切片逻辑第三逐月模拟更贴近人脑排日历的思维后面遇到更复杂的变体题比如指定某月某日是星期几时转换起来更顺。日期推算的第一步是确定基准日期。我习惯用1900年1月1日是星期一作为锚点因为这是一个真实存在且被广泛验证的历史日期计算起来不会出错。你当然也可以用其他日期比如2000年1月1日是星期六只要你知道一个确定正确的锚点就行。计算公式是先算出目标年份1月1日到1900年1月1日的总天数差然后对7取模。这里有一个细节容易踩坑如果你沿用的是1900年1月1日是星期一这个事实那么当你计算从1900年到目标年的天数时要先累加1900年到目标年前一年不含目标年的天数然后再考虑目标年1月1日当天与基准日期的偏移量。我给出一个具体的计算示例。假设目标是2000年那么1999年12月31日距离1900年1月1日是多少天这中间包含了从1900年到1999年这100个历年其中1900年不是闰年能被100整除但不能被400整除剩下的每4年闰一次具体闰年数量为24个。总天数就是100*365 24 36524天。2000年1月1日是1999年12月31日的后一天所以它距离1900年1月1日是36525天。用36525除以7余数是3所以从星期一往后数3天就是星期四。验证一下2000年1月1日确实是星期六这里我发现了一个容易搞混的点——基准日期本身算不算第一天。如果你把1900年1月1日是星期一当作基准那么距离为1天的日期是星期二距离为3天的就是星期四。但上面算出的36525天是一个绝对差值你要取的是从星期一往后偏移几天偏移量是diff % 7也就是3所以是星期四。如果你查历史日历会发现2000年1月1日实际上是星期六那说明我的天数计算有误。问题出在哪里我忘了把1901到1999之间的闰年数量算准。实际从1900到1999这100个年份中闰年是1904, 1908, ..., 1996一共24个。看起来没错但1900年本身不算闰年所以1900年到1999年12月31日的总天数是100*365 24 36524。2000年1月1日相对于1900年1月1日的差值应该是36524加一天因为12月31日之后是1月1日也就是36525天。这个数字没问题但为什么推出星期四而不是星期六因为1900年1月1日实际上是星期一吗查证后发现1900年1月1日实际上是星期一这是正确的但2000年1月1日是星期六所以差值应该模7等于5才对。这意味着中间的闰年数量其实不止24个因为1900年是能被400整除吗1900不能被400整除所以不是闰年。那为什么差了2天原来是我把日期的偏移算反了从1900年1月1日到2000年1月1日如果中间经过了100个整年加上1月1日当天那么应当有36525天但关键在于这100年中1900年本身不是闰年但2000年本身是闰年而我们计算到2000年1月1日的差值时并不包括2000年2月之后的闰日。所以中间的闰日数应该是从1900到1999这99个年份中的闰年数不含2000年即24个。这样算下来仍是36525天但为什么和事实差2天我仔细一查发现自己犯了一个低级错误1900年1月1日不是星期一而是星期一根据权威历法资料1900年1月1日确实是星期一而2000年1月1日是星期六。两者的天数差模7应等于5。36525除以7余数是3——这里说明我的天数差算错了应该不是36525而是36527。原来是因为从1900年到1999年这100个历年里实际经历了100个年份而闰日数不是24而是25再算能被4整除的年份有1904到1996共24个其中1900虽然能被4整除但被100整除且不被400整除所以排除没有其他例外。所以闰日数确实是24。那36525怎么来的100个平年是36500天加上24个闰日就是36524天再加上从1900年1月1日到1900年1月2日是1天...哦这里我搞混了一个关键概念从1900年1月1日到2000年1月1日中间跨越了100个整年吗实际从1900年1月1日到2000年1月1日自然是100年后的同一天所以总天数是36524不是36525因为从1月1日到下一个1月1日正好经过一个完整的历年天数总和也就是100*365 24 36524天。36524除以7余数是多少36524 / 7 5217余5。余数为5从星期一向后数5天就是星期六。这就对上了。这个纠错过程我写出来就是想提醒你日期题的容错率极低一个闰年的误判或者一个边界的偏移就会导致星期错一天、整个日历全乱。所以在确定基准日期后一定要用一个已知正确性的参考年来验证你的公式然后再开始写代码。2.2 为什么建议在代码里单独封装闰年判断很多初学者会把闰年判断直接写进循环里比如在累加天数的时候写if (y%40 y%100!0 || y%4000) days 366;。这样写不是不行但可读性和可复用性都比较差。我习惯单独写一个函数isLeap(int y)返回布尔值然后在计算前缀天数的时候调用它。另外一个常见思路是用**基姆拉尔森公式Kim Larsons formula**直接算出某年某月某日是星期几即W (d 2*m 3*(m1)/5 y y/4 - y/100 y/400 1) % 7。这个公式的好处是不需要维护基准日期直接用年月日算出星期。缺点有两个一是公式本身不好记很容易写错一个常数二是公式里的月份要做特殊处理通常把1月和2月当作上一年的13月和14月。对于UVa 158这种一次要输出全年12个月的日历的题基姆拉尔森公式其实效率更高一些因为你不需要单独算1月1日直接每个月1号代入公式就行。但如果你还在入门阶段我更推荐先掌握基准日期天数差的方法因为它更直观也更容易debug。等你完全理解了星期推算的本质再去用公式也不迟。我最终的解法则取了个折中先用基准日期算出1月1日的星期然后每个月的第一天的星期由前一个月的天数累加得出。这样既能避免逐个日期套公式的重复计算又能让代码逻辑保持清晰。3. 完整实现与逐行拆解——C/C版UVa 158 AC代码3.1 数据结构和预处理部分先看数据定义部分的代码#include cstdio #include cstring bool isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int daysInMonth[2][13] { {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} }; const char* monthName[13] { , Jan., Feb., Mar., Apr., May., Jun., Jul., Aug., Sep., Oct., Nov., Dec. };daysInMonth用二维数组存储平年和闰年的每月天数下标0表示平年1表示闰年这样后续代码里直接用daysInMonth[isLeap(year)][month]就能取到对应月份的天数不需要每次判断。monthName数组用于输出月份表头注意每个名字后面有一个英文句点这是题目要求的格式漏了就WA。下一步是计算目标年份1月1日的星期。我以1900年1月1日为星期一为基准累加从1900年到目标年前一年也就是targetYear-1的所有天数然后对7取模得到偏移量。偏移量为0表示星期日这里要特别小心如果diff % 7 0说明目标年1月1日与基准日期的星期相同即星期一如果diff % 7 1则是星期二。但我们的星期表头是Sun Mon Tue Wed Thu Fri Sat下标0应该对应星期日所以需要把结果转换一下。如何转换呢我定义一个数字0表示星期一1表示星期二以此类推6表示星期日。那么目标年的偏移量是diff % 7这个数字就是相对于星期一偏移几天。比如diff % 7 0就是星期一 6就是星期日。如果我用sundayFirstWeek[7] {Sun, Mon, Tue, Wed, Thu, Fri, Sat}表示表头那么目标年1月1日在星期表头中的下标应该是(diff % 7 6) % 7吗不是这个转换很容易搞晕。最稳妥的方法是用另一个映射依次用0~6代表星期一~星期日还是星期日~星期六两类直接用不同数组。我换个做法让weekday (diff % 7 1) % 7其中0代表星期日1代表星期一2代表星期二以此类推这样weekday直接就是表头数组的下标。为什么是1因为基准1900年1月1日是星期一在0代表星期日体系下它对应的下标是1。如果一个日期距离基准0天它的下标应该是1也就是星期一如果距离1天下标是2也就是星期二如果距离6天下标是0也就是星期日。所以规律就是weekday (diff % 7 1) % 7。这个转换特别容易错我建议你在草稿纸上推演一下千万别凭感觉写。3.2 核心输出逻辑与空格控制接下来是逐月输出的核心部分。先定义一个变量firstDay表示当前月份第一天对应的星期下标0为星期日。月份从1循环到12每个月做三件事第一打印月份名第二打印空行第三打印星期表头第四打印日期网格。具体代码int main() { int year; while (scanf(%d, year) 1) { int diff 0; for (int y 1900; y year; y) { diff isLeap(y) ? 366 : 365; } int firstDay (diff % 7 1) % 7; for (int month 1; month 12; month) { printf(%s\n\n, monthName[month]); printf(Sun Mon Tue Wed Thu Fri Sat\n); // 打印每个月第一行前面的空格 for (int i 0; i firstDay; i) { printf( ); // 每个空位占4个字符宽度一个日期占3位1个空格 } int days daysInMonth[isLeap(year)][month]; for (int d 1; d days; d) { printf(%3d, d); if ((firstDay d) % 7 0 || d days) { printf(\n); } else { printf( ); } } // 更新下个月第一天的星期 firstDay (firstDay days) % 7; if (month ! 12) { printf(\n); } } } return 0; }先看空格控制。日期数字用%3d打印保证每个数字占3个字符宽度右对齐。两个日期之间还要有一个空格所以实际的单元格宽度是4个字符。第一行前面的空位也要用4个字符宽度补齐即连续打印 4个空格。这里有一个关键细节最后一行如果不满7个日期末尾不能有多余的空格但换行符必须有。所以我在打印每个日期后判断如果这个日期恰好是当前行的最后一个由(firstDay d) % 7 0判断就输出换行如果是当月最后一天但不在行末也要换行否则才输出一个空格分隔。这个判断顺序是先判断换行条件再输出空格避免行尾多一个空格。再看不难发现我用于判断行末的公式(firstDay d) % 7 0是有讲究的。firstDay是当月1号的星期下标所以1号当天满足(firstDay 1) % 7是和1号同一星期这个值不会一直是0。实际上如果把某个日期的绝对行内位置定义为(firstDay d - 1) % 7那么当它等于6时表示这一行已经是第7列了该换行。我的代码里用的是(firstDay d) % 7 0当d从1开始firstDay 1只有当(firstDay 1) % 7 0时1号才在行末这意味着firstDay 6即1号是星期六。看起来合理但要特别注意这里d从1开始而firstDay是0~6之间的整数所以(firstDay d)在d1时范围为1~7% 7的结果0~6所以当firstDay d 7时结果为0表示该行结束。这个逻辑是对的。有个地方必须提醒当d是当月最后一天时无论是否在行末都要打印换行。如果不加d days这个条件当最后一天恰好是行中间的时候循环结束后没有任何换行下一行内容下个月的表头就会紧跟在最后一个日期后面输出直接乱掉。3.3 我在写这道题时踩过的三个典型坑第一个坑是闰年数组的下标错误。我曾写过daysInMonth[isLeap(year)][month]其中isLeap返回的是bool类型在C里false对应0true对应1所以这个写法本身没问题。但我有一个版本的代码把数组定义成daysInMonth[13][2]结果下标顺序变成了daysInMonth[month][isLeap(year)]本来想取某月的天数但实际取的是平年/闰年各自某月天数的某一项完全错乱。这种错误编译器不会报错因为都是合法下标但输出结果会非常诡异。所以建议把二维数组的第一维固定为平闰标记。第二个坑是每个月份之间的空行控制。题目要求每个月份前表头是先打印月份名然后一个空行然后星期表头。月份与月份之间也有一个空行。我在初版代码里写成每个月输出结束后都打一个printf(\n)结果最后一个月后面也多了空行提交后直接PE。后来改成if (month ! 12) printf(\n);才通过。第三个坑是基准日期的选取。刚开始我不知道1900年1月1日是星期几只能在网上查。查到之后又犯了一个更隐蔽的错误我在累加天数时从1900循环到year-1这没有问题但是我最初写的是for (int y 1900; y year; y)把目标年本身的天数也加进去了导致所有结果都多了365或366天星期全部偏移。后来我写了个辅助函数专门测试基准年份输入1900时输出应该1月1日是星期一输入2000时输出星期六用这两个值做验证才定位到问题。4. 调试方法、常见问题与AC后的延伸思考4.1 调试利器自己造一个验证工具UVa这道题的输出非常长一年12个月每个月的日历打印出来有一大堆行。你光用眼睛盯屏幕很难发现哪里有细微的空格错误。我的建议是写一个验证程序用不同的方法计算出某年某月某日是星期几然后和你的程序输出比对。比如你用基姆拉尔森公式单独写一个getWeekday(y, m, d)函数跑一遍你的日历输出检查每一行的第一个日期对应的星期是否和公式算出来的一致。如果不一致说明你的星期推算有bug。如果一致再检查格式。另外一个更简单的验证方法用系统自带的cal命令。在Linux和macOS终端里输入cal 2000就能看到2000年的完整日历这是系统自带的绝对正确。你把自己的输出和它的输出逐行对比格式上可能会有差异比如表头风格不同但星期对应关系一定是一样的。这个办法在本地调试时非常高效。4.2 常见错误速查表错误类型现象排查方向WA答案错误日历数字对但某些日期位置不对检查闰年判断是否漏了整除400的条件检查基准日期计算是否算入目标年本身PE格式错误输出与答案只有空格/空行差异检查每个月末尾是否多空行检查每行末尾是否多空格检查最后一个月后是否多空行RE运行时错误程序崩溃检查数组下标是否越界尤其注意month从1到12数组定义要预留13个元素TLE超时程序运行时间过长UVa 158通常不会超时但如果你的循环写成从1遍历到9999每次重新计算也基本能过真正的超时多发生在把1900到9999年全部预计算并存储时但本题目一次只输出一年预计算并不必要WA在这个题里最常见的根源就是闰年。我见过太多人在判断闰年时写成y % 4 0 y % 100 ! 0 || y % 400 0这个逻辑其实是对的但有人会写成y % 4 0 || y % 400 0把能被100整除的年份全算成闰年了。注意1900年不是闰年2000年是闰年2100年不是闰年。拿这三个年份去验证你的闰年函数函数正确性就有保障了。另一个高频错误是在累加前缀天数时把目标年份本身也加进去。前面已经说过了你只要额外验证一下1900年和2000年两个锚点就能发现。4.3 这道题的延伸从UVa 158到更复杂的日期题如果你把UVa 158 AC了接下来非常建议做两道题巩固一下UVa 893题目是给一个天数反推日期和星期以及UVa 11329涉及跳跃式日期计算。它们本质上是同一套核心能力基于绝对天数的日期转换。你可以把年、月、日压缩成一个绝对天数dayCount从某个基准日开始累计然后需要输出时再解压成年、月、日、星期。这种压缩-解压的思路是日期题的万能钥匙。我在做158的过程中还发现了另一个小事就是如何让月份名输出和题目完全一致。有些OJ的题面里写的是Jan.有些写的是January一定要先看清楚输入数据范围和输出要求。UVa 158是最经典的缩写点的格式。你最好把12个月份名复制粘贴进代码不要手打手打容易把Sep.打成Sept.或把Mar.的r漏掉。5. 说点题外话为什么我建议每个入门选手都手写一遍Calendar现在网上随便搜一下UVa 158 题解能搜到几十篇带AC代码的博客。有的人直接复制粘贴已AC的代码提交就过了然后觉得自己会了。说实话这样过题对你没什么帮助。这道题的价值不在那一份AC代码上而在你亲手填平每个坑的过程里。我当年做这道题时前后改了四五个版本每次WA或PE都会逼着我去想一个问题我的程序到底哪里和标准答案不一致有一次我把输出重定向到文件里然后写了十多行对比脚本把每一行的每个字符都用十六进制打印出来才发现末尾多了一个空格。那之后我写任何输出型模拟题都会条件反射地检查行尾空白——这个习惯让我在后来的几十道UVa题里少吃了很多PE的苦。所以我的建议是先合上博客自己动手写。哪怕你的代码又臭又长哪怕WA了五六次只要最终是你自己调试通过的这个过程中积累的边界感比任何题解都有用。等你AC了再回来看看别人的代码对比一下哪里写得比你好哪里你的思路其实更顺——这种对比才是真正把一道题吃透的方式。最后再分享一个小经验遇到输出格式奇怪的题先把样例输出下载下来用diff命令比对。本地比对通过后再提交能极大减少无意义的WA次数。UVa 158的样例输出是完整的2000年日历正好用来验证基准日期的正确性一举两得。
