百炼OJ算法刷题：日期算法错题本Vol.8-2964:日历问题
前言：
在算法题里，有一类题几乎每个人都会遇到：
日期 / 星期计算题。
给你一个起始日期和若干天数，让你求最终的年月日与星期。
乍一看很简单，但真正写代码的时候就会发现问题：
闰年规则
不同月份天数
星期循环
年份变化
日期边界
这些细节如果处理不好，程序就会出错。
这类题其实是一个非常典型的“时间模拟问题”。
它不仅考察代码能力，更考察对时间结构的建模能力。
这篇文章记录了我完整解决日历问题（POJ 2964）的思考过程。
一、题目回顾：日历问题
题目描述
在我们现在使用的日历中：
闰年：能被 4 整除
但能被 100 整除而不能被 400 整除的不是闰年
例如：
| 年份 | 是否闰年 |
|---|---|
| 1600 | 是 |
| 1700 | 否 |
| 1800 | 否 |
| 1900 | 否 |
| 2000 | 是 |
现在给定：
从 2000 年 1 月 1 日开始经过的天数。
要求输出：
YYYY-MM-DD DayOfWeek其中 DayOfWeek 为：
Sunday Monday Tuesday Wednesday Thursday Friday Saturday已知：
2000-01-01 是 Saturday输入格式
多组数据，每行一个整数：
days最后一行：
-1输出格式
YYYY-MM-DD DayOfWeek样例输入
1730 1740 1750 1751 -1样例输出
2004-09-26 Sunday 2004-10-06 Wednesday 2004-10-16 Saturday 2004-10-17 Sunday二、直觉解法：时间模拟
2.1 核心思路
这类题最自然的想法是：
把时间当作一个可以逐层减少的结构。
我们从大到小处理：
天数 → 年份 → 月份 → 日期具体流程：
1️⃣ 先减去整年的天数
2️⃣ 再减去整个月的天数
3️⃣ 剩下的就是日期
同时：
星期 = (起始星期 + 经过天数) % 7三、关键模块拆解
为了让代码结构清晰，我们可以拆成几个函数。
3.1 判断闰年
闰年规则：
能被4整除 但能被100整除且不能被400整除的除外代码实现：
bool leap(int y){ return (y%4==0 && y%100!=0) || (y%400==0); }3.2 获取月份天数
不同月份天数不同。
31天：1 3 5 7 8 10 12 30天：4 6 9 11 2月：28 或 29代码：
int mdays(int y,int m){ int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; if(m==2 && leap(y)) return 29; return d[m]; }3.3 星期计算
已知：
2000-01-01 是 Saturday我们定义星期编号：
| 数字 | 星期 |
|---|---|
| 0 | Saturday |
| 1 | Sunday |
| 2 | Monday |
| 3 | Tuesday |
| 4 | Wednesday |
| 5 | Thursday |
| 6 | Friday |
于是：
weekday = days % 7四、完整算法流程
我们从2000-01-01开始模拟。
第一步：计算年份
循环减去年份天数：
365 或 366直到剩余天数小于一年。
第二步：计算月份
循环减去每个月天数：
1月 → 2月 → 3月 ...直到剩余天数小于当月天数。
第三步：计算日期
剩余天数 + 1：
day = days + 1第四步：计算星期
weekday = total_days % 7五、完整代码实现
#include<iostream> #include<iomanip> using namespace std; bool leap(int y){ return (y%4==0 && y%100!=0) || (y%400==0); } int mdays(int y,int m){ int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; if(m==2 && leap(y)) return 29; return d[m]; } int main(){ int days; string w[7]={ "Saturday","Sunday","Monday", "Tuesday","Wednesday","Thursday","Friday" }; while(cin>>days && days!=-1){ int total=days; int y=2000; while(days >= (leap(y)?366:365)){ days -= leap(y)?366:365; y++; } int m=1; while(days >= mdays(y,m)){ days -= mdays(y,m); m++; } int d=days+1; cout<<y<<"-" <<setw(2)<<setfill('0')<<m<<"-" <<setw(2)<<setfill('0')<<d<<" " <<w[total%7]<<endl; } }六、时间复杂度分析
算法复杂度：
| 部分 | 复杂度 |
|---|---|
| 年份循环 | O(年份数) |
| 月份循环 | O(12) |
| 总复杂度 | O(years) |
由于年份最大不会超过 9999，这个复杂度完全可接受。
七、日期问题的核心模板
其实所有日期题都可以归纳为一个模板：
模板一：星期计算
weekday = (start_week + days) % 7模板二：日期推算
while(days >= year_days) days -= year_days while(days >= month_days) days -= month_days day = days + 1模板三：月份循环
next_month_week = (current_week + month_days) % 7掌握这三个模板，绝大多数日历类算法题都能解决。
八、这类题的识别指南
如何一眼看出是日期模拟题？
一般有以下特征：
✅ 给定某个起始日期
✅ 给定天数或时间差
✅ 要求计算未来日期
✅ 涉及闰年或星期
常见题型：
日历问题 Friday the 13th 日期推算 日期差计算九、写在最后：时间也是一种数据结构
这道题让我第一次意识到：
时间其实也是一种结构化数据。
年份 → 月份 → 日期 → 星期
它们之间存在非常清晰的层级关系。
当我们把时间拆解成这些结构后，问题就变得非常清晰。
很多算法题其实也是这样：
看似复杂
其实只是结构没有拆清楚
当你建立好模型，代码就会自然出现。