杭电OJ 2036~2045刷题攻略：贪心、递推与计算几何入门

1. 为什么是2036~2045：这道题号区间的含金量

如果你在杭电OJ（HDU Online Judge）上刷过题，大概率见过这个区间。对很多老ACMer来说，2036到2045这段题号，几乎就是“大一入门必刷清单”的代名词。我的记忆里，每年暑假集训队招新，学长给新人的第一张题单上一定有这几道，它们不像后面的难题那样劝退，但也绝不是随便写几行循环就能糊弄过去的水平。

先说结论：2036~2045是一个难度曲线设计得很讲究的题号区间。它的核心特点是“数学思维为主、代码量不大、陷阱隐藏得很深”。比如2036“改革春风吹满地”考的是多边形面积，2037“今年暑假不AC”考的是贪心，2045“不容易系列之(3)—— LELE的RPG难题”考的是递推。你可以明显感觉到，这些题考察的不是你会不会背某个算法模板，而是你能不能把题目描述转化成数学表达式，再用代码实现出来。

这个区间适合谁？我的建议是：刚学完C语言循环、数组、函数，准备进入算法竞赛门槛的新手，尤其是大一、大二学生。你要是能独立把这十题全部AC，基本说明你具备了“读懂题目、分析规律、处理边界、调试程序”的完整闭环能力。这也是为什么很多集训队面试会直接拿这个区间来筛人的原因。

有意思的是，这十道题虽然没有一道需要高级数据结构，但几乎每一道都有让新手“当场去世”的细节。有的题目数据是浮点数，有的是多组输入直到EOF，有的递推关系你得列到第10项才能发现规律。所以这区间刷下来，收获的不仅仅是十次AC的快乐，更是一整套“竞赛题该怎么读、怎么想、怎么避免踩坑”的方法论。

下面我把每一道题的核心思路、关键陷阱和实操细节逐一拆开讲。这不是题解的简单罗列，而是把我当年刷这些题的思考过程、踩过的坑、以及后来带新人时反复强调的点，全部摊开放在你面前。

2. 十道题逐一拆解：思路、陷阱、小技巧

2.1 2036 改革春风吹满地：多边形面积的几何直觉

这道题是我当年在这区间里卡得最久的之一，不是因为它难，而是因为我当时不知道“叉积”这个工具。题目要求计算一个简单多边形的面积，顶点坐标按顺序给出，有的还带小数。常规思路是把它分割成三角形，但如果你真的去一个个算三角形的底和高，那不仅麻烦，而且浮点误差大得离谱。

正解是利用向量叉积的几何意义：平面上任意三点A、B、C构成的三角形面积，等于向量AB和向量AC叉积的绝对值的一半。对于一个顶点按顺序排列的多边形，把第一个点当作基点，依次和其他相邻两点组成三角形，把所有叉积相加，最后取绝对值的一半就是总面积。为什么能直接叠加？因为叉积本身是有符号的，凸多边形的叉积同号，凹多边形的叉积有正有负，而求和的结果恰好自动抵消了凹进去的部分。这一点很关键，但我在当时完全没意识到，只记得“这样算出来是对的”。

实操上有几个细节必须注意：

• 顶点坐标用double存储，不要用int，因为题目坐标可能不是整数。
• 叉积求和的公式是sum += x1 * y2 - y1 * x2，注意下标循环时最后一个点要绕回起点。
• 输出的格式要求是保留一位小数，用%.1lf，我见过不少人忘了格式导致Presentation Error。

提示：如果这道题你看到“面积”两个字就直接套海伦公式，恭喜你，你已经踩进了精度陷阱。海伦公式在边长相差很大时误差很明显，而叉积法几乎不会出这个问题。

2.2 2037 今年暑假不AC：贪心的第一个里程碑

2045之前真正让新手体会“算法思想”的题，就是这道。它的经典程度不用多说，几乎每一本讲贪心的入门书都会拿它当例题。题目大意是你有一堆电视节目区间，每个节目有开始时间和结束时间，问你最多能完整看完多少个节目。

贪心策略是：按结束时间从小到大排序，优先选结束早的节目，然后从它结束的时间点继续找下一个开始时间不冲突的节目。这个策略的正确性证明其实很有意思——任何最优解的第一个节目，都可以被替换成“结束时间最早”的节目而不使结果变差，因为替换后留下的剩余时间只会更多。用数学归纳法可以严格证明，但我当年做题时只记了结论，后来带新人才认真推了一遍。

这道题有一个很容易忽略的点：节目的开始时间可以为0，结束时间也可以很大，所以时间轴的边界要处理干净。排序用结构体比较方便，直接用一个二维数组做冒泡排序也能过，数据量不大。但如果你用C语言写，排序的交换一定要把整个结构体整体交换，别只换了开始时间或结束时间，这种低级错误在OJ上会体现为“答案错误”而不是“编译错误”，排查起来很浪费时间。

