第一次在CSP第一轮试卷里看到完善程序题时我心里是有点发怵的。前面单项选择还能靠背知识点蒙一蒙阅读程序可以硬着头皮跟着跑唯独完善程序这种“半成品代码”总让人脑子转不过弯来。后来带学生备考发现大家在这道题上的失分率普遍比想象中高很多选手能轻松做对后面的算法大题却在完善程序题上栽跟头。完善程序题说白了就是给你一段不完整的C代码挖掉几个空再给出几个选项让你选出正确的语句把程序补完整。它处在“读懂代码”和“写出代码”之间既考语法更考算法直觉。这篇文章就把我这些年做完善程序题的经验、给学生讲题时的总结、以及赛场上实际用到的判断方法完整讲一遍希望能帮正在备战CSP的你少走弯路。1. 完善程序题到底在考什么1.1 它是“读代码”和“写代码”之间的桥梁完善程序题在CSP第一轮里占的分量不轻一般有两道题分值加起来差不多能到总分的三成上下。和单项选择的零散知识点不同这种题是连续的、有逻辑的代码你需要像一个外科医生一样把缺掉的段落补回去。它不是单纯的背诵也不是纯粹的算法设计而是要同时具备三样东西看得懂程序结构、想得清算法流程、写得出正确语句。很多同学误以为完善程序题就是“靠感觉选”其实它考察的能力非常明确。第一是变量的生命周期每个变量从定义到消亡都经历了什么它的值在什么时候更新、什么时候被读取。第二是循环不变式一段循环代码维护的是什么条件循环结束后哪些变量变、哪些变量不变。第三是边界控制数组下标会不会越界循环是执行n次还是n-1次while的结束条件是否覆盖了所有情况。这三个能力恰恰也是复赛写代码时最容易出问题的地方。1.2 它和阅读程序题的本质区别阅读程序题是“给你一段完整代码问你输出是什么”本质上是一个模拟执行的过程你可以拿着样例硬着头皮从头走到尾。完善程序题则反过来代码并不完整你需要根据题目的算法描述推断出空位处本来应该写什么。这就像给你一篇被人挖掉关键词的议论文你要根据上下文和作者的中心思想把文章补回来。所以很多人在阅读程序题上拿高分在完善程序题上却翻车原因就在这里。阅读程序考的是“顺着代码走”完善程序考的是“理解代码为什么这么写”。前者是执行者视角后者是设计者视角。备考完善程序题需要刻意训练自己用“设计者视角”去读代码每读一行不要只问“这一行做什么”还要问“这一行不写行不行”“如果换一种写法行不行”“这个空如果填别的会不会影响后面什么”。1.3 从课内编程到竞赛代码的思维切换CSP用到的C代码和学校信息技术课里教的那种“小程序”差别很大。学校里的程序通常是顺序结构为主加上简单的for循环和if判断代码长度几十行。而CSP第一轮里出现的完善程序往往是贪心、分治、动态规划、图论这些经典算法的实现代码里充斥着递归、指针、位运算、排序比较函数等高级技巧。你如果没有见过这些算法的标准写法光靠语感去猜几乎不可能猜对。我的建议是在备考完善程序题之前先把竞赛中常见算法的“标准代码模板”过一遍。比如二分答案的模板、双指针滑动窗口的模板、DFS和BFS的遍历框架、并查集的find与merge、最短路的Dijkstra堆优化写法、DP的状态转移框架。不需要每个都背得滚瓜烂熟但至少要能在一堆代码里认出“哦这是二分”“哦这是深搜”。这个识别能力是解题速度的基石。我做真题的时候发现很多学生读题读得很慢不是因为读不懂中文而是因为看到代码里的一段结构根本不知道它在干什么需要从头模拟一遍才知道意思。如果你提前熟悉了常见算法模板读代码的速度会快很多也更知道空位大概应该在哪个位置出现。2. 破解完善程序题的三步通用流程2.1 先建“变量档案”再谈填空拿到完善程序题第一件事不是去看空而是把整段代码从头到尾读一遍把每个变量都登记下来。我管这个叫“变量档案”包括四个要素类型、作用、初值、变化时机。比如看到一个变量ans它的类型是int作用可能是记录最优答案初值是0或特别小的数变化时机一般在循环体内用max或min更新。有了这个档案空位处的正确选项往往自己就浮出水面了。为什么要先做这一步因为完善程序题里的空基本都是围绕变量之间的数值关系来设的。你不知道cnt是计数数组还是cnt用来记录左指针就不知道空里该减cnt[a[l]]还是cnt[l]。你想不清楚prev是“上一个元素的值”还是“上一个元素的下标”就会在更新语句上栽跟头。建立变量档案的过程就是在给整个程序画一张地图有了地图走迷宫才不会乱。举个例子如果程序里出现了一个数组vis[]我们一看就知道它大概率是“标记某个东西是否出现/被访问过”它的取值一般只有0和1更新方式通常是vis[x]1或者vis[x]。再比如变量tot、sum通常是累加器l、r常常是左右边界cur、now是当前值pre往往是上一位置或上一个值。竞赛代码里约定俗成的命名习惯非常明显你养成读变量的习惯之后很多空甚至不用看选项就能先猜出一个“预期答案”再去选项里对应。2.2 用一个样例把主流程跑通变量档案建好之后不要慌着去选答案。拿题目给的样例把程序从main函数开始手动模拟执行3到5步。这一步非常关键它的目的不是算出最终答案而是搞清楚两件事第一程序在“正常情况”下是怎么运转的第二哪个空位属于“核心逻辑”哪个空位属于“边界处理”。手动模拟的时候建议按下面的节奏每执行一行代码就更新一次关键变量的当前值。看到if分支就判断一下条件是否成立看到循环就记录当前循环到第几轮、循环变量是什么。你会发现大部分空位在你模拟的过程中会自然暴露出来要么是某个变量没有被更新要么是某个条件不知道依据什么判断要么是某个数组的下标不知从何而来。你把这些“卡住”的位置和原本的空位对照常常能一一对应。有一个我反复给学生强调的点手动模拟不要只模拟一半。很多学生看样例数据前几步没问题就急着去做下一题结果后面程序二分或者递归的部分完全没走到空选全靠蒙。至少要把一个完整样例从头跑到尾而且最好选一个“能区分边界”的数据来模拟。比如有n1的情况就要拿n1试一下如果区间二分就拿区间长度为1的情况试一下。这些极端情形是完善程序题最爱考的地方也是靠“感觉”过不去的坎。2.3 语义优先语法兜底最后排除法到了需要填某个空的时候我的判断顺序永远是先看语义再看语法最后用排除法兜底。语义判断指的是根据空前后的代码逻辑推测这个空位“应该做什么事情”。例如空位上一行刚刚更新了某个计数下一行却要判断“是否出现了重复”那么这个空位大概率就是在写“如何判断重复”的条件。写代码的人不会无缘无故插入一段上下文每一个空在代码里都有明确的“位置感”你要做的是站在作者的思路上说出这个位置的职责。语义判断选不出来时再检查语法。候选选项里可能存在类型不匹配、数组下标写成变量、函数返回值遗漏等问题这些语法错误可以快速排除。再不行就用排除法逐个选项代入源码看哪个能保证程序编译通过且逻辑自洽。但排除法一定要谨慎因为有的选项虽然语法正确、单独看也说得通组合起来却会让程序陷入死循环或数组越界。把选项代入之后最好用一个小样例在脑子里重新跑一遍确认它不影响整个程序的最终结果。这三步合在一起就是我的“完善程序题三步走”。第一步解决“程序在干嘛”的问题第二步解决“空位在干嘛”的问题第三步解决“该填什么”的问题。你按顺序执行正确率会明显上升。3. 两道经典题的逐空拆解3.1 双指针滑动窗口最长不重复子段这道题的算法描述通常是给定一个长度为n的整数序列a求出最长的连续子段长度要求子段内的所有数字都互不相同。n不超过100000a[i]不超过1000000。经典解法是双指针加计数数组。我在这里把代码框架写出来故意挖了几个空模拟CSP第一轮完善程序题的出题方式。你先别急着往下看答案试着自己在心里填一遍#include bits/stdc.h using namespace std; const int MAXV 1000000; int a[100005], cnt[MAXV 5]; int main() { int n; cin n; for (int i 0; i n; i) cin a[i]; int ans 0, l 0; for (int r 0; r n; r) { cnt[a[r]]; // (1) 为什么这里写 a[r]而不是 r? while (cnt[a[r]] 1) { // (2) 结束条件为什么是 1 cnt[a[l]]--; // (3) 为什么减的是 a[l] 而不是 l? l; // (4) 移动左指针的顺序能不能颠倒 } ans max(ans, r - l 1); // (5) 子段长度为什么是 r-l1? } cout ans endl; return 0; }这个程序的核心逻辑是右指针r不断向右扩展把新元素加入区间加入之后如果发现计数超过1说明出现了重复那么就需要移动左指针l把重复元素移出区间直到区间内所有数字计数不超过1。每次调整完当前区间[l, r]都是一个合法的不重复子段用它的长度更新答案。逐个看这几个空第(1)处使用a[r]作为下标是因为cnt数组是按“数值”计数的不是按“位置”计数的。如果写成cnt[r]含义就变成了统计下标r出现了几次完全错误。这里考察的是“数组下标到底代表什么”这个最基本也最容易忽略的问题。第(2)处的while (cnt[a[r]] 1)是判断加入当前元素后是否出现重复。注意这里是while而不是if因为左指针可能需要连续移动多次才能把重复元素完全清出去。比如区间里已经有两个5右指针又读到一个5那左指针要一直移动到跳过第一个5之后cnt[5]才会从3变成2再变成1这可能需要不止一次左移。如果写成if左指针只移动一次重复元素可能还没被移除程序就输出错误答案。第(3)处减掉的是cnt[a[l]]也就是左指针指向的那个数的计数。很多人会在这道题里选错把减法写成cnt[l]--这几乎是考场上最典型的错误。l是位置a[l]是位置上的值计数数组记录的是每个值的出现次数所以要减的当然是a[l]。这种错误和前面第(1)处的cnt[a[r]]是同一个坑出题人很喜欢在同一个空位换着花样考。第(4)处先说结论cnt[a[l]]--和l的顺序不能颠倒。如果先执行l那么a[l]已经是新位置的值了减掉的就不是原来左指针指向的那个数如果先减再自增减掉的才能对应当前左指针位置。类似这种“先处理再移动”的顺序问题在一次遍历型算法里特别常见遍历数组、遍历链表、遍历树的时候都会碰到。做题时如果看到两个操作共享同一个变量一定要想清楚哪个先哪个后。第(5)处区间[l, r]的长度在双闭区间写法下是r - l 1。如果你把区间定义成左闭右开[l, r)那长度才是r - l。题目程序里用的是哪种区间形式必须在读变量档案时确认好不然最后一个空很容易错。我的经验是看到for (int r 0; r n; r)通常左指针初始化为0区间是[l, r]长度用r - l 1看到for (int r 1; r n; r)就要重新判断坐标体系是1-based还是0-based千万别想当然。3.2 二分答案砍树问题第二道题我选二分答案因为CSP完善程序题非常喜欢考二分它也是最容易因为模板不熟而丢分的地方。这题描述是有n棵树第i棵树高度为h[i]要砍掉若干高度使得砍下来的总木头长度至少为m求允许的最大砍树高度H。超过H的部分被砍掉小于等于H的树不砍。标准代码框架如下#include bits/stdc.h using namespace std; int n, m, h[100005]; bool check(int x) { long long sum 0; for (int i 0; i n; i) { if (h[i] x) sum h[i] - x; // 只有高于x的树才会产生木头 } return sum m; } int main() { cin n m; int maxh 0; for (int i 0; i n; i) { cin h[i]; maxh max(maxh, h[i]); } int l 0, r maxh; while (l r) { int mid (l r 1) / 2; // (1) 为什么这里要1? if (check(mid)) l mid; // (2) 砍得动H还可以再高一点 else r mid - 1; // (3) 木头不够H必须降低 } cout l endl; // (4) 输出l还是r? return 0; }这道题的核心是H越高能砍的木头越少H越低能砍的木头越多。所以check(x)返回true时说明x这个高度能砍出足够多的木头那么答案至少是x可以继续尝试更高的高度返回false时说明x太高了砍不出那么多木头答案必须小于x。第(1)处是二分模板里最经典的细节mid (l r 1) / 2。为什么这里要加1因为当l 1 r且check(l)为真时执行l mid此时如果mid算出来等于l左边界就不动了程序会陷入死循环。加上1让mid取到区间中点偏右的位置保证区间规模一定会缩小。判断二分模板该用哪种取整方式有一个口诀如果更新方式是l mid就用(lr1)/2如果更新方式是r mid就可以用(lr)/2。不确定时就在纸上模拟l1, r2的情况看会不会死循环这是最保险的验证方法。第(2)和第(3)处本质上是同一种逻辑的两面check返回true说明当前高度可行答案可以往大方向找返回false说明当前高度不可行答案必须往小方向找。要注意的是随着check结果不同边界条件是l mid还是r mid - 1这取决于当前mid本身是否可能是答案。在“求最大值”的问题里mid可能正好是最终答案所以l直接变成mid而r不能直接变成mid只能变成mid-1因为mid已经确定不可行了。第(4)处循环退出时l r所以输出l或者r都一样。但如果你用的是另一种二分写法比如while (l r)配合单独记录答案变量ans那退出时l和r可能不相等就不能随便输出l或r了。这个一定要看清题目程序用的哪种模板再决定输出谁。我特意选这两道题是因为它们代表了完善程序题里最常出现的两大类型一类是“线性扫描类”用双指针、前缀和、计数数组维护区间信息另一类是“判定类”用二分答案把最优化问题转成可行性判断。你只要把这两类模板吃透CSP第一轮完善程序题的大半分数就已经拿下了。3.3 从案例中抽象出的通用提问每次拆完一道完善程序题我都会让学生用三个问题复盘这段程序在维护什么信息循环的退出条件是什么每个空放入选项后边界情况有没有被破坏这三个问题可以套用到任何一道完善程序题上也是从“会做某道题”到“会做所有题”的关键。下次你再遇到一道陌生的完善程序题先不要急着逐空去找答案先回答出这三个问题再决定怎么下手。4. 考场上的高频陷阱与排查清单4.1 数组下标是用数值还是用位置这是我在批改学生练习时见到最多的一类错误。计数数组、标记数组、桶排序、哈希统计这些算法里数组下标是“数值本身”而在普通数组访问里下标是“位置序号”。完善程序题经常故意在同一个空位给出多种下标写法来迷惑人。建议看到cnt、vis、hash这类名字第一反应先确认它是按值索引还是按位置索引再看选项。快速自查方法看它的初始化与更新。如果所有更新都形如cnt[某个值]它就是按值索引如果更新是cnt[某个下标] 某值它就是按位置索引。索引方式一旦确认很多下标类错误可以直接排除。4.2 边界条件差一小于、小于等于、减一差一错误在完善程序题里特别常见比如循环是i n还是i n答案是r - l还是r - l 1二分的mid - 1还是mid。这种错误很难靠“语感”判断必须用极端样例验证。看到一个循环或边界条件就拿n1、区间长度为1、元素全部相同、元素全部不同这种极端数据在脑子里跑一遍正确写法一定能跑过错误写法大概率会撞上越界或者死循环。我还记得有一个学生在一道区间和问题上选了r - l我让他拿n1的例子试一下他刚写到区间[0,0]的长度时自己就笑了。很多边界错误不是不会而是没有养成验证的习惯。每次填完一个空花五秒钟做一个极端样例的快速脑内验证这个投入产出比是非常高的。4.3 递归和循环的顺序先操作还是先递归DFS、二叉树遍历、回溯算法里递归调用和当前节点操作输出、记录、恢复现场的顺序是完善程序题的高频考点。前序遍历是先访问当前节点再递归左右子树中序遍历是先左再当前再右后序是先左右再当前。这本身不难但程序一旦加上“恢复现场”的代码就经常有人把回溯语句放在错误的位置。判断顺序的方法只有一个拿一个只有3个节点的小树或者小图手动模拟一遍看递归出口和回溯语句是否和预期一致。CSP真题里有一道经典的树遍历完善程序题把访问节点、递归左子树、递归右子树、回溯恢复四个动作打乱让考生选正确的顺序。这种题如果你不去画那棵只有3个节点的小树光在脑子里空想很容易被绕进去。4.4 各类题型的错误自查表我整理了一份自查表平时做题可以对照着排查。它不是标准答案但覆盖了完善程序题里八成以上的失分点。错误类型典型表现自查方法下标用错cnt[l]写成cnt[a[l]]或反过来先确认计数数组是按值索引还是按位置索引边界差一输出r-l而不是r-l1用n1的极端数据验证区间长度递归顺序错先递归后输出或恢复现场位置错了画一棵3节点的小树手动模拟二分死循环更新lmid却用了(lr)/2模拟l1, r2的情况检查是否死循环变量名混淆prev到底是数值还是下标建立变量档案确认每个变量的作用初值错误累加器没初始化或ans初值设错看变量第一次使用前是否有赋值4.5 考场上最实用的三个建议第一个建议是控制时间。CSP第一轮整体时间比较紧张我带学生的策略是单选和阅读程序尽量快在完善程序上留出足够的时间。一般两道完善程序题控制在20到25分钟内完成。如果一道题卡了超过10分钟就先跳过把会做的空先填了剩下没把握的空最后统一处理。第二个建议是善用试卷上的草稿区。变量档案表格、样例模拟过程都写在草稿纸上不要全靠脑子记。人脑在考场上根本记不住那么长的状态一个简单变量变化表能省下大量重复思考的时间。第三个建议是别空着。完善程序题一般是选择形式即使完全不会也先填一个看起来最合理的答案不要因为拿不准就空着不选。做完之后如果有时间再把拿不准的题重新代入样例验证一遍。这里也想顺带提一句复赛时最忌讳的三件事其实和初赛是相通的写完不测试、不关注边界、不分析复杂度。完善程序题的训练恰好能帮你提前改掉这些毛病。5. 备考完善程序题的正确训练方式5.1 用“真题变式”练手感很多学生的刷题方式是把历年CSP真题做一遍对完答案就丢到一边效果一般。我建议一个做法把做过的完善程序题拿出来不看选项直接把答案填上然后给这道题换一个相似的算法要求自己动手改一两个空变成“新题”。比如原题考的是双指针你就把题目改成求“最长恰好有k个不同数字的子段”看看哪几个空需要改。这个过程特别能锻炼对程序结构本质的理解。具体操作时可以先在草稿纸上把原题的代码抄下来然后故意挖掉几个关键语句给周围的同学或自己做一遍。如果你能准确地说出“为什么这个空必须填这一句”说明你是真正理解了这段代码如果你只是背住了答案换个空位就露馅了。这种变式训练不需要每天做很多一周两三道坚持一个月效果比盲目刷十套题都好。5.2 建立自己的“错因分类档案”我自己的刷题记录本分栏就是“算法类型、错因、正确思路”。错因不完全等于算法不会很多是“变量作用域没看清”“区间定义搞反”“递归边界漏考虑”。把这些高频错因记下来考前翻一遍比做十道新题还有用。因为人的错误是有惯性的同一个坑你第一次踩可能是因为不懂第二次踩就纯粹是因为没有系统总结。举个例子如果你发现自己三次错在“计算区间长度忘记加1”那考前最后一天只需要做一件事把所有涉及区间长度、数组区间、二分区间的题目集中看一遍把“1/-1”的逻辑彻底理清。这种针对性复习比泛泛地刷套题效率高得多。5.3 分数之外完善程序题是复赛的隐形训练最后还想说点“题外话”。完善程序题表面上只占第一轮二三十分但它真正训练的是你读别人代码、理解算法边界、检查逻辑漏洞的能力。复赛写代码时debug的很大一部分工作就是“找出代码里不合理的逻辑”这和做完善程序题的思路几乎一模一样。我带过两个水平差不多的学生一个热衷于刷完善程序题一个只刷复赛大题。到了复赛前者的代码调试速度明显更快因为他平时就在练习“从残缺的代码中找出正确的边界”。所以说不要只把完善程序题当成初赛的得分工具它本质上是一种算法阅读理解训练对长期竞赛能力提升非常有帮助。我现在带学生复习CSP时还是会把完善程序题放在“性价比最高”的位置。原因很简单它不像阅读程序那样需要大量机械模拟也不像复赛大题那样对代码能力要求极高它考的是你愿不愿意静下心来把一段代码读懂。而这份耐心也是编程这条路上最宝贵的品质之一。希望这篇文章里的变量档案法、三步解题流程、两道案例拆解和考场自查清单能帮你在下次拿到完善程序题时少一点慌张多一分笃定。如果你有自己独特的填空技巧也欢迎在评论区一起交流。