1. 先把题意拆明白UVa 158 到底在考什么1.1 输入输出长什么样UVa 158 Calendar 这道题几乎每个刷算法题的人都和它打过照面题单里它排得很靠前看着也简单——给一个年份和一个月份把整个月的日历按星期排出来。可真正动手写的时候新手基本都会卡在三个地方闰年规则记混、某天是星期几算不对、输出格式反复出现 Presentation Error。先约定一个最常见、也是网上大多数解法采用的题面格式多组输入每组一行两个整数year和month比如2000 2。对每一组输出该月的月历。标准输出长这样Calendar for 2000-02 Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 7 8 9 10 11 12第一行是Calendar for YYYY-MM第二行是七个固定的星期缩写第三行开始就是日历格子。2000 年 2 月 1 日是星期二所以 1 号从第二列开始排。年份范围在原题里给得很宽基本覆盖 1 到 3000 年所以不能靠“把某几个特殊年份打表”偷懒必须写出通用的日期计算。1.2 三个核心难点拆解第一是闰年判定。绝大多数人知道“四年一闰”但世纪年怎么处理才是这道题真正想考的点。第二个难点是“某月 1 号是星期几”这需要从日历系统本身找规律用累加法、公式法或者查表法都能解决但每种方法都有自己的坑。第三个难点是输出格式空格多一个少一个、空行位置不对、月份没补零都可能让你在评测系统里吃到 PE。其实这道题的价值不在于算法有多难而在于它是“日期模拟”这类题的标杆。很多后续问题比如判断两个日期相差多少天、计算某天是周几、生成整年日历核心逻辑都和 UVa 158 一模一样。把这道题弄透后面遇到日期题基本就是换壳。1.3 动手写代码前先问自己三个问题我在带新手的时候会让他们先回答三个问题再开始写。第一这一年到底使用哪套“历法规则”是儒略历还是格里高利历UVa 158 明确要求使用格里高利历也就是我们现在用的公历闰年规则是“能被 4 整除但不能被 100 整除或者能被 400 整除”。第二你的星期计算锚点是什么我习惯用 2000 年 1 月 1 日那天是星期六这是一个被广泛验证过的可靠起点。第三输出格式是整月月历还是只要星期序号题目原文写了什么就必须严格遵守这个等到后面讲格式坑的时候再展开。2. 日历计算的底层原理闰年规则与星期锚点2.1 闰年规则的来历为什么是 4、100、400 这三个数很多人背规则很熟练但不知道背后的道理遇到题目版本一变就容易慌。回归年地球绕太阳一圈大约是 365.2422 天。儒略历简单粗暴规定每 4 年一闰平均下来一年是 365.25 天比实际多了 0.0078 天。这个误差看着小积累 400 年就多出大约 3 天导致春分日期越来越漂移。格里高利历的修正思路是每 400 年只保留 97 个闰年而不是儒略历的 100 个。具体做法就是“能被 100 整除但不能被 400 整除”的年份不算闰年。这样算下来格里高利历的平均年长是 365 97/400 365.2425 天和真实回归年的误差缩小到每年约 0.0003 天大约三千多年才会差出一天。所以代码里的闰年判断长这样bool isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); }还有一个非常实用的隐藏规律400 年刚好是 146097 天而 146097 7 × 20871能被 7 整除。这意味着格里高利历的“星期模式”每 400 年完全重复一次2000 年和 2400 年的日历长得一模一样。这个性质后面可以用来做 O(1) 优化。2.2 锚点推导法把“星期几”变成可计算的数星期几本质上是“从某个已知星期几的日期开始经过了多少天”的取余问题。我选 2000 年 1 月 1 日作为锚点已知它是星期六。用 0 表示星期天、1 表示星期一……6 表示星期六那么计算某年某月 1 号的星期序号就是weekday_of_day1 (6 days_from_2000_01_01(year, month)) % 7days_from_2000_01_01由两块组成从 2000 年到目标年份之间所有完整年份的天数加上目标年份中 1 月到目标月份之前所有完整月份的天数。我举个完整例子算 2015 年 2 月 1 日。2000 到 2014 共 15 年其中 2000、2004、2008、2012 是闰年所以这些年贡献 15 × 365 4 5479 天。再加上 2015 年 1 月的 31 天总天数是 5510 天。5510 除以 7 余 1星期六序号 6 加 1 等于 7模 7 后是 0也就是星期天。查真实日历2015 年 2 月 1 日确实是星期天对上号了。2.3 三种算法方案对比除了锚点累加法还有两个常见方案。第一个是蔡勒公式Zellers Congruence它是纯数学的 O(1) 计算适合对公式敏感的人缺点是公式稍长记错一个符号结果就完全不对。第二个是打表法把一段范围内的星期数据预先算好存起来适合年份范围固定的题目但范围一旦扩大就失去通用性。方案理解难度出错风险适用场景锚点累加法低低绝大多数字典题推荐新手蔡勒公式中中追求 O(1)、熟悉公式推导打表法/暴力查表低高范围受限固定年份段的离线预计算我的建议是日常练习优先用锚点累加法原因是它的每一步都可以用真实日期验证。等熟练之后再尝试蔡勒公式毕竟代码简洁也是优点。3. C 实现把日历算得又快又准3.1 三个工具函数先行写日期题最忌讳把逻辑全塞在 main 里。我会先拆出三个工具函数isLeap判断闰年、daysInMonth返回某年某月的天数、daysFromAnchor计算从锚点日期到目标月份 1 号的天数差。#include cstdio const char* WEEK_NAME[] {Sun, Mon, Tue, Wed, Thu, Fri, Sat}; int normalDays[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool isLeap(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } int daysInMonth(int y, int m) { if (m 2 isLeap(y)) return 29; return normalDays[m]; }这里有个我踩过的坑月份数组的下标一定要窝心从 1 开始也就是第 0 位填 0这样daysInMonth(y, 1)自然返回 31不会出现“月份减一”的混乱。另外 2 月的 29 天必须单独处理否则闰年的 2 月会直接少算一天。3.2 计算某月 1 号的星期序号daysFromAnchor是核心。从 2000 年到y之间每经过一个完整年份累加 365 或 366再累加y年 1 月到m-1月的天数。这里要特别注意y 2000的情况不能直接写一个从 2000 递增到y的循环因为那样循环体根本不执行得到的天数永远是 0。int daysFromAnchor(int y, int m) { int total 0; if (y 2000) { for (int i 2000; i y; i) total isLeap(i) ? 366 : 365; } else { for (int i y; i 2000; i) total - isLeap(i) ? 366 : 365; } for (int i 1; i m; i) total daysInMonth(y, i); return total; } int firstDayWeekday(int y, int m) { // 2000-01-01 是星期六序号为 6 return ((6 daysFromAnchor(y, m)) % 7 7) % 7; }firstDayWeekday里最后那个7) % 7是专门处理负数的。C 的取模对负数不是数学意义上的取余如果不做归一化年份早于 2000 时可能算出负数星期序号。3.3 输出格式对齐与空格是重灾区日历输出的本质是给每个格子腾 4 个字符的位置数字用 3 位宽度右对齐再加 1 个空格作为列间距。星期缩写的长度正好也是 3天然对齐。星期天这一列后面不需要多余的尾部空格否则在严格的评测系统里就是 Presentation Error。int main() { int y, m; bool firstCase true; while (scanf(%d%d, y, m) 2) { if (!firstCase) puts(); firstCase false; printf(Calendar for %04d-%02d\n, y, m); for (int i 0; i 7; i) printf(%s%c, WEEK_NAME[i], i 6 ? \n : ); int w firstDayWeekday(y, m); int totalDays daysInMonth(y, m); for (int i 0; i w; i) printf( ); for (int day 1; day totalDays; day) { printf(%3d, day); if ((w day - 1) % 7 6 || day totalDays) printf(\n); else printf( ); } } return 0; }printf( )输出 4 个空格恰好占满一个空列。日期输出的判断条件是“到了星期六换行或者今天是本月最后一天换行”这两个条件缺一不可否则月底那一行可能没换行导致和下一组输出粘连。3.4 关于月份和年份的格式细节%04d-%02d会把年份补足 4 位、月份补足 2 位这是我在题面基础上做出的一个常见约定。如果原题要求年份不补零改成%d即可。这一步是很多代码风格不统一的人反复 PE 的根源我的建议是提交前先去题面确认到底要Calendar for 2000-02还是Calendar for 2000-2确认无误再提交别赌。4. 实测与离线自测在 WSL2 里把正确性磨出来4.1 手写样例与期望输出对照我对这道题做了几组手工验证其中最有价值的四个用例是闰年的 2 月、普通年的 2 月、平世纪年能被 100 整除但不能被 400 整除、闰世纪年。这四个边界把闰年判断的每一条分支都覆盖了。输入期望关键结果2000 22000-02-01 是星期二2 月共 29 天2015 22015-02-01 是星期天2 月共 28 天2100 22100 年不是闰年2 月共 28 天2 月 1 日是星期一2000 32000-03-01 是星期三说明前面 2 月的 29 天生效了按上面的代码跑一遍输出应该和cal 2 2000、cal 2 2100这类系统日历完全一致。2100 是最容易翻车的一个用例因为很多人的闰年判断只写了y % 4 0这样会把 2100 错误地当成闰年导致 2 月多输出一天。4.2 WSL2 环境下的编译运行我平时在 WSL2 里写算法题编译运行就三行命令g calendar.cpp -o calendar ./calendar input.txt cat output.txt如果没装 g先执行sudo apt install g。WSL2 的好处是纯 Linux 环境自带cal、diff、python3这些对拍工具不用再折腾虚拟机。用cal 2 2100直接人工比对或者把程序输出和系统日历放在一起./calendar input.txt my_output.txt cal 2 2100另外可以用 Python 的calendar模块做大规模随机验证。calendar.weekday返回周一为 0、周日为 6转换成“周日为 0”的序号只需要加 1 再模 7import calendar def first_weekday_sun0(y, m): return (calendar.weekday(y, m, 1) 1) % 7 for y in range(1, 10000): for m in range(1, 13): assert first_weekday_sun0(y, m) reference_cpp_first_weekday(y, m)这种对拍脚本只要跑几分钟就能把从公元 1 年到 9999 年所有月份的星期序号全部验证一遍比自己肉眼查快得多。4.3 评测网站暂时不可用的离线验证三板斧有阵子经常在群里看到有人问“wsl2 uva is not available”“在线评测的网站打不开怎么办”。我的处理方式很固定不干等把离线验证三板斧用起来。第一板斧是样例测试原题给的样例输入输出先跑通。第二板斧是系统工具交叉验证上面说的cal和 Pythoncalendar就是现成的校验器覆盖范围比样例大得多。第三板斧是边界清单自查把年份 1、2000、2100、2400、9999月份 1、2、3、12以及“月初是星期天”“月末落在星期六”这些特殊形态全测一遍。这样即使网站恢复之前我也已经把自己的代码验证得差不多了恢复后直接提交不会浪费时间。5. 常见问题与排查技巧实录5.1 星期几总是差一天这是日期题里最常见的 bug最隐蔽的原因有三个。一个是锚点记错比如把 2000-01-01 记成星期天那所有结果都会偏移一天。第二个是 1 月 1 日的序号计算方式不对累加天数时错误地把目标月份的当月也加进去。第三个就是负数取模问题年份早于锚点年份时天数差是负数C 的%会给你一个负结果必须做归一化。我自己的建议是把“2000-01-01 星期六”和“1900-01-01 星期一”这两个锚点背死。1900-01-01 是星期一同样是经过验证的多一个锚点自查交叉验证的时候会更安心。5.2 Presentation Error多余空格、空行与位数UVa 158 这类老牌题目对输出格式的挑剔程度比现代评测系统高得多。常见的 PE 原因有这么几个日历格子之间用了 Tab 而不是空格每行行尾多打了一个空格每组日历之间空行了或者没空行月份输出没有补零最后一组输出后多加了一个空行。我的经验是用“每组之间空一行最后一组不空行”的写法也就是代码里的firstCase标记方式。如果你拿到的题目明确写了“每组结束后空一行”那就反过来实现。无论如何必须以题面文字为准出题人的说明比任何网上模板都优先。5.3 边界年份和闰年的坑年份为 1 时循环计算要正确年份为 9999 时累加天数会很大但只要用long long或者直接对 400 年周期取模就不会超出int范围。这里强烈推荐一个优化因为格里高利历每 400 年就是一个完整星期循环可以先对年份取y % 400再计算不仅更快还天然规避了超大整数问题。还有一个很经典的坑是“公元前”或者“0 年”。原题一般只给正年份但如果遇到类似题目务必确认是否包含公元 0 年这里不做假设以题目陈述为准。5.4 问题速查表症状最可能原因处理方式所有日期星期序号统一偏移锚点星期记错用真实日期验证锚点闰年 2 月只输出 28 天漏了 2 月的特殊处理单独判断 2 月2100 年被当成闰年闰年判断少了% 100条件使用完整闰年公式年份小于锚点年份时结果错乱负数取模未归一化使用(x % 7 7) % 7行尾多空格、间距不对空格数没按列宽打统一用 4 字符列宽输出粘连、没有空行缺空行标记或月末换行条件缺失用firstCase控制空行6. 从一道题到工程实践日历逻辑的“版本对应”6.1 开源日历应用里的同一套逻辑你以为日历计算只在刷题时有用其实真实产品里的核心逻辑一模一样。比如开源生态里常见的 Fossify Calendar也就是社区接续维护的一个安卓日历应用它处理每月排布、跨月事件、重复事件时底层也要算“某月 1 号是星期几”和“这个月有几天”。事件能不能正确落在周一的位置依赖的依然是我们上面写的这套闰年规则和星期推导。区别在于工程版要考虑更多用户自定义每周从星期几开始、时区切换、夏令时、农历和公历并行展示。但所有复杂功能的基础都是那道 UVa 158 练过的“给定年月输出月历”。如果你有机会读开源日历的代码会发现它们的日期工具类里days_in_month、is_leap_year这些函数命名和题解里几乎如出一辙。6.2 v-calendar 的版本对应组件与框架版本怎么配另一个和“版本”相关的常见问题来自前端领域。很多人在 Vue 项目里用 v-calendar 这个日历组件却搞不清楚“v calendar 版本对应”到底怎么匹配。简单记v-calendar 的 2.x 对应 Vue 23.x 对应 Vue 3。安装时用npm install v-calendar^2和npm install v-calendar^3分别对应装错大版本会导致插件注册报错、组件不渲染。这恰好和日历系统本身的发展形成对照儒略历和格里高利历就是两套“大版本”它们的闰年规则不同你必须确认自己处理的是哪个版本才能决定某一年是否算闰年。做日期开发时我习惯先写清楚“当前模块遵循格里历规则”这个前提再开始计算这和先确认 v-calendar 的版本再写组件是一个道理。6.3 再往下可以怎么练如果这道题你已经能一遍 AC我建议往三个方向扩展。第一把daysFromAnchor重写成基于 400 年周期的 O(1) 版本彻底吃透“146097 天恰好是整数周”这个性质。第二研究蔡勒公式和末日算法Doomsday Algorithm掌握多种星期计算方案以后碰到不能用累加法的海量查询场景才不会慌。第三把程序改造成支持“每周从周一开始”“输出英文月份名”“生成全年日历”等变体需求这就是从刷题到做产品的第一步。最后说一点个人体会。我当年第一次交 UVa 158 就是 PE被格式教育之后养成了两个习惯一是固定用“4 字符列宽”来想所有日历输出二是写日期代码前永远先写注释“anchor: 2000-01-01 Saturday”。这两个习惯后来帮我解决了不少更复杂的日期题。如果你也经常在日期计算上翻车强烈建议先把这两个锚点记死再动手写循环。