2.3 2038：容易被忽略的一道基础题

2038在区间里的存在感相对低一些，但它代表的一类“纯模拟”题型很重要。很多新手刷题有个坏习惯：只看难度标签，觉得简单的跳过，难的不敢碰。但2038这种题恰恰是锻炼“把自然语言翻译成代码逻辑”的最好素材，它不考算法，就考你能不能老老实实把题目的模拟过程写对。

我的建议是，2038这类题你不要追求“优雅解法”，要追求“一次写对的能力”。比如变量初始化位置对不对、循环边界是小于还是小于等于、遇到特殊情况是否提前跳出，这些习惯都是在刷这类题时养成的。如果一道模拟题你交了三遍才过，别灰心，这才是常态。

2.4 2039 三角形：别被“判断三角形”四个字骗了

这题代码量不超过十行，但它坑了无数人。原因是题目要求输入三条边判断能否构成三角形，但输入数据可能是浮点数，可能顺序不固定，可能边长接近边界值。我看到过很多人在论坛上问：“为什么我判断a+b>c就是过不了？”

关键不在于逻辑，而在于两件事：

• 要用double读入三条边，不要用int。题目没说边是整数，你一用int，浮点数据直接被截断，边界情况必炸。
• 判断覆盖所有排列顺序。如果你只写了a+b>c，没对三条边做排序或穷举，那最长的边在c的位置时逻辑是对的，一旦最长边在a的位置，同样的三条边就会判错。

所以稳妥写法是先把三边排个序，让a <= b <= c，然后只判断a + b > c一次，顺便还能用c - b < a避免浮点误差导致的边界误判。这道题让我学会了一个很重要的习惯：涉及浮点数比较时，尽量转成差值与0的比较，或者用容差处理，别写等号。

2.5 2040 亲和数：约数计算的优化意识启蒙

2040是教你“不要真的从1循环到n去求约数”的第一课。题目让判断两个数是否是亲和数，所谓亲和数就是a的所有真约数之和等于b，且b的所有真约数之和等于a。我第一次写的时候从1循环到a/2，交了发现也能过，因为数据范围不大。但如果你把这种习惯带到后面的题里，比如2041那种递推，就会体会到什么叫“复杂度爆炸”。

虽然2040的数据范围让暴力也能过，但我还是建议你练习一下优化版：枚举到sqrt(n)，每找到一个约数就同时算上它对应的另一个约数。这样你能顺便学会“根号优化”这个以后高频使用的技巧。另外注意，真约数不包括自身，所以循环从1开始，并且约数成对时别把重复的加两次——比如n=16时，4是平方根，只能加一次。

2.6 2041 超级楼梯：递推思维的第一次正面交锋

2041算是一道递推基础题。题目是一段楼梯共有M级，每次可以走一级或两级，问走到第M级有多少种走法。这个问题的递推公式是f(n) = f(n-1) + f(n-2)，本质就是斐波那契数列。但很多人第一次看到会陷入“枚举法”的误区，试图把所有路径一条条列出来，M稍微大一点就直接爆。

关键认知是：你不需要关心每一步具体怎么走的，只需要关心“最后一步是从哪一级跨上来的”。走到第M级，要么从M-1级走一级上来，要么从M-2级走两级上来，所以方案数是两者之和。这种“倒推过去”的思维方式，是递推题的核心。以后遇到所有递推题，第一步一定是问自己：当前状态可以由哪些前置状态转移过来。

实现层面，M的范围通常不大，用long long存结果即可，甚至不需要用数组，三个变量滚动更新就行。但注意递推起点f(1)=1, f(2)=2，不要写成f(0)=1然后一路推到M，那样看起来对，但边界很容易错。

2.7 2042 不容易系列之二：递推里的“反向计算”

2042这道题很多人的第一反应是设变量然后正向模拟，但题目“过收费站交钱翻倍”的过程是逆着叙述的，你会发现正向模拟很容易绕晕。这种题型的通用解法是从终点倒推回起点，每次做逆运算。

举个例子，题目大概是说有一类收费站规则，每次过站交一定费用后剩余的钱再翻倍之类，最后问一开始有多少钱。如果你顺着题目给的顺序去算，每个“翻倍”之后还要判断“交的钱够不够”，容易漏掉状态。反过来，从最后剩余的1块钱出发，每一步做“除以2再加上交的费用”，逻辑就顺畅得多。

这题的教训很实用：当题目描述的过程是正向的，但问你初始状态时，优先考虑倒推。算法竞赛里很多递归、递推题目都是这种套路，练好倒推思维，后面做“约瑟夫环”“猴子选大王”之类的题会轻松很多。

2.8 2043 密码：字符分类统计的边界处理

