1. 項目概述一次高強度算法集訓的復盤與沉淀又一年寒假集訓結(jié)束了。作為LSNU某高校ACM集訓隊的帶隊老隊員每年這個時候看著學弟學妹們從對復雜算法的一知半解到能獨立拆解、分析并解決一系列精心設計的題目這個過程本身就充滿了成就感。但集訓的價值遠不止于那幾周高強度的刷題和講題。真正的“財富”是集訓結(jié)束后每個人對知識點的梳理、對解題思路的復盤以及將零散經(jīng)驗系統(tǒng)化、結(jié)構(gòu)化的能力。這份“LSNU寒假集訓題解”正是這種沉淀的產(chǎn)物。它不是一份簡單的答案集合而是一份融合了題目分析、核心思路、代碼實現(xiàn)細節(jié)以及我個人踩坑經(jīng)驗的實戰(zhàn)筆記。這份題解主要面向的是有一定C/Java/Python基礎正在系統(tǒng)學習數(shù)據(jù)結(jié)構(gòu)與算法并準備參加藍橋杯、ICPC/CCPC區(qū)域賽、乃至力扣周賽的同學們。它解決的問題很直接當你面對一道新題時如何快速定位其考察點如何將學過的算法模型與實際問題建立連接如何在代碼實現(xiàn)中避開那些教科書上不會寫的“坑”通過拆解這次集訓中的典型題目我希望不僅能提供“怎么做”的路徑更能講清楚“為什么這么做”以及“還能怎么做”的思考過程。接下來我會選取幾個最具代表性的題目類別進行深度剖析。2. 核心題型與解題方法論框架寒假集訓的題目覆蓋了動態(tài)規(guī)劃、圖論、搜索、數(shù)據(jù)結(jié)構(gòu)等主要板塊。盲目刷題效率低下建立清晰的解題框架才是關鍵。我的方法論可以概括為“四步拆題法”審題建模 - 算法匹配 - 細節(jié)實現(xiàn) - 邊界驗證。2.1 審題建模將現(xiàn)實問題抽象為數(shù)學模型這是最關鍵的一步直接決定了后續(xù)所有工作的方向。很多同學卡殼不是因為算法不會而是沒讀懂題或者抽象錯了模型。以一道經(jīng)典的“數(shù)字替換”問題為例靈感來源于洛谷相關題目。題目描述可能很長但核心通常是給定一個初始數(shù)字A和目標數(shù)字B以及若干種操作如乘以2、加1、反轉(zhuǎn)數(shù)字等求從A到B的最少操作步數(shù)。審題要點狀態(tài)定義立即意識到這是一個“狀態(tài)轉(zhuǎn)移”問題。當前“數(shù)字”本身就是一個狀態(tài)。狀態(tài)空間數(shù)字的范圍是多少這決定了狀態(tài)數(shù)量是否可接受。如果B很大可能需要考慮剪枝或更優(yōu)的數(shù)學模型。操作定義每種操作都是從一個狀態(tài)到另一個狀態(tài)的邊且通常邊權為1一次操作一步。這立刻指向了**BFS廣度優(yōu)先搜索**求最短路徑的模型。去重與剪枝在BFS過程中一個數(shù)字可能通過不同路徑被多次訪問到。必須使用一個visited集合來記錄已訪問狀態(tài)避免重復入隊和死循環(huán)。這是此類題目最易忽略的細節(jié)。注意建模時一定要警惕“想當然”。比如“反轉(zhuǎn)數(shù)字”操作要明確前導零的處理例如從1230反轉(zhuǎn)得到0321通常應視為321。這個細節(jié)必須在審題階段就與出題人意圖或樣例確認清楚否則會浪費大量調(diào)試時間。2.2 算法匹配從問題特征到標準算法抽象出模型后就要與已知的算法工具箱進行匹配。這需要你對常見算法的適用場景非常熟悉。求最短步數(shù)/最小代價 狀態(tài)轉(zhuǎn)移-BFS無權圖或Dijkstra/SPFA帶權圖。上文的數(shù)字替換就是典型BFS。問題具有最優(yōu)子結(jié)構(gòu)即大問題的最優(yōu)解包含小問題的最優(yōu)解且無后效性-動態(tài)規(guī)劃DP。例如背包問題、最長公共子序列等。涉及連通性、最短路徑、最小生成樹-圖論算法并查集、Dijkstra、Floyd、Kruskal等。需要枚舉所有可能情況但狀態(tài)空間不大-DFS深度優(yōu)先搜索或狀態(tài)壓縮枚舉。需要頻繁查詢區(qū)間特性如最值、和、GCD或維護有序集合-數(shù)據(jù)結(jié)構(gòu)線段樹、樹狀數(shù)組、平衡樹等。以一道動態(tài)規(guī)劃題為例 “最大子數(shù)組和”的變種——環(huán)形子數(shù)組的最大和。這是力扣和藍橋杯的?？汀藴誓Ｐ推ヅ涫紫认氲浇?jīng)典的非環(huán)形“最大子數(shù)組和”Kadane算法DP狀態(tài)為dp[i]表示以i結(jié)尾的最大和。環(huán)形特性轉(zhuǎn)化環(huán)形意味著子數(shù)組可以跨越數(shù)組頭尾。直接套用Kadane算法行不通。這里需要一點逆向思維環(huán)形數(shù)組的最大和只有兩種可能情況一這個最大和子數(shù)組沒有跨越頭尾那就是普通的最大子數(shù)組和。情況二這個最大和子數(shù)組跨越了頭尾。那么剩下的中間部分即不包含在最大和子數(shù)組里的部分必然是一個連續(xù)的子數(shù)組并且其和是最小的。算法調(diào)整因此我們可以分別計算max_normal: 原數(shù)組的“最大子數(shù)組和”。min_normal: 原數(shù)組的“最小子數(shù)組和”。同樣用Kadane算法思想求最小值。total: 數(shù)組所有元素的總和。那么跨越頭尾的最大和就是total - min_normal。最終答案就是max(max_normal, total - min_normal)。邊界處理這里有一個巨坑如果數(shù)組全是負數(shù)那么total - min_normal會等于0因為min_normal就是total即所有負數(shù)之和。但此時最大和應該是那個最大的負數(shù)本身而不是0。所以需要特判當max_normal 0時直接返回max_normal。這個例子完美展示了如何將陌生問題環(huán)形通過分析和轉(zhuǎn)化拆解為已知的標準模型非環(huán)形最大/最小子數(shù)組和的組合。3. 數(shù)據(jù)結(jié)構(gòu)在解題中的巧妙應用很多題目考察的不是單一算法而是數(shù)據(jù)結(jié)構(gòu)的靈活運用。熟練掌握幾種關鍵數(shù)據(jù)結(jié)構(gòu)能讓你在解題時如虎添翼。3.1 單調(diào)棧解決“下一個更大元素”類問題這是集訓中高頻出現(xiàn)的考點。單調(diào)棧維護一個棧內(nèi)元素單調(diào)遞增或遞減的序列常用于在O(n)時間復雜度內(nèi)解決一類特定問題。經(jīng)典問題給定一個數(shù)組為每個元素尋找其右邊第一個比它大的元素Next Greater Element。暴力解法是O(n2)對于1e5的數(shù)據(jù)量必然超時。單調(diào)棧解法思路準備一個空棧用于存放數(shù)組元素的索引存索引更方便獲取結(jié)果。從右向左遍歷數(shù)組從左向右也可以但思考邏輯略有不同。對于當前元素nums[i]如果棧非空且nums[棧頂索引] nums[i]則不斷彈出棧頂。因為當前nums[i]比這些棧頂元素大對于更左邊的元素來說nums[i]才可能是“下一個更大元素”這些被彈出的元素已經(jīng)不可能了。此時如果棧為空說明右邊沒有比nums[i]大的元素結(jié)果記為-1或特定值。如果棧非空那么nums[棧頂索引]就是右邊第一個比nums[i]大的元素記錄結(jié)果。最后將當前索引i壓入棧中。C代碼示例vectorint nextGreaterElement(vectorint nums) { int n nums.size(); vectorint res(n, -1); // 初始化結(jié)果數(shù)組為-1 stackint stk; // 棧里存的是索引 for (int i n - 1; i 0; --i) { // 維護一個從棧底到棧頂單調(diào)遞減的棧棧頂最小 while (!stk.empty() nums[stk.top()] nums[i]) { stk.pop(); } res[i] stk.empty() ? -1 : nums[stk.top()]; stk.push(i); } return res; }實操心得單調(diào)棧的難點在于想清楚維護的單調(diào)性是遞增還是遞減以及遍歷的方向。我的記憶口訣是“找右邊更大從右向左掃維護遞減棧棧頂小彈出那些比我小或等的剩下的棧頂就是答案”。多畫圖模擬過程是理解單調(diào)棧最好的方式。3.2 并查集處理動態(tài)連通性問題并查集用于高效管理一些不相交集合的合并與查詢問題在圖論中判斷連通性、求連通分量以及一些具有傳遞關系的問題中應用廣泛。經(jīng)典問題社交網(wǎng)絡中的朋友關系。給定N個人和M條“朋友”關系雙向隨后有Q個查詢每個查詢問兩個人是否是朋友直接或間接。并查集核心操作初始化每個人都是自己的父親即parent[i] i。查找找到某個元素所在集合的“根”代表。通常使用路徑壓縮優(yōu)化讓查找路徑上的所有節(jié)點都直接指向根。合并將兩個元素所在的集合合并。通常使用按秩合并優(yōu)化將深度小的樹接到深度大的樹下。帶路徑壓縮和按秩合并的并查集模板class UnionFind { public: vectorint parent, rank; UnionFind(int n) : parent(n), rank(n, 0) { for (int i 0; i n; i) parent[i] i; } int find(int x) { // 路徑壓縮 if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } } bool connected(int x, int y) { return find(x) find(y); } };在解題中的應用并查集不僅用于靜態(tài)合并。有一類“離線查詢”或“逆向處理”的問題非常巧妙。例如題目給出一個圖然后依次刪除某些邊再詢問連通性。正向處理很困難因為刪除邊不利于并查集。此時可以逆向思考把操作序列倒過來就變成了從最終狀態(tài)開始逐步添加邊并維護連通性。這樣并查集就能完美勝任。這種“逆向思維并查集”的組合是解決一類難題的利器。4. 動態(tài)規(guī)劃專題從線性DP到狀態(tài)壓縮動態(tài)規(guī)劃是集訓的重中之重也是區(qū)分度最高的部分。其核心在于定義狀態(tài)和狀態(tài)轉(zhuǎn)移方程。4.1 線性DP經(jīng)典模型與變形最長遞增子序列是入門必學。定義dp[i]為以第i個元素結(jié)尾的LIS長度。轉(zhuǎn)移方程dp[i] max(dp[j]) 1其中j i且nums[j] nums[i]。復雜度O(n2)。優(yōu)化對于“最長遞增子序列”的長度問題可以采用“貪心二分查找”的方法將復雜度降至O(n log n)。維護一個數(shù)組tails其中tails[k]存儲長度為k1的遞增子序列的最小末尾元素。遍歷原數(shù)組用二分查找在tails中找到第一個大于等于當前元素x的位置并替換它。如果x大于所有tails中的元素則追加到末尾。最終tails的長度就是LIS的長度。這個方法只用于求長度無法得到具體的子序列。變形題實戰(zhàn)我們來看一道集訓中的題目它融合了LIS思想和前綴和。題目描述給定一個數(shù)組你可以進行任意次操作每次操作選擇一個數(shù)將其加1或減1。求最少操作次數(shù)使得數(shù)組變成一個嚴格遞增的序列。要求最終序列的每個數(shù)必須是正整數(shù)。分析最樸素的想法枚舉最終序列。但最終序列的值域可能很大無法枚舉。關鍵洞察對于最終嚴格遞增的序列b[]有b[i] b[i-1] 1。為了最小化操作次數(shù)Σ|a[i] - b[i]|并且b[i]必須是正整數(shù)一個經(jīng)典的技巧是進行變換。變換令c[i] a[i] - i。那么原問題中b[i] b[i-1]等價于b[i] - i b[i-1] - (i-1)。我們定義d[i] b[i] - i則要求d[i] d[i-1]即序列d[]是非遞減的原問題轉(zhuǎn)化為求一個非遞減序列d[]使得Σ| (a[i] - i) - d[i] |最小且b[i] d[i] i 0。由于b[i]0所以d[i] -i在數(shù)據(jù)范圍內(nèi)通常很容易滿足可以暫時忽略此約束最后檢查。這是一個經(jīng)典的“將序列變?yōu)榉沁f減序列的最小代價”問題。有一個結(jié)論使得代價最小的非遞減序列d[]一定可以由原序列c[]中的某些數(shù)組成。問題進一步轉(zhuǎn)化為在c[]中找一個非遞減子序列允許相等使得Σ|c[i] - 子序列對應值|最小。這可以通過動態(tài)規(guī)劃解決但更優(yōu)的方法是使用“中位數(shù)貪心”或者用“帶權最長不下降子序列”的思路。一個實用的解法適用于本題數(shù)據(jù)范圍中等的情況是定義dp[i][j]為考慮前i個元素且第i個元素變?yōu)榈趈大的c[]中的值離散化后時的最小代價。狀態(tài)轉(zhuǎn)移方程為dp[i][j] min(dp[i-1][k]) |c[i] - val[j]|其中k j。這個min(dp[i-1][k])可以用前綴最小值優(yōu)化將復雜度從O(n3)降為O(n2)。這道題充分展示了如何通過巧妙的數(shù)學變換a[i] - i將陌生問題嚴格遞增轉(zhuǎn)化為已知模型非遞減進而套用或修改經(jīng)典DP思路。4.2 狀態(tài)壓縮DP解決小規(guī)模集合問題當問題涉及到一個較小的集合比如不超過20個元素的“選取”或“排列”狀態(tài)時狀態(tài)壓縮DP是利器。它用一個整數(shù)的二進制位來表示集合的狀態(tài)。經(jīng)典問題旅行商問題TSP的簡化版。有n個城市n 20給出兩兩之間的旅行成本求從城市0出發(fā)經(jīng)過所有城市恰好一次最后回到城市0的最小成本。狀態(tài)設計dp[S][i]表示已經(jīng)訪問過的城市集合為S二進制掩碼并且當前位于城市i的最小成本。S是一個n位的二進制數(shù)第k位為1表示城市k已訪問。初始狀態(tài)dp[1 0][0] 0表示從城市0出發(fā)只訪問了城市0成本為0。狀態(tài)轉(zhuǎn)移要從狀態(tài)(S, i)轉(zhuǎn)移到(S| (1 j), j)其中城市j未被訪問過即S的第j位為0。轉(zhuǎn)移成本為dp[S][i] cost[i][j]。我們需要更新dp[S|(1j)][j]為最小值。最終答案遍歷所有城市i取dp[(1n)-1][i] cost[i][0]的最小值即訪問完所有城市后從最后所在城市i返回起點0的總成本。代碼框架int n 20; vectorvectorint cost(n, vectorint(n)); vectorvectorint dp(1 n, vectorint(n, INF)); dp[1][0] 0; // 從城市0開始 for (int mask 1; mask (1 n); mask) { for (int i 0; i n; i) { if (!(mask (1 i))) continue; // 當前狀態(tài)必須包含i if (dp[mask][i] INF) continue; // 無效狀態(tài) for (int j 0; j n; j) { if (mask (1 j)) continue; // j不能已經(jīng)訪問過 int newMask mask | (1 j); dp[newMask][j] min(dp[newMask][j], dp[mask][i] cost[i][j]); } } } int ans INF; int fullMask (1 n) - 1; for (int i 0; i n; i) { if (dp[fullMask][i] ! INF) { ans min(ans, dp[fullMask][i] cost[i][0]); } }注意事項狀態(tài)壓縮DP的復雜度通常是O(2^n * n2)當n20時2^20 ≈ 1e6再乘以n2(400)是4e8在時間限制較緊時可能需要進行常數(shù)優(yōu)化或者尋找其他思路。對于TSP問題n20通常是極限。5. 搜索與剪枝暴力算法的藝術當問題沒有明顯的多項式解法時搜索DFS/BFS是兜底的選擇。但純暴力往往超時因此“剪枝”技術至關重要。5.1 DFS回溯與可行性剪枝典型問題N皇后問題數(shù)獨問題。 以數(shù)獨為例這是一個經(jīng)典的DFS回溯問題。我們需要在9x9的空格中填入數(shù)字1-9滿足每行、每列、每個3x3宮內(nèi)數(shù)字不重復。樸素DFS每次找一個空格嘗試填1-9如果合法就遞歸不合法就回溯。這個搜索樹非常大。剪枝策略最優(yōu)順序剪枝不要按固定順序如從左到右、從上到下選擇空格。每次都選擇當前可填數(shù)字最少的空格即候選數(shù)最少的格子。這能極大減少分支數(shù)量。這需要實時維護每個空格的行、列、宮的約束情況。可行性剪枝在嘗試填入一個數(shù)字前快速檢查它是否違反行、列、宮的約束?？梢杂梦贿\算加速用三個9x9的整數(shù)數(shù)組row、col、box其每個元素的第k位表示數(shù)字k1是否可用。檢查(row[i] col[j] box[bid])的結(jié)果中哪些位為1就表示哪些數(shù)字可以填。唯一候選數(shù)剪枝在填某個空格的候選數(shù)時如果發(fā)現(xiàn)某個數(shù)字在該行、該列或該宮的其他所有位置都不能填那么這個數(shù)字必須填在這個位置。位運算優(yōu)化示例int row[9], col[9], box[9]; // 初始化為0x1FF (二進制9個1)表示所有數(shù)字可用 // 獲取位置(i, j)可以填的數(shù)字的位掩碼 int getPossible(int i, int j) { int b (i / 3) * 3 (j / 3); return row[i] col[j] box[b]; } // 填入數(shù)字num (0-8 表示1-9) void placeNumber(int i, int j, int num) { int b (i / 3) * 3 (j / 3); int mask 1 num; row[i] ^ mask; // 將第num位取反表示占用 col[j] ^ mask; box[b] ^ mask; board[i][j] num 1; } // 移除數(shù)字 void removeNumber(int i, int j, int num) { int b (i / 3) * 3 (j / 3); int mask 1 num; row[i] ^ mask; // 再次取反恢復可用 col[j] ^ mask; box[b] ^ mask; board[i][j] .; }通過這種高級剪枝和位運算優(yōu)化即使是“最難數(shù)獨”也能在毫秒級內(nèi)求解。5.2 BFS與雙向BFS對于狀態(tài)空間很大但只求最短步數(shù)的問題BFS是標準解法。但當狀態(tài)空間過于龐大時單向BFS可能因為隊列膨脹而超時或超內(nèi)存。雙向BFS應運而生。它從起點和終點同時開始BFS當兩邊的搜索相遇時路徑長度就是兩邊步數(shù)之和加一。這能極大減少搜索的寬度。適用場景狀態(tài)轉(zhuǎn)移可逆且起點和終點狀態(tài)明確。算法流程準備兩個隊列q_start,q_end和兩個記錄距離或?qū)訑?shù)的映射dist_start,dist_end。初始化q_start放入起點dist_start[start]0q_end放入終點dist_end[end]0。每次選擇當前節(jié)點數(shù)較少的那一邊進行擴展一層平衡兩端搜索速度。擴展節(jié)點時檢查新狀態(tài)是否在另一端的dist映射中出現(xiàn)過。如果出現(xiàn)過則找到相遇點最短路徑為dist_start[cur] 1 dist_end[new]。否則更新本端的dist映射并將新狀態(tài)加入本端隊列。注意事項雙向BFS在狀態(tài)空間呈指數(shù)增長時優(yōu)勢明顯例如在“八數(shù)碼”問題或某些字符串變換問題中。實現(xiàn)時判斷“相遇”是關鍵通常用哈希集合如unordered_set來記錄一端已訪問的狀態(tài)另一端擴展時進行查找。雙向BFS的代碼比單向BFS復雜但一旦掌握是解決此類問題的強力工具。6. 圖論算法實戰(zhàn)最短路徑與最小生成樹圖論題目在競賽中占比很高其中最基礎也最重要的是最短路徑和最小生成樹。6.1 Dijkstra算法單源最短路的黃金標準用于求解非負權圖的單源最短路徑。其核心是貪心策略使用優(yōu)先隊列小頂堆優(yōu)化。算法步驟初始化距離數(shù)組dist[]起點為0其余為無窮大。將起點(dist0, node)放入優(yōu)先隊列。當隊列非空彈出當前距離最小的節(jié)點u。如果彈出的dist[u]大于當前記錄的距離說明是舊數(shù)據(jù)直接跳過懶惰刪除這是優(yōu)先隊列優(yōu)化的關鍵技巧。遍歷u的所有鄰接邊(u, v, w)。如果dist[u] w dist[v]則更新dist[v]并將(dist[v], v)入隊。C實現(xiàn)鄰接表使用vectorpairint, int graph[N]const int INF 0x3f3f3f3f; vectorint dijkstra(int start, int n, vectorvectorpairint, int graph) { vectorint dist(n, INF); dist[start] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; // 最小堆 pq.emplace(0, start); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 關鍵跳過已過時的記錄 for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.emplace(dist[v], v); } } } return dist; }常見錯誤用于帶負權邊的圖。Dijkstra算法基于貪心假設當前最短路徑就是全局最短負權邊會破壞這個假設。對于含負權邊的圖應使用SPFA或Bellman-Ford算法。沒有使用“懶惰刪除”導致同一個節(jié)點多次入隊隊列膨脹。上述代碼中的if (d dist[u]) continue;就是處理這個問題的標準寫法。6.2 最小生成樹Kruskal與Prim算法用于在加權連通圖中找出一棵權值和最小的生成樹。Kruskal算法更易于理解和實現(xiàn)適用于稀疏圖。將所有邊按權值從小到大排序。初始化一個并查集。按順序遍歷每條邊(u, v, w)如果u和v不在同一個連通分量中用并查集檢查就將這條邊加入生成樹并合并u和v所在的集合。當選中n-1條邊時結(jié)束。Prim算法類似于Dijkstra適用于稠密圖。任選一個起點加入集合T已包含在生成樹中的點集。維護一個優(yōu)先隊列存放所有連接T集合與外部節(jié)點的邊(u, v, w)其中u在T內(nèi)v在T外。鍵值為邊權w。每次取出權值最小的邊將對應的外部節(jié)點v加入T并將v連接外部的新邊加入優(yōu)先隊列。重復直到所有節(jié)點加入T。選擇策略如果圖用鄰接矩陣存儲且非常稠密Prim算法未優(yōu)化版的O(V2)可能比Kruskal的O(E log E)快。在大多數(shù)情況下特別是使用鄰接表并配合優(yōu)先隊列優(yōu)化O(E log V)的Prim與Kruskal性能相近。我個人更偏愛Kruskal因為其代碼簡潔且并查集是通用組件。7. 調(diào)試技巧與常見“坑點”實錄即使思路正確實現(xiàn)時也可能掉入各種陷阱。這里分享幾個我踩過的“坑”和調(diào)試方法。7.1 多組數(shù)據(jù)輸入的初始化問題這是新手最常見的錯誤之一。題目要求處理T組測試數(shù)據(jù)但忘記在每組數(shù)據(jù)開始前清空全局的vector、map、隊列等數(shù)據(jù)結(jié)構(gòu)。錯誤示例vectorint graph[MAXN]; // 全局鄰接表 int vis[MAXN]; void solve() { int T; cin T; while (T--) { int n, m; cin n m; // 忘記清空 graph 和 vis for (int i 0; i m; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); } // ... BFS/DFS ... } }正確做法要么將數(shù)據(jù)結(jié)構(gòu)定義在while循環(huán)內(nèi)部推薦作用域清晰要么在循環(huán)開始時手動清空。void solve() { int T; cin T; while (T--) { int n, m; cin n m; vectorvectorint graph(n 1); // 局部變量自動初始化 vectorint vis(n 1, 0); // ... 后續(xù)操作 ... } }7.2 整數(shù)溢出與精度問題中間結(jié)果溢出即使最終答案在int范圍內(nèi)計算過程中的中間變量也可能溢出。例如計算組合數(shù)C(n, m)時分子階乘很容易超出long long范圍。需要使用取模運算或者在計算時及時約分如用遞推公式C(n, m) C(n-1, m-1) C(n-1, m)。浮點數(shù)比較不要直接用比較浮點數(shù)。應該判斷兩者差的絕對值是否小于一個極小值eps如1e-9。if (fabs(a - b) 1e-9) { // 認為相等 }除法取整在C/C中整數(shù)除法是向零取整。如果需要向上取整公式是(a b - 1) / b而不是ceil((double)a / b)后者有浮點誤差和性能開銷。7.3 邊界條件與特殊輸入空輸入題目說“有多行輸入”但可能第一行就是EOF。你的讀入循環(huán)要能處理這種情況。while (cin n m) { // 這樣寫可以自然處理EOF // ... }n0 或 n1圖論、樹相關問題中節(jié)點數(shù)為0或1時你的算法是否能正確處理DP問題中數(shù)組長度為0或1時初始化是否正確負權邊與零權環(huán)在使用基于松弛操作的最短路算法如SPFA時要能檢測負權環(huán)。零權環(huán)雖然不會讓路徑無限小但可能導致算法陷入死循環(huán)或得到非簡單路徑需要根據(jù)題意判斷是否允許。7.4 調(diào)試輸出與對拍當程序結(jié)果錯誤時不要盲目盯著代碼看。小數(shù)據(jù)調(diào)試構(gòu)造一些小的測試用例在本地用cout或printf打印出關鍵變量的中間結(jié)果與手算結(jié)果對比。對拍寫一個絕對正確但可能很慢的暴力程序brute.cpp和你的優(yōu)化程序sol.cpp同時運行。用隨機數(shù)據(jù)生成器gen.cpp產(chǎn)生大量隨機輸入比較兩個程序的輸出。一旦發(fā)現(xiàn)不一致就找到了讓程序出錯的測試數(shù)據(jù)然后針對這個數(shù)據(jù)縮小規(guī)模進行單步調(diào)試。這是競賽中查找隱蔽錯誤的最有效方法。使用調(diào)試器熟練使用GDB或IDE的調(diào)試功能設置斷點查看變量單步執(zhí)行能幫你快速定位邏輯錯誤。集訓的題目千變?nèi)f化但核心的解題思想和代碼實現(xiàn)技巧是相通的。這份題解記錄了我認為最有價值的部分。真正的提升來自于將這里的方法論應用到每一道新題上不斷練習、總結(jié)和反思。最后保持一顆平常心享受解決難題帶來的純粹快樂這才是算法競賽或者說任何技術學習中最持久的內(nèi)驅(qū)力。