第一次在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時還是會把完善程序題放在“性價比最高”的位置。原因很簡單它不像閱讀程序那樣需要大量機械模擬也不像復賽大題那樣對代碼能力要求極高它考的是你愿不愿意靜下心來把一段代碼讀懂。而這份耐心也是編程這條路上最寶貴的品質之一。希望這篇文章里的變量檔案法、三步解題流程、兩道案例拆解和考場自查清單能幫你在下次拿到完善程序題時少一點慌張多一分篤定。如果你有自己獨特的填空技巧也歡迎在評論區一起交流。