2043考的是字符串处理，题目要求判断一个密码是否符合特定规则，比如长度范围、字符种类数量条件。这题本身不难，但它是区间里少有的“读入带空格的字符串”相关题目。如果你用scanf("%s")去读，遇到空格就断了，大概率会WA。

所以核心点在于：

• 如果密码可能包含空格，用gets或者getline读入整行，但注意前面的换行符要吃掉。
• 遍历字符串时对每个字符做ASCII范围判断，分别归为大写、小写、数字、其他符号四类。
• 统计完成后，根据题目要求的“至少包含几类字符”和长度限制输出YES或NO。

这题的坑主要在“其他符号”的处理上。很多人只判断了前三种，忘了题目里可能要求“除了字母数字以外的符号也计入一类”。所以读题时一定注意“字符种类”是三种还是四种。另外，字符串长度可能包含末尾的\0，不要拿strlen去和数组容量比较，要拿它和题目要求比较。

2.9 2044 一只小蜜蜂：递推的一次实际应用

2044同样是一个递推问题，背景是蜜蜂从某个编号格子爬向目标格子，只能沿特定方向移动，问一共有多少种路线。其实它本质也是斐波那契数列的变体，但比2041多了一点：不是从固定起点开始，而是任意两个格子之间。

这就意味着你不能套f(1)=1,f(2)=2的固定公式，而是要根据起点和终点计算“相差的步数”，然后求对应的斐波那契值。如果把起点终点都映射到一条直线上，问题就退化成“从第一格到第n格的走法”。很多人在这里犯错是因为没有做坐标换算：起点不是1，终点不是M，直接套递推公式，结果偏一位。

实操上，建议先把起点、终点的编号做差，得到距离，然后打一个表存斐波那契数列的前几十项。注意结果可能比较大，用long long存，别用int。这类“换了个背景的递推题”，本质是告诉你：递推不只是数学公式，它是在描述状态转移过程，背景信息需要你先抽象成状态。

2.10 2045 不容易系列之(3)—— LELE的RPG难题：递推加特殊约束

2045是这个区间里公认思维含量最高的一道题，也是很多人第一次接触“带约束的递推”或者“环形排列”类问题。题目背景是n个格子排成一排，三种颜色涂色，相邻格子颜色不同，而且首尾颜色也不同，问有多少种涂法。

第一步要意识到：首尾颜色不同这个要求，把问题从“线性排列”变成了“环形排列”的边界约束。如果只是线性相邻不同，那就是简单乘法原理：首格3种，后面每格2种，一共3 * 2^(n-1)种。但首尾颜色也必须不同，直接乘就会多出一堆首尾相同的情况。

递推的关键思路是分两类讨论。假设前n-1个格子已经满足相邻不同且首尾不同，那么第n个格子只能涂一种颜色（因为要同时和n-1格不同、和首格不同）。但如果前n-1个格子的首尾是相同的，那第n个格子反而有两种涂法。所以你设两个状态分别表示“首尾相同”和“首尾不同”的方案数，然后建立状态转移。

具体推导一下：

• 用same[n]表示长度为n、首尾颜色相同的合法涂法数，diff[n]表示首尾颜色不同的合法涂法数。
• 考虑在长度为n-1的基础上在末尾加一格，末格颜色取决于倒数第二格和首格的约束。
• 最终答案是diff[n]。

这个分类思想非常值得反复咀嚼，因为后面你会遇到更多“有附加条件的递推”，比如环形染色、不相邻问题等，通用的手段就是引入多个状态变量，写状态转移方程，甚至可以写成矩阵快速幂。一道2045，可以说是递推从“套公式”到“自己设计状态”的转折点。

3. 从读题到AC的完整实操流程：一个可复制的做题方法论

这一节不针对某一题，而是把刷2036~2045这类区间题时，我个人验证过无数遍的完整流程分享出来。这个过程写下来很朴素，但你对每一道题都走完一遍，效率会明显提高。

第一步，读题三遍。不是夸张，是真读三遍。第一遍看整体：输入是什么、输出是什么格式。第二遍看边界：数据范围多大、是否多组输入、坐标是否可能为负、有没有浮点数。第三遍找陷阱：题目描述里有没有“不保证按顺序”“可能包含”这类关键词。做完这三件事再动手写代码，能减少80%的无效提交。

第二步，动手推演一个小样例。用题目给的样例不够，你要自己构造一个更小的特例，比如n=3、4，或者在纸上画一个多边形，把叉积手算一遍。这一步看起来浪费时间，但能真正暴露你对题意的理解偏差。我见过太多人代码逻辑“应该对”，但因为一开始题目理解错，白折腾半小时。

