杭电OJ2011-2025刷题复盘：十五道入门题避坑与基础能力拆解

我最近把杭电oj的2011到2025这十五道题重新过了一遍顺手把踩过的坑、总结的思路都整理了出来。这批题目属于典型的入门巩固区间难度不大但考察点很杂有浮点数精度处理、有递推思维、有数组下标陷阱、也有字符串边界问题。如果你是刚接触OJ的新手或者刷题刷到中间有点迷茫想找点确定性的题目找找手感这份记录应该对你有用。我会按题号顺序逐题拆解每道题给出核心思路和易错点最后再聊一些普适性的刷题方法论。1. 这十五道题到底在考察什么一张整体的能力图谱先说结论杭电oj 2011到2025这段区间不是让你挑战算法难度的而是在帮你夯实编程基础。十五道题里没有任何一道需要高级数据结构或复杂算法但它们把新手最容易忽略的细节问题全部暴露出来了。我把这十五道题按考察点重新分了类这样你一眼就知道每道题在练什么。题目区间考察重点典型题目2011-2013数学计算、递推逆推多项式求和、素数判定、蟠桃记2014-2015数组处理、连续区间的遍历评委打分、偶数求和2016-2018数组交换、统计、递推增长数据交换、字符串数字统计、母牛故事2019-2021有序插入、排序变体、贪心思想数列有序、绝对值排序、发工资2022-2023二维数组、行列统计、格式输出海选女主角、平均成绩2024-2025字符串标识符、字符查找与插入合法标识符、查找最大元素这个分类有什么用我刷完这批题之后最大的感受是它们并不是孤立的每几道题之间其实存在能力递进。比如2011到2013这组从直接的浮点数累加到数学判定再到逆向递推其实是在训练你“把数学公式翻译成循环结构”的能力。而2019到2021这组从有序插入到绝对值排序再到贪心纸币分配是在一层层加深你对排序和选择逻辑的理解。另一个值得注意的点是这十五道题基本覆盖了OJ最常见的三大坑浮点数格式输出、空格处理、多组输入的模式。这三件事会一直伴随你刷到后面几百题早一点在这批题目里吃透后面会轻松很多。我自己当年刷到2023求平均成绩的时候就被输出格式卡了半个多小时那时候才真正意识到OJ的机器判定是分毫不差的不是“差不多”就能过。所以我的建议是不要因为题目简单就直接跳过而是像体检一样把每道题可能隐藏的知识点抠出来。你能在这一批题目里写出“不乱用数组长度、不搞错浮点数精度、不忘记吸收换行符”的代码说明基础已经比大多数人扎实了。2. 逐题拆解上数学规律、递推思维和数组遍历的四个示范这类题目的解法往往不是唯一的我先讲我认为最适合新手理解的思路再补充一些优化细节。2.1 2011多项式求和交替符号和浮点精度是两道坎这道题要求计算多项式的部分和1 - 1/2 1/3 - 1/4 ... 一直加到第n项。核心在于两点一是符号交替二是使用浮点数而非整数运算。符号交替的常见写法有两种第一种是用pow(-1, i1)来切换符号第二种是维护一个单独的sign变量每轮取反。个人更推荐第二种因为pow函数本身有开销而且新手用pow处理浮点符号时容易出现类型不匹配的告警。我实际测试下来用sign变量每次乘-1代码简洁且不会出错。浮点数精度这个点更关键。很多新手写多项式求和的代码时会这样写sum 1 / i; // i是int这行代码在C/C里是整数除法结果恒为0。正确的做法是把1写成1.0或者先声明i为double类型。这道题输出的结果要求保留两位小数所以使用printf(%.2f, sum)最直接如果使用C的cout则需要配合iomanip里的fixed和setprecision(2)。我还想提醒一个细节输入格式。这道题题目里给的是先输入m表示有几组数据然后每组输入一个n。我见过不少人在这一步就把数据读串了建议每组数据处理完就立即输出不要攒着最后统一输出这样可以避免数组或容器管理出错。2.2 2012素数判定sqrt边界比暴力枚举更重要2012题给了一个表达式n^2 n 41要求判断当x在某个区间[a, b]内取值时这个表达式的结果是否始终为素数。题目本身不难但有两个关键点。第一个是区间可能包含负数和0。很多人看到“素数”两个字下意识默认x是正整数但题目并没有这么限制。当x取负值时n^2 n 41可能仍然为正这时需要正常判断而当结果等于1时不是素数等于0时也不是素数。条件判断时最好显式处理这些边界值不要默认“表达式一定大于0”。第二个是判断素数的方法。最稳妥的做法是循环到sqrt(n)不要到n/2更不要到n。我之前对比过效率虽然这道题的数据量小暴力到n也能过但刷题不是只求过养成这个习惯后面遇到大规模数据时就能受益。核心代码思路如下bool isPrime(int num) { if (num 2) return false; for (int i 2; i * i num; i) { if (num % i 0) return false; } return true; }判断区间内是否全部为素数逐个判断即可一旦发现不是素数就立刻结束并输出NO。这道题的价值在于它让你熟悉“范围判定”这种常见模式后面很多题目都会套用类似结构。2.3 2013蟠桃记递推公式的逆向推导要画图蟠桃记的题目描述通常是这样第一天猴子摘了一堆桃子当即吃了一半还不过瘾又多吃了一个以后每天都是这样先吃当天剩下的一半再加一个到第n天早上想再吃时发现只剩下一个桃子了。问第一天一共摘了多少个。这道题最忌讳的是顺着题意正向硬推因为每天的数量变化是“吃掉一半加一个”正向推你无法确定初始值。正确思路是从第n天倒推。第n天剩下1个那第n-1天剩下的数量就是(1 1) * 2 4第n-2天就是(4 1) * 2 10。规律是前一天的桃子数等于后一天的桃子数 1乘以2。写成循环就是int ans 1; for (int i 1; i n; i) { ans (ans 1) * 2; }注意循环次数是n-1次而不是n次我第一次就写成了n次结果答案多算了一轮白白WA了一次。这种“逆推减一次循环”的题型本质上是递推的逆向使用。你可以把每天的桃子数列成一个表1、4、10、22、46……会发现就是乘2加2的规律再反转理解了这个过程比硬背代码有用得多。2.4 2014青年歌手大奖赛评委会打分排序后掐头去尾这道题要求去掉一个最高分和一个最低分然后求剩余分数的平均值。常规做法是读入所有分数排序然后从第二个加到倒数第二个再除以n-2。但这里有个容易被忽略的坑最高分和最低分可能不止一个。比如分数是9.9、9.9、9.8、9.7、9.6去掉一个最高分9.9后剩下的数组里还有一个9.9它仍然参与平均。排序后掐头去尾这种解法天然地只去掉一个最高和一个最低完美契合题意。另外要注意输出格式题目一般要求保留两位小数。直接printf(%.2f, sum / (n - 2))即可。有人会纠结sum是否要用double答案是要因为平均分要求浮点精度。分数本身虽然可能是整数但平均值是浮点数。这道题虽然简单但它把“排序辅助解决统计问题”的思路演示得很清楚后面很多涉及最大最小值的题目都会用到这个套路。3. 逐题拆解下排序变体、二维数组和字符串边界的进阶陷阱如果你把2015到2025这几道题的代码都写一遍会发现它们开始出现“条件组合”的复杂逻辑而不再是一层循环能解决的。3.1 2015偶数求和分段统计的边界要写成统一公式这道题的要求是把一段连续的偶数序列按每m个一组求平均值如果最后一组不足m个则按实际数量求平均。打个比方从2开始数2、4、6、8、10、12、14这些偶数如果每3个一组那第1组是2、4、6的平均值4第2组是8、10、12的平均值10最后一组是14平均值14。新手最容易犯的错误是在循环内部用if去判断“是不是每组最后一个元素”然后零散地处理边界。这种做法不仅容易漏而且逻辑复杂。更好的思路是分层处理先完整地按m个一组算剩下的单独算一个尾巴。一种简洁的写法是int k n / m; // 完整组的数量 for (int i 0; i k; i) { int start 2 i * m * 2; // 这一组第一个偶数值 int sum m * (start start (m-1)*2) / 2; // 等差数列求和 printf(%d, sum / m); } // 处理剩余不足m个的等差数列求和公式在这里非常实用省掉了内层循环效率更高。我实测了一下用求和公式比逐项累加至少快一倍而且代码更短。这个思路在后续很多分块统计的题目里都可以复用。3.2 2016数据的交换输出找的是最小值的下标而不是值这道题让你在一组数里找出最小值把它和第一个数交换位置然后输出整组数。听起来很简单但我见过大量WA发生在同一个地方很多人只记住了最小值是多少没记住最小值在第几个位置。正确的逻辑是先遍历数组找到最小值的索引minIndex然后交换a[0]和a[minIndex]。注意数值可能重复如果有多个最小值题目要求的是第一处出现的最小值所以你更新最小值的条件应该是“严格小于”而不是“小于等于”。这个细节我在答疑的时候几乎每次都要强调。还有一个隐藏的小问题如果最小值本来就是第一个元素交换操作也不能出错。用标准swap函数或者临时变量交换都没问题但不要因为下标相同就省略交换避免后面的输出逻辑出现分支。3.3 2017字符串统计getchar和缓冲区是新手最大的敌人这道题要求统计一个字符串中数字字符0-9出现的个数。看起来简单但输入环节可能会出现经典陷阱。如果上一道题目读入的是整数回车后缓冲区里残留了一个换行符直接getchar()会把这个换行符当成一个字符串读进去导致统计结果错误。所以这里我建议统一使用cin或者scanf处理输入顺序或者每读完一个整数后用getchar()把这个换行符“吃掉”。当然后续如果用gets或者getline则无需担心换行问题。以下是标准做法int t; cin t; cin.ignore(); // 吃掉换行 while (t--) { string s; getline(cin, s); // 统计数字 }统计时直接遍历字符串用字符判断s[i] 0 s[i] 9即可不需要转换成整数。这里有一个值得养成的习惯碰到字符判断始终使用字符字面量比较而不是记住ASCII码数值。3.4 2018母牛的故事多写几个测试用例就能发现递推规律母牛的故事是一道递推题一头母牛每年年初生一头小母牛每头小母牛从第四年开始每年也生一头小母牛。问第n年的时候总共有多少头牛。这道题的已知解法是f(n) f(n-1) f(n-3)具体推导过程是这样第n年的牛等于去年的牛它们都还在加上新出生的小牛。新出生的小牛数量等于三年前的牛总量因为三年前的牛到了今年刚好全部具备生育能力。这个递推式的推导比单纯记住公式要重要得多。我建议新手先手工列一个表第1年1头第2年2头第3年3头第4年4头第5年6头第6年9头…… 当你列到第6年时就能看出来规律是a[n] a[n-1] a[n-3]。如果直接看代码你可能永远也理解不了为什么要减3。实现时注意题目可能有多组输入直到读到0为止。所以要用while (cin n n ! 0)的结构并且在读入前先把前若干项递推结果算好或者边输入边算。这道题在杭电oj里算是递归/递推的入门必做题理解了它后续很多更复杂的递推题就有了参照物。3.5 2019数列有序插入排序的最小实现题目要求把一个新的整数插入到一个已经有序的数列中插入后仍然保持有序并输出新数列。最简单的方法是把新数加到数组末尾然后从后往前相邻比较并交换直到它落到正确的位置——这就是插入排序的一趟操作。int a[105]; int n, m; while (cin n m (n || m)) { for (int i 0; i n; i) cin a[i]; int pos n; a[pos] m; while (pos 0 a[pos] a[pos-1]) { swap(a[pos], a[pos-1]); pos--; } // 输出 }这道题对没有系统学过排序算法的新手来说是一个很好的“发现式学习”机会。你不一定需要提前背插入排序模板只需要想清楚“如果我在排队时突然来一个插队的人队列里的人怎么挪位置”就能写出来。3.6 2020绝对值排序比较器的灵魂是绝对值而非原值绝对值排序要求按整数的绝对值从大到小排序如果绝对值相同那么保持原数的相对顺序严格来说这道题只要求按绝对值排绝对值相等的顺序不影响判定。核心点在于你不能直接把所有数取绝对值之后再排因为输出时还要保留原始值包括负号。用C的话可以自定义sort的比较函数bool cmp(int a, int b) { return abs(a) abs(b); }如果用的是C语言qsort或者手写冒泡都行。手写冒泡时比较条件同样要套abs()。这里有个常见错误是在排序前把数组元素替换成绝对值了导致最后输出的全是正数。要时刻区分“比较的依据”和“存储的值”。手写排序还有一个细节本题n的范围通常不大冒泡排序复杂度足够但如果你写成sort记得在C里包含algorithm头文件并且用全局函数或lambda表达式写比较器。3.7 2021发工资贪心思想的初体验这道题是经典的找零钱问题变种老师有n个月的工资需要发放每个月的工资都是一个整数值求至少需要准备多少张人民币面额分别是100、50、10、5、2、1元。解题思路简单直接对每个工资数从大到小依次用面额去除并取余。int count(int salary) { int denominations[] {100, 50, 10, 5, 2, 1}; int cnt 0; for (int denom : denominations) { cnt salary / denom; salary % denom; } return cnt; }这道题的价值在于它引入了贪心思想的雏形。为什么从面额大的开始分因为面额大的纸币数量越少总张数就越少。在这个固定面额体系下贪心策略是最优的不会出现需要退回去调整的情况。你可以尝试把面额改成3元试试贪心就不是最优了这样对比着理解会更深刻。另外注意题目是n个月所以要累加每个人工资的张数而不是只看单个工资。多组输入时记得每轮重置计数器。3.8 2022海选女主角二维数组max初值的选取是个坑这道题是给一个m行n列的矩阵要求找出绝对值最大的元素并输出它的下标和值下标从1开始。核心思路很简单遍历所有元素维护当前绝对值最大值和对应位置。最容易翻车的就是maxNum的初始值。有人设成0结果矩阵里所有元素的绝对值都大于0反而没错但如果设成某个固定值比如999恰好矩阵里所有数的绝对值都小于它第一次更新就不会触发。更稳妥的做法是用一个flag标记是否第一次遇到或者直接把maxNum设为第一个元素的值再遍历剩下的。代码如下int maxVal a[0][0], maxI 1, maxJ 1; for (int i 0; i m; i) { for (int j 0; j n; j) { if (abs(a[i][j]) abs(maxVal)) { maxVal a[i][j]; maxI i 1; maxJ j 1; } } }注意输出顺序是行号、列号、元素值三者用空格分隔。这道题的m和n可能是一个范围比较大的值建议数组开成全局或动态大小的vector避免局部大数组导致栈溢出。3.9 2023求平均成绩格式输出是决胜点2023这道题我愿称之为“入门阶段最好的细心程度试金石”。题目要求输入m个学生n门课的成绩输出每门课的平均分、每个学生的平均分以及各科成绩都大于平均分的学生人数。逻辑本身不复杂但输出格式非常讲究所有浮点数都要保留两位小数行列对齐。实现上需要两种遍历按列求各科平均分按行求学生平均分。如果先按行读入成绩可以同时累加行和列的总和最后再求平均值。然后第三个统计是对每个学生逐门课和该科平均分比较如果都大于则计数。我把核心结构列出来double score[55][10]; // m个学生n门课 double rowAvg[55], colAvg[10]; // 先按行读入同时累加行总和、列总和 // 读完后分别除以n、m得到平均分 // 按要求输出输出时注意每门课平均分之间用空格分隔但行尾不能有多余空格。这是PEPresentation Error的重灾区很多人辛辛苦苦把答案算对了就栽在最后多了一个空格上。个人经验是先对非末尾元素输出“值空格”最后一个单独输出换行。3.10 2024 C语言合法标识符字符分类判断要用完整规则这道题要你判断字符串是否符合C语言标识符的命名规则第一个字符必须是字母或下划线后续字符必须是字母、数字或下划线。看起来不难但有几个陷阱。第一输入的多组字符串可能包含空格不能使用cin s因为cin读到空格就停了。正确做法是用getline但要注意前面读入整数时残留的换行符所以读完整数后要调用一次getchar或cin.ignore()。第二判断条件要覆盖所有情况首字符如果是数字直接不合法后续字符出现了空格、标点、运算符都不合法。空字符串算不算合法按C语言标准空字符串不是合法标识符但实际题目case中极少出现稳妥起见可以单独处理。第三这里说的“字母”通常指大小写共52个字符。如果你用ASCII码区间判断要写四个区间a-z、A-Z、_、0-9。用库函数isalpha和isdigit会更简洁但注意isalpha不会把下划线判为字母所以下划线要单独判断。3.11 2025查找最大元素注意字符串里可能有多个最大值这道题的要求是在字符串中的每个最大元素后插入“(max)”字符串后输出。比如说字符串“ABA”最大元素是B那输出就是“A(max)BA(max)”。这里有个关键细节最大元素可能出现多次每次出现后面都要加(max)。我的做法是先遍历一遍字符串找出最大字符maxCh然后再遍历一遍拼接结果如果当前字符等于maxCh就输出该字符再加(max)否则直接输出。注意不要直接在原字符串上插入因为插入操作会改变后续字符的位置关系容易引入bug。char maxCh 0; for (char c : str) if (c maxCh) maxCh c; for (char c : str) { cout c; if (c maxCh) cout (max); } cout endl;题目输入同样是多组字符串如果字符串里可能包含空格也要用getline读取并处理好前面的换行符。4. 刷题过程中最常踩的几个坑从WA到AC的排查思路这十五道题如果你全部自己写一遍并成功提交大概会经历几次WA甚至PE。我把自己刷题时遇到的几类问题以及对应的排查方法整理出来这可能比题目本身的解法更有价值。4.1 PE格式错误永远不要小看空格和换行我在2023求平均成绩这道题上被卡了三次PE原因是行尾多打了一个空格。OI/ACM的判定机通常会把格式错误单独标记出来意思是你答案的内容是对的但输出的空白字符位置不对。如何避免我的习惯是不要在循环内直接输出“元素空格”而是先用一个数组或字符串把结果拼接好最后统一输出或者判断一下是不是当前行的最后一个元素。通用模板for (int i 0; i n; i) { if (i 0) cout ; cout val[i]; }这样第一个元素前不加空格元素之间正好一个空格行尾自然没有多余空格。4.2 WA答案错误但本地测试没问题多半是数据类型或边界问题本地测试和OJ结果不一致最可能的原因是数据范围超过了你预设的类型。比如有些题目里的数值会很大用int存储可能溢出得用long long。2021发工资这道题虽然工资值本身不大用不到long long但有些题面扩展后就会用到建议从一开始就养成习惯不确定就用long long。另一个原因是多组输入的初始化。很多人会在循环外定义变量但循环内没有重置导致上一轮的残留数据影响下一轮。特别是求和变量sum、计数变量cnt每轮都要清零。还有一个隐蔽的边界循环条件写成while (cin n)没问题但如果题目要求读到0结束你还在继续处理0就会多算一组。2018母牛的故事明确说明了输入0结束很多人会忘记在循环里加if (n 0) break。4.3 缓冲区问题cin和scanf混用时要特别小心我做2017字符串统计时吃过一次亏当时用的是while循环里先读整数t再在每轮里用gets读字符串结果gets直接读到了换行符。解决办法我已经在前面提到了但这里想强调一个理念尽量统一使用一种输入流。要么全程用cin/cout要么全程用scanf/printf。如果你必须混用记得在读字符串前把缓冲区的换行符清掉。还有一种推荐做法是用getchar()配合getchar()逐个字符读能完全掌控输入过程但对新手来说容易写错。更简单的方案是用string加getline配合cin.ignore()这个组合对大多数入门字符串题都够用了。4.4 用“打印中间结果”代替“脑子想象”当你的代码逻辑复杂到没办法一眼看出问题时不要干瞪眼。把循环里的关键变量打印出来看看每一轮变化是否符合预期。我调试2025插入(max)时就是在原字符串内部插入导致死循环打印了idx之后才发现下标越界。这种调试方法虽然原始但对于入门阶段学习循环、数组、字符串的题目来说非常高效。4.5 第一次没过不要立刻改代码先读三遍题目描述我在刷2020绝对值排序的时候最初以为输出按绝对值从小到大结果题目要求从大到小白改一次。后来我养成了一个习惯WA之后先不碰代码回去把题目文字通读一遍特别是“输出要求”这一段。很多时候WA不是你逻辑错了而是你和出题人对“排序方向”“比较方式”“输出格式”的理解不一致。5. 这批题刷完之后的总结方法如何让每道题留下经验刷题不等于做题。同样是用一个小时有人刷完了十五道题脑子里只留下了“都过了”的印象有人从每道题里提取出一个可复用的模式遇到新题时能快速匹配旧经验。我自己的方法比较简单每次AC之后会问自己三个问题第一这道题考了哪个知识点答案可能是浮点数精度、排序、递推、字符串操作等。如果是自己不太熟悉的知识点我会额外找两三道同类题目加强练习。第二这道题哪里最容易出错把易错点记到笔记里哪怕只有一句话。比如“2013递推循环次数是n-1”“2022max初始值取数组第一个元素”。这些话在关键时刻比教科书有用得多。第三这道题能不能用不同方法再做一遍特别是2020绝对值排序手写冒泡和sort自定义比较器是两种完全不同的思路2018母牛的故事可以用递归、递推数组、甚至模拟三种方式解决。每种实现都能帮你加深对同一个逻辑的不同侧面的理解。如果你愿意还可以把这十五道题当成一个“基础能力自测清单”——不看任何题解限时独立完成如果某个题型卡壳超过二十分钟说明对应知识点还没有完全内化值得回头补一下。刷OJ不是为了刷数量而是为了把每道题都变成你能力的一部分。这个区间刷透之后再往后的题目会轻松不少。