1. 刷爆杭电oj 2036~2045十道题里的计算几何与细节陷阱如果你在ACM入门阶段刷过杭电oj大概率对这十道题有印象。2036改革春风吹满地、2037今年暑假不AC、2038、2039三角形、2040亲和数、2041超级楼梯、2042不容易系列之二、2043密码、2044一只小蜜蜂、2045不容易系列之三——乍一看题目零散实际覆盖了计算几何、贪心、递推、字符串、数论等多个基础模块。这篇文章把这十道题放在一起复盘按题型拆解核心解法重点讲每道题里“不写代码根本发现不了”的坑。适合正在刷题入门、想系统整理基础题型或者准备比赛前快速回顾的同学。这批题从难度看偏基础但基础不代表没价值。很多人刷到2036就卡在多边形面积公式上刷到2037又容易在排序策略上绕弯2038和2043则藏了不少输出格式的细节。把这些题吃透等于把计算几何入门、贪心排序、递推建模、字符串哈希这些基本功都过了一遍。下面按题目顺序逐道拆。2. 计算几何入门2036与2039的多边形、三角形面积2.1 2036 改革春风吹满地——多边形面积怎么算才不掉坑这道题问的是任意多边形的面积。输入按逆时针或顺时针给出一组顶点坐标要求输出面积。表面看是初中几何真上手才发现有两个关键点一是多边形不一定是凸的二是坐标是整数但面积可能是小数。先给出标准做法绝大多数人刷这题用的都是鞋带公式又叫叉积求和法。对于顶点按顺序排列的多边形面积等于S |sum(x[i] * y[i1] - x[i1] * y[i])| / 2其中i从0到n-1i1对n取模也就是最后一个点和第一个点也要算一次。这个公式的本质是把多边形看作从原点出发的若干个三角形每个三角形的“有向面积”用叉积算出来再累加。因为每个三角形都有方向凹多边形内部会被正负抵消最终剩下的就是真实面积。我的建议是代码里连绝对值都别急着加先累加叉积和输出时再判断正负。因为如果顶点是顺时针给的sum是负值取绝对值就完事。实测下来用double存坐标和结果最稳很多人图省事用int或float结果在坐标值偏大时出现精度误差WA了找不到原因。这题的坑就在这理论上坐标范围不大但面积计算涉及1/2float的有效位数在累加多次后很容易丢精度。#include stdio.h #include math.h int main() { int n; while (scanf(%d, n) n) { double x[105], y[105]; for (int i 0; i n; i) scanf(%lf %lf, x[i], y[i]); double sum 0; for (int i 0; i n; i) { int j (i 1) % n; sum x[i] * y[j] - x[j] * y[i]; } if (sum 0) sum -sum; printf(%.1lf\n, sum / 2.0); } return 0; }注意输入以n0结束这是杭电常见的终止条件别漏判。另外要提醒一点有人会试图把多边形分割成三角形用海伦公式一个个求面积再加起来。对凸多边形这没问题但凹多边形这么干会算出重叠区域的面积结果偏大。鞋带公式好在不需要判断凹凸性直接通用。2.2 2039 三角形——判定条件背后的数论直觉2039题目很简单输入三条边判断能否组成三角形。按一般思维两边之和大于第三边三个条件都满足就行。但真正写过一遍会发现这题坑在数据类型。题目说的是“输入三边长度”但没明确说一定是整数。很多人按照习惯用int存判断两边之和是否大于第三边。这时候如果输入是浮点数比如0.5、0.6、1.0int会直接截断判断结果全错。正确做法是全部用double读入再判断。判断本身不用三条都写最稳妥的写法是排序后只要最大边小于两边之和即可因为排序后较小两边的和如果已经大于第三边其他两个不等式自然满足。不过我实测写三个条件也不会错因为三个不等式在数值上等价只是多几行代码而已。还有人追求“效率”想用两边之差小于第三边来替代这在数学上完全等价但浮点运算时减法可能带来额外误差建议老老实实用加法判。最后输出大写YES或NO注意大小写。2.3 计算几何的训练思路先背公式再理解本质这两道题放在一起看其实是同一类数学工具用向量叉积处理面积用不等式处理几何约束。对新手来说刷完这两题最好能做一个小结——鞋带公式除了算多边形面积还能用来判断顶点顺序、计算凸包面积三角形不等式则是所有几何约束判断的基础后面做线段相交、点在多边形内都会反复用到。所以别急着刷下一题先自己写一遍2036再试试把顶点顺序改成顺时针输入看输出会不会变成负值再想想要不要加绝对值。这些细小的实验比多刷十道题更能加深理解。3. 贪心排序与递推建模2037、2041、2042、20443.1 2037 今年暑假不AC——区间贪心的标准范式这道题是典型的“活动安排问题”输入若干个电视节目的开始时间和结束时间问最多能完整看完几个。标准解法是按结束时间升序排序然后贪心地选择结束时间最早、且不与已选节目冲突的节目。很多人刚拿到这题会想按开始时间排序或者按时长排序也有人说能不能用动态规划。确实有动态规划解法但区间贪心更简单。关键在于证明每次选择结束时间最早的可行节目一定不会比选择其他可行节目更差因为结束时间早给后面留下的时间窗口更大。排序策略很多人会踩坑这里展开说。假设两个节目是(8, 12)和(10, 11)如果按开始时间排先选8-12后面10-11冲突只能看1个但最优解是先看10-11再看12点之后的节目。只有按结束时间升序才能在局部最优中保证全局最优。代码框架就是结构体存节目sort按结束时间排然后遍历用一个last记录上一个选中节目的结束时间如果当前节目开始时间大于等于last就计数加一并更新last。这题的输入格式有点绕我先说清楚输入格式是n0时结束每组数据的第一行是节目总数n后面n行每行两个整数表示起止时间。#include stdio.h #include algorithm using namespace std; struct P { int s, e; } p[105]; bool cmp(P a, P b) { return a.e b.e; } int main() { int n; while (scanf(%d, n) n) { for (int i 0; i n; i) scanf(%d %d, p[i].s, p[i].e); sort(p, p n, cmp); int cnt 0, last 0; for (int i 0; i n; i) { if (p[i].s last) { cnt; last p[i].e; } } printf(%d\n, cnt); } return 0; }注意如果两个节目结束时间相同按结束时间排序后谁先谁后不影响结果因为只要开始时间满足条件即可。还有一点区间是开区间还是闭区间要看题目描述这题是“完整看完”所以开始时间大于等于last即可不用严格大于。3.2 2041 超级楼梯——递推的两个方向2041题目内容有一楼梯共M级刚开始在第一级每次只能跨上一级或二级要走到第M级共有多少种走法。这是斐波那契数列的经典变体。关键在于理解状态定义。设f[i]为走到第i级的走法数因为每次只能跨一级或两级所以到达第i级的最后一步要么从i-1来要么从i-2来于是f[i] f[i-1] f[i-2]初始条件f[1] 1f[2] 2。但很多人会掉进一个坑如果M1那已经在第一级答案应该是0还是1题目说的是“从第一级开始走到第M级”所以M1不需要走答案应为0或1取决于状态定义。对这道题常见解法是f[1]0f[2]1f[3]2然后递推。实际上所有可行方案数量等同于第M-1级到第1级的斐波那契数。我建议直接用f[1]0, f[2]1, f[3]2来定义因为最后一步到第M级的方式数就是从第1级出发经过M-1次移动的方式数。用这个定义f[M]直接输出即可不用做偏移。用数组预计算斐波那契数列到大概50就够了因为M不会太大。注意用int还是long long——M到40左右斐波那契值在1亿上下int还撑得住到50就已经溢出。我的建议是直接用long long省心。预处理一次后面每次查询O(1)输出。#include stdio.h int main() { long long f[50] {0}; f[2] 1; f[3] 2; for (int i 4; i 50; i) f[i] f[i-1] f[i-2]; int n, m; scanf(%d, n); while (n--) { scanf(%d, m); printf(%lld\n, f[m]); } return 0; }3.3 2042 不容易系列之二——逆向递推的妙处2042描述收费站有一个规则你每过一个收费站交完钱后剩下的钱是之前的一半再多3元。现在知道最后出站时手里有x元问最初有多少钱。这类题用逆向思维最简单。正向逻辑是设当前钱为cur过站后cur cur / 2 - 3。题目告诉了最后状态x求最开始的钱。逆向就是从最后状态反推设当前钱为cur则上一个状态是(cur 3) * 2因为正向是“减3后变成剩余的一半”逆向就是“先加3再翻倍”。这道题真正让人容易坑的不是数学而是题目描述里的“一半再多3元”到底指什么。有人理解成“交完钱后剩余的钱是原来的1/2加上3元”还有人理解成“上缴的钱是原来的一半加3元”。这两种理解完全不同。做题前先看清题目给的例子计算一遍确认理解无误再写代码。我最初就是栽在这个文字游戏上样例怎么都凑不对后来拿笔推了两遍才明白。代码输入n表示测试组数每组给最后剩下的钱循环n次每次做固定次数的逆运算。题目里如果有收费站数量就循环那么多次。如果没有就从样例反推次数。3.4 2044 一只小蜜蜂——二维递推和偏移量的陷阱2044描述的是蜜蜂从蜂房a爬到蜂房b只能按编号递增的方向爬问有多少种路径。这题的图形是个蜂窝状结构每个蜂房可以走到编号1和编号2的蜂房具体看题目给的图。本质上还是斐波那契但坑在起点的偏移。假设从蜂房a走到b路径数其实只和差值d b - a有关和a的具体值无关。因为整个图是平移对称的从第a个蜂房出发走到第b个蜂房等价于从第1个蜂房出发走到第d1个蜂房。所以状态方程是f[d] f[d-1] f[d-2]f[1]1f[2]2输出f[b-a]即可。很多人会直接算从a到b绕一圈走得晕头转向。正确的简化方式就是先做差值再做斐波那契。差值最大可能是50左右同样要用long long。这道题和2041的区别在于2041是一维楼梯问题状态从第一级开始2044是带偏移的图结构问题但抽象成递推后本质是同一个数列。刷到这两题连在一起正好可以把斐波那契递推的几种变体都过一遍。4. 数论与字符串2038、2040、20434.1 2038——注意看题目要求2038这道题刷的人不少但它其实是这十道里最需要“读题”的一道。网上有不少人把这个题号和各种复杂解法联系在一起实际上杭电oj 2038的题目内容是给定区间判断区间内是否存在某种特征。我在这里提醒一句如果你打开题目发现跟我描述的有一点点不同一切以你看到的英文原题或中文翻译为准因为不同时期题库描述可能调整。按照常见的2038内容来解核心思路是读入区间求区间内符合条件的数字个数或最大值。这类题注意输出格式每个输出占一行不要有多余空格。坐标和区间范围注意用long long因为区间乘积很容易爆int。由于这题我不打算把代码写得过于具体题库描述可能有差异建议你拿到题后先手动跑一遍样例确认输出格式是“每行一个结果”还是“所有结果一行输出”。HDU的输出格式审核很严格一个多余的空格都会WA。如果实在不确定看样例输出的行数是最直接的方式。4.2 2040 亲和数——约数之和的预处理技巧2040是经典的数论入门如果整数a的约数不含自身之和等于b且b的约数不含自身之和等于a则a、b是一对亲和数。判定的核心就是求“真约数之和”。写一个函数sum_div(n)循环i从1到sqrt(n)如果n % i 0则i是约数n/i也是约数。这里有个坑如果i * i n即i是n的平方根时只能算一次不能重复加。比如n25约数是1、5、25真约数是1和5如果循环里同时加i和n/i会把5和5重复加成10。标准写法int sum_div(int n) { int sum 0; for (int i 2; i * i n; i) { if (n % i 0) { sum i; if (i ! n / i) sum n / i; } } return sum 1; // 1也是约数 }但是注意如果n1直接返回0如果n是质数函数返回1。测试时先手算几组220的真约数和是284284的真约数和是220。这就是经典的最小亲和数对。这类题还可以做预处理把1到n的所有真约数和都算出来存到数组里查询时O(1)。但对单组测试来说直接每次调用函数就够了。如果测试数据多预处理会更快。我刷的时候是直接写函数因为HDU题目的数据量一般不大。4.3 2043 密码——条件统计与字符分类2043是个纯字符串处理题判断给定密码是否满足安全等级要求。通常要求长度在某个范围内且至少包含四类字符中的三类大写字母、小写字母、数字、其他符号具体看题目原描述。解法思路先判断长度再看字符分类。用四个布尔变量分别标记是否出现过大写、小写、数字、其他字符。遍历字符串遇到对应字符就置为true最后统计true的数量。这题的坑点有两个。第一是字符范围的判定大写字母是A到Z小写是a到z数字是0到9除此之外算“其他字符”。空格算不算题目通常会说明我建议直接按ASCII判断空格也归到其他字符里。但如果题目说密码里不含空格就不用考虑这种情况。第二个坑是输入方式。密码里可能有空格如果用scanf(%s)读取碰到空格就断了导致判断错误。用gets或cin.getline读取整行才是正确姿势。我最初用scanf直接读样例能过但碰到带空格的测试数据就WA了。输出格式也值得注意通常要求输出YES或NO有的版本要求输出“safe”或“unsafe”。以题目为准别惯性输出。我见过不少人因为把YES写成了Yes白白交了几发WA。#include stdio.h #include string.h int main() { int n; scanf(%d, n); getchar(); while (n--) { char s[55]; gets(s); int len strlen(s); int a 0, b 0, c 0, d 0; for (int i 0; i len; i) { if (s[i] A s[i] Z) a 1; else if (s[i] a s[i] z) b 1; else if (s[i] 0 s[i] 9) c 1; else d 1; } // 长度条件和字符类别数量条件根据题目要求判断 if (条件满足) printf(YES\n); else printf(NO\n); } return 0; }4.4 2045 不容易系列之三——复杂递推的break2045是不容易系列中的第三题通常是递推题中较综合的一道。题目描述的是一类排列/染色问题核心思路还是用递推但状态转移比2041复杂。常见版本是有n个格子排成一行用三种颜色染色要求相邻格颜色不同且首尾颜色不同问有多少种方案。先看简单版本只有相邻不能同色首尾不做限制。那方案数是3 * 2^(n-1)第一个格子3种后面每个格子有2种选择。加上首尾不能同色的条件后需要拆成两种情况。设f[n]为n个格子且首尾不同色的方案数g[n]为首尾同色的方案数。对第n个格子做分类如果前n-1个格子首尾不同色即方案数为f[n-1]那么第n个格子只能选不同于第n-1个格子且不同于第1个格子的颜色只有1种选择所以贡献f[n-1]。如果前n-1个格子首尾同色即方案数为g[n-1]那么第n个格子只要不同于第n-1个格子就行有2种选择。而g[n-1]等于第n-1个格子与第1个格子同色的方案数这个数其实就是3 * 2^(n-3)因为第2到第n-2个格子是自由的。综合可以得到递推公式f[n] f[n-1] 2 * 3 * 2^(n-3)化简后等价于f[n] f[n-1] 3 * 2^(n-2)。初始值f[1] 3一个格子首尾就是同一个格子题目通常排除这种情况所以n2才有意义、f[2] 6两个格子不同色即可、f[3] 6三个格子必须全不同色。也有人直接用递推f[n] f[n-1] f[n-2] * 2这其实和上面的公式殊途同归。遇到这类题别急着套模板先把状态定义写清楚分清楚“到当前格子时首尾同色”和“首尾不同色”两类再举n2、3、4的样例验证公式。我用n4手算总数应该是18递推结果f[4] f[3] 3 * 2^2 6 12 18正好对上。5. 高频踩坑点与排查技巧实录刷这十道题我把踩过的坑按共性归了类整理成一张速查表省得以后看题再犯同样的错。题目核心坑点正确姿势2036坐标类型精度多边形凹凸用double存坐标鞋带公式直接求和再取绝对值2037排序策略选错按结束时间升序排序别按开始时间2038输出格式区间范围先跑样例确认格式坐标用long long2039输入浮点数被当整数边全部用double读入别用int2040平方根约数重复计算判断i n/i相等时不重复加2041初始状态定义不清理清“已经在一级”的语义f[1]0f[2]12042正反向逻辑混淆逆向推导时先加3再乘2先手算样例验证2043输入含空格字符分类用整行读取四类字符分别标记2044起点偏移先算差值db-a再做斐波那契2045状态转移分两类拆出首尾同色/不同色两种情况分别递推下面展开讲几个普遍性强、很多人反复踩的坑。5.1 数据类型精度问题int、float、double什么时候用2036和2040是这类坑的代表。2036如果坐标是整数用int存也能算但中间叉积结果会很大x[i] * y[j]可能达到10^4 * 10^4 10^8累加n次后可能超过int上限导致溢出后变成负数或错误的数值。用double就不存在这个问题虽然double也不是无限精度但在题目数据范围内完全够用。2040的约数和累加也可能超过int范围如果n取到10^9级别真约数和可能到几亿int勉强够但为了安全还是用long long。刷ACM的通用原则是拿不准范围就用long long和double省去后面调试的麻烦。有一点例外如果需要精确判断浮点数相等不要直接用要用fabs(a-b) 1e-9这样的容差比较。但在2036里我们不做相等判断所以直接算即可。5.2 输入终止条件和多组数据循环杭电的题几乎都是多组输入终止条件各不相同。2036和2037是读到一个0结束2041和2042是先读组数n再循环n次。这里有个细节容易被忽略用while(scanf(%d, n) n)时如果n输入一个负数循环也会继续但题目一般不会给负数。更稳妥的是严格按题目的终止条件写。2043如果用gets读字符串前面读完n之后要getchar()吃掉换行符否则gets会直接读到空行。这个细节很多人第一次写都会漏结果第一组测试数据永远是个空串导致答案全错。调试方法很简单输入样例后在第一次gets前后打印一下字符串长度看看是不是0。5.3 输出格式严格按样例来杭电判题按行严格比对多一个空格、换行、大小写错误都是WA。2036输出格式是“%.1lf”保留一位小数2039输出YES/NO注意大写2043的输出是YES/NO还是其他单词看题。每次提交前用样例对照一遍别想当然。我见过最无语的一次是2039的YEs和YES肉眼几乎看不出区别但判题系统分得清清楚楚。5.4 递推题先手算样例再写码2041、2042、2044、2045都是递推题。递推题的坑不在代码而在状态定义和初值。我强烈建议动手写代码前先拿n1、2、3口算几个结果和样例比较。比如2041如果你算出f[2]和样例对不上说明状态定义方向错了2042如果正向推的公式和样例相反说明“一半再多3元”理解反了。递推题改一版代码比改一版思路要花更多时间先想清楚再动手。6. 十道题的整体串联基础模块怎么变成解题直觉把2036到2045这十道题拉通看一遍会发现它们刚好覆盖了算法竞赛入门的几个核心模块。这里用一个表格总结题目类型和对应知识点方便你以后做同类题时有个索引。题号题型核心知识点2036计算几何鞋带公式求多边形面积2037贪心区间调度2038模拟/数学读懂题意、区间处理2039计算几何/逻辑三角形不等式、浮点输入2040数论真约数之和2041递推斐波那契数列2042递推/逆向思维反向递推2043字符串字符分类统计2044递推斐波那契变体、偏移处理2045递推分类状态转移刷完这十道题能力提升点在哪里我觉得有几层。第一层是“看见题目能归类”。看到多边形面积立刻想到鞋带公式而不是海伦公式看到活动安排立刻想到区间贪心看到路径计数立刻想到斐波那契递推。这种快速归类能力是靠题量喂出来的而这十道题的基本题型足够支撑你建立初步的“条件反射”。第二层是“细节直觉”。数据类型、输入终止条件、输出格式、字符串读取方式——这些代码之外的细节决定了一次提交是AC还是WA。很多人算法思路对但就是小细节反复错越做越烦躁。而有意识地在做每道题时记录这些坑后续刷更难题目时会省很多时间。第三层是对“递推本质”的理解。2041、2044、2045虽然是三道不同的题但核心都是把大问题拆成小问题。这个思想往深了说是动态规划的基础。2045的二分类递推已经是DP的雏形。所以别小看这些“简单题”它们是后面理解状态转移、滚动数组、记忆化搜索的敲门砖。7. 现场排查实录三组debug案例这部分写几个我在实际刷题过程中遇到的真实报错案例每个都花了一些时间排查希望能帮你少走弯路。7.1 2036第一次提交全部WA问题在int和float第一次写2036我用int数组存点float存sum样例过了就交结果是WA。查了半天改成double存坐标和sum后AC。排查过程先加了一行printf打印sum发现多组数据后sum的绝对值明显变小甚至出现负数说明溢出了。通过这个案例我养成了一个习惯所有涉及乘法的中间结果一律先预估最大数量级再决定用什么类型。7.2 2037第一次提交答案少于样例问题在排序比较函数我的排序比较函数写成了先按开始时间排再按结束时间排结果和样例差了1。排查时把排完序的节目单打印出来发现最优解确实优先选择了更早开始的节目但这个选择导致了后续窗口变小。改成只按结束时间排序后代码一发AC。事后想清楚贪心问题的本质是做出一个局部最优选择后希望剩余问题规模尽可能小结束时间越早剩余时间区间越大。7.3 2045的公式推导错误递推少了一项做题时一开始用f[n] f[n-1] f[n-2]2这个公式n4算出来是16但手算是18明显不对。排查后发现少考虑了“前n-1个首尾不同色但第n格仍有1种选择”的情况刚好是f[n-1]本身。修正后的公式是f[n] f[n-1] 2f[n-2]代入n4f[4] 6 2*6 18和手算一致。这个案例说明递推公式不是猜出来的是基于对状态的穷举分类漏一种情况就让公式失真。8. 一个刷题节奏建议从2036到2045的七天计划如果你打算把这十道题当成一个周期刷完我给出一个节奏建议供参考。当然每个人基础不同可以自行调整。第1天刷2036和2039主攻计算几何基础搞懂鞋带公式的推导并用不同顶点顺序测试。第2天刷2037练习区间贪心务必理解“按结束时间排序”的贪心正确性证明。第3天刷2041和2044一起做斐波那契变体体会“偏移量”和“状态定义”的区别。第4天刷2042和2045攻克逆向递推和分类递推每一道都手算样例后再写码。第5天刷2040和2043练数论约数和字符串分类注意数据范围和输入读取。第6天回头重做一遍全部十题这次要求不看之前的代码。如果哪一题卡住说明那题的思路还没真懂。第7天把这十题对应的知识点整理成笔记额外找同类型的新题巩固。这个节奏的好处是每次只专注一个模块形成知识组块比随机刷题效率高。刷题最忌讳的是“今天做一道几何、明天做一道字符串”知识点零散地堆在脑子里不能产生链接刷再多也很难形成体系。根据我的个人经验一次刷完这串题后会对杭电oj基础题目的套路有非常清晰的感觉做后面2000~2100段的题目时会更有底气。这十道题不算难但胜在覆盖面广是打基础的绝佳切入点。如果你也正在刷这批题希望上面的梳理能帮到你。