第三步，编码时坚持“先搭框架后填细节”。先写主函数结构：读入、循环、核心函数，再往里填算法逻辑。这样即使中途发现思路不对，改起来也快。尤其在2045这种递推题里，建议把状态数组的推导过程先用注释写在代码上方，边写边对照。

第四步，自测极端数据后再提交。训练营里很多新人交题前只测样例，样例过了就交，结果WA了完全懵。实际上你只需要再多测三种情况：最小值、最大值、特殊情况。比如2036的三角形退化成一条线，2041的M=1，2043的空字符串。这些数据不在样例里，却能让你代码里的低级缺陷现出原型。

一个完整的做题时间分配建议是这样的：读题思考占40%，编码占30%，调试测试占30%。很多人反过来了——题目没想明白就急着敲键盘，结果调试占70%。这不是熟练度问题，是习惯问题。

4. 新手最容易踩的坑：我从这十道题里总结的排查经验

刷完2036~2045，有几类错误几乎所有人都会遇到，这里统一整理出来，方便你对号入座。

先说多组输入。杭电OJ很多题目都是“多组测试数据，以EOF结束”，这是新手最容易懵的地方。正确写法是while(scanf("%d", &n) != EOF)，在C++里也可以用while(cin >> n)。如果你少写了这个循环，往往只能过第一个样例，或者一直等输入导致超时。这在2036到2045的区间里很常见，尤其2036、2037、2040、2041、2043、2044都是多组输入。

再说数组大小。2044和2045需要打表，如果你把表的大小只开到50，测试数据一大就越界。更隐蔽的是，2045的状态数组下标从0还是1开始计算，直接决定递推公式能不能套对。我见过有人diff[1]=0, diff[2]=6推得好好的，换到diff[0]=0, diff[1]=3就全错，其实就是起始状态设置的问题，排查时一定要回到定义上。

还有一个很容易被忽略的坑——输出格式里的空格和换行。杭电OJ的输出判断是严格逐字符比较的，多一个空格或少一个换行都算Presentation Error。2036保留一位小数，如果你的位数不对，系统会报PE而不是WA，不要误以为代码逻辑错了。类似地，2037每种结果之间有没有空行，要看题目描述，有的题要求“每组输出后加一个空行”，有的不需要，建议写完对照样例输出逐字符核对。

最后说一个比较抽象的坑：当你在本地编译器跑通，交到OJ上却WA，第一步先怀疑你的编译器是不是对你太宽容了。比如某些旧编译器允许gets，但OJ的编译环境可能已经不支持；变量未初始化在本地可能是0，在OJ上可能是随机值。我刷这十道题时的体会就是：本地跑通只是必要条件，在OJ上“一次AC”才是真正的检验，而你唯一能做的是让自己的代码更规范、更少依赖未定义行为。

5. 这十题刷完之后，下一步该往哪走

很多人刷完2045会觉得“我是不是已经会递推了”，这个想法很危险。2041和2044的递推是“一眼就能看出来数列”，2045才开始涉及“自己设计状态”，而真正的递推动态规划，比如背包、区间DP、状压DP，远比这复杂得多。但如果你把2045的“分类讨论状态转移”吃透了，后面接触动态规划时会发现思维路径是相通的。

我个人建议的延伸路径是这样的：

• 2041之后去刷HDU 2013、2018，巩固基础递推。
• 2045之后去刷HDU 2064、2068，体会“带特殊条件的递推”可以变形到什么程度。
• 2037之后去刷LYOJ或者POJ里的区间贪心，理解“排序+扫描”这个套路还能用在哪些场景。
• 2036之后去刷凸包、点在多边形内判断这类计算几何入门题，你会发现叉积永远是最底层的工具。

不要贪多，一道题吃透，比自己闷头交十道“看了题解才AC”的题有价值得多。我在带集训队的时候经常说：100道水题堆不出一个竞赛奖，但20道题如果每一道都能讲清楚为什么这么做、什么时候不能这么做，那效果远超题海战术。

另外给一个刷题节奏的建议：这十道题不要一次性一天刷完。分成三天，每天三四道，中间穿插复盘。第一天刷模拟和几何，第二天刷贪心和字符串，第三天集中攻递推。每刷完一组，花二十分钟把代码重新看一遍，把注释补上，把当时卡住的点记在笔记里。过一周再回来重做一遍，看看能不能不查资料直接AC。这种“间隔重复”比连续刷十遍更有效。

我在实际刷题过程中的一个小习惯，最后分享给你：每AC一道题，我会在代码文件头部写三行注释，第一行是这题的核心思路，第二行是我第一次犯的错，第三行是如果用不同的方法还能怎么做。这个方法坚持一年以后回头看，那些注释比任何题解都珍贵，因为它记录的是你自己的思维漏洞，而不是网上的标准答案。刷完2036到2045，如果你能在每个文件里写下这行注释，就不虚此行。