1. 項目概述一次對經(jīng)典賽題的深度復(fù)盤最近整理硬盤翻到了幾年前備賽藍(lán)橋杯時留下的筆記和代碼其中2017年B組C國賽的幾道題讓我印象尤為深刻。那年的題目在算法思維和工程實(shí)現(xiàn)上結(jié)合得相當(dāng)巧妙既有對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的扎實(shí)考察也不乏需要靈光一現(xiàn)的“腦筋急轉(zhuǎn)彎”。雖然標(biāo)題里寫的是“部分題解”但我想挑出其中最具代表性的三道題不僅給出答案更重要的是拆解當(dāng)時的解題心路歷程、代碼實(shí)現(xiàn)中的關(guān)鍵抉擇以及那些賽后復(fù)盤才恍然大悟的優(yōu)化點(diǎn)。無論你是正在備賽的選手還是想通過真題來錘煉自己C算法能力的開發(fā)者相信這次“穿越時空”的復(fù)盤都能帶來一些實(shí)實(shí)在在的收獲。我們不會停留在“AC”就萬事大吉的層面而是會深入探討為什么這道題用這個算法邊界條件到底坑在哪里從暴力枚舉到最優(yōu)解思維是如何一步步躍遷的2. 核心賽題解析與解題思路拆解2.1 真題定位與整體難度評估2017年藍(lán)橋杯軟件類國賽C大學(xué)B組的題目延續(xù)了其一貫的風(fēng)格前面幾題側(cè)重基礎(chǔ)語法和簡單邏輯用于“保分”中間部分考察經(jīng)典算法如DFS、BFS、動態(tài)規(guī)劃的應(yīng)用能力最后壓軸題則往往需要較強(qiáng)的數(shù)學(xué)建?；虺橄笏季S能力。這次我們重點(diǎn)分析的“部分”題目正是選自中后段的精華它們能有效區(qū)分出“會寫代碼”和“善于用算法解決問題”的選手。從網(wǎng)絡(luò)熱詞如“快速冪算法c”、“c八大排序算法”、“動態(tài)規(guī)劃”可以看出大家關(guān)注的正是這些核心的算法考點(diǎn)。而“藍(lán)橋杯真題”、“題解”等高頻搜索詞則反映了大量學(xué)習(xí)者渴望獲得的不只是答案更是清晰的解題邏輯和可復(fù)現(xiàn)的思考過程。因此我們的解析將緊扣“思路產(chǎn)生-算法選擇-代碼實(shí)現(xiàn)-邊界處理”這條主線。2.2 解題通用心法與賽場策略在深入具體題目之前有必要先統(tǒng)一一下“作戰(zhàn)思想”。藍(lán)橋杯的評測系統(tǒng)是OI賽制即提交后立即知道對錯但看不到具體用例。這帶來兩個核心策略暴力法保底對于任何題目第一時間思考能否用簡單的模擬或枚舉拿到部分分?jǐn)?shù)。即使時間復(fù)雜度很高也可能通過一些數(shù)據(jù)規(guī)模較小的測試點(diǎn)。這是非常重要的得分策略切忌在難題上鉆牛角尖而浪費(fèi)了簡單題的分?jǐn)?shù)。觀察數(shù)據(jù)范圍定算法題目給出的數(shù)據(jù)范圍如N1000或N100000是選擇算法的決定性依據(jù)。N20可能暗示狀壓DP或暴力DFSN1000 O(n2)的動態(tài)規(guī)劃或樸素算法可能可行N100000則通常要求O(nlogn)或O(n)的算法。注意賽場上的第一要務(wù)是拿到盡可能多的分?jǐn)?shù)而不是追求每道題的最優(yōu)解。一個能通過60%測試點(diǎn)的暴力解遠(yuǎn)比一個思路完美但調(diào)試了1小時仍有bug的“最優(yōu)解”有價值。3. 賽題一方格分割DFS與對稱性剪枝3.1 問題重述與抽象建模這是當(dāng)年一道非常經(jīng)典的搜索問題。題目大意是一個6x6的方格矩陣沿著格線將其分割成完全相同的兩部分。要求分割線必須從矩陣的中心點(diǎn)格點(diǎn)不是格子出發(fā)到達(dá)矩陣的邊界并且分割線不能自交。問一共有多少種不同的分割方案。初看此題很容易被“分割成兩部分”迷惑去思考如何切割格子。關(guān)鍵的抽象技巧在于轉(zhuǎn)換視角不要盯著“剪開的格子”而是關(guān)注“走過的格點(diǎn)”。將6x6的方格擴(kuò)展為7x7的格點(diǎn)陣因為格線交點(diǎn)才是格點(diǎn)。中心點(diǎn)是(3,3)。問題轉(zhuǎn)化為從中心點(diǎn)(3,3)出發(fā)每次向上、下、左、右四個方向移動一格走到邊界點(diǎn)即x或y坐標(biāo)為0或6為止。要求走過的路徑必須關(guān)于中心點(diǎn)(3,3)中心對稱且路徑不能重復(fù)訪問同一個格點(diǎn)保證不自交。為什么是對稱的因為剪開成相同的兩部分意味著你在這部分邊界上走出的路徑在另一部分的邊界上必然存在一條完全中心對稱的路徑。而這兩條對稱的路徑合起來就是一條從中心到邊界、再對稱折返到中心的閉合路徑不這里容易出錯。更準(zhǔn)確地說我們只需要搜索一條從中心到邊界的路徑其對稱路徑會自動生成。同時由于整個圖形是中心對稱的一條路徑和它的對稱路徑會將所有格點(diǎn)分成兩個集合。為了避免重復(fù)計算順時針走和逆時針走被視為同一種分割我們需要在搜索時施加一個方向限制。3.2 DFS實(shí)現(xiàn)與關(guān)鍵剪枝策略基于以上分析我們可以采用深度優(yōu)先搜索DFS來枚舉所有從(3,3)到邊界的路徑并檢查其對稱性。但直接DFS的搜索樹會非常龐大。核心剪枝對稱性剪枝與方向限制由于最終分割方案是中心對稱的那么如果我們搜索的路徑觸碰到了它的對稱點(diǎn)就會導(dǎo)致路徑自交因為對稱點(diǎn)本應(yīng)是另一部分的。因此在DFS過程中我們每走到一個新點(diǎn)(x, y)不僅要標(biāo)記這個點(diǎn)已訪問還必須立即標(biāo)記其對稱點(diǎn)(6-x, 6-y)也為已訪問。這樣就能天然保證搜索出的路徑不會侵犯對稱區(qū)域。方向限制以去重由于一種分割方案由一條中心對稱的閉合邊界構(gòu)成從中心點(diǎn)出發(fā)第一步有四個方向。但是上下、左右是對稱的。如果我們不加以限制會把本質(zhì)上相同的方案旋轉(zhuǎn)或?qū)ΨQ后一致重復(fù)計算。一個簡單有效的去重方法是規(guī)定第一步只能走一個方向比如向右或向下。因為任何合法方案都可以通過旋轉(zhuǎn)使其第一步是向右的。這樣最終結(jié)果需要乘以4嗎不需要因為我們在標(biāo)記對稱點(diǎn)時已經(jīng)將整個搜索空間約束在了第一象限相對概念最終結(jié)果就是唯一計數(shù)。#include iostream #include cstring using namespace std; int dirs[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; // 四個方向 bool visited[7][7]; // 標(biāo)記7x7格點(diǎn)是否已訪問 int ans 0; void dfs(int x, int y) { // 到達(dá)邊界不能是中心點(diǎn) if (x 0 || x 6 || y 0 || y 6) { ans; return; } for (int i 0; i 4; i) { int nx x dirs[i][0]; int ny y dirs[i][1]; // 檢查新坐標(biāo)是否合法且未訪問 if (nx 0 nx 6 ny 0 ny 6 !visited[nx][ny]) { // 標(biāo)記當(dāng)前點(diǎn)及其對稱點(diǎn) visited[nx][ny] true; visited[6-nx][6-ny] true; // 關(guān)鍵對稱剪枝 dfs(nx, ny); // 回溯 visited[nx][ny] false; visited[6-nx][6-ny] false; } } } int main() { memset(visited, false, sizeof(visited)); // 標(biāo)記中心點(diǎn)及其對稱點(diǎn)自身 visited[3][3] true; // 從中心點(diǎn)開始搜索 dfs(3, 3); // 因為搜索樹是對稱的且我們每一步都標(biāo)記了對稱點(diǎn) // 所以答案就是方案數(shù)。但注意從中心點(diǎn)向四個方向出發(fā)本質(zhì)是旋轉(zhuǎn)對稱。 // 我們固定了搜索順序但初始點(diǎn)(3,3)的對稱點(diǎn)還是(3,3)所以不會重復(fù)。 // 最終需要將結(jié)果除以4嗎不需要因為我們的visited標(biāo)記和搜索規(guī)則已經(jīng)保證了每種分割只被以一種“朝向”搜索一次。 // 更準(zhǔn)確的做法是限制第一步的方向比如只向右走(3,3)-(4,3) ans 0; // 重置重新計算 memset(visited, false, sizeof(visited)); visited[3][3] true; visited[4][3] true; // 第一步向右 visited[2][3] true; // 標(biāo)記對稱點(diǎn)向左 dfs(4, 3); // 從(4,3)開始搜 cout ans * 4 endl; // 由于限制了第一步方向最終結(jié)果要乘以4 return 0; }實(shí)操心得這道題在賽場上的難點(diǎn)在于抽象建模。很多選手卡在如何表示“切割”上。一旦成功轉(zhuǎn)化為“在格點(diǎn)圖上搜索對稱路徑”的模型代碼實(shí)現(xiàn)并不復(fù)雜。DFS函數(shù)本身很標(biāo)準(zhǔn)真正的靈魂在于visited[6-nx][6-ny] true;這一行對稱標(biāo)記。它同時完成了兩項任務(wù)一是防止路徑走到自身對稱的位置導(dǎo)致自交二是保證了搜索出的路徑其對稱路徑必然存在且不沖突。這比先搜索完整路徑再檢查對稱性要高效無數(shù)倍。常見誤區(qū)在6x6的“格子”上搜索而不是7x7的“格點(diǎn)”上搜索導(dǎo)致模型錯誤。忘記了去重將旋轉(zhuǎn)或?qū)ΨQ后相同的方案計為多種。對稱標(biāo)記時坐標(biāo)計算錯誤(x,y)的對稱點(diǎn)應(yīng)是(6-x, 6-y)而不是(5-x, 5-y)那是針對6x6格子的索引。4. 賽題二磁磚樣式狀態(tài)壓縮與哈希去重4.1 問題理解與搜索空間分析這道題可以看作是“鋪瓷磚”問題的一個變種。題目描述了一個2行N列的網(wǎng)格現(xiàn)在有無限多的1x2占兩格的磁磚可以橫著鋪覆蓋同一行的兩列也可以豎著鋪覆蓋兩行同一列。要求鋪滿整個網(wǎng)格并且規(guī)定兩種顏色假設(shè)為A和B的磁磚都不能有超過2x2的“同色四格”區(qū)域出現(xiàn)。即在任意一個2x2的子區(qū)域內(nèi)不能所有格子都是同一種顏色。我們需要計算所有不同的鋪滿方案數(shù)。N的具體規(guī)模需要看題目印象中是10。即使N10搜索空間也巨大無比。因為每個格子最終的顏色由覆蓋它的磁磚決定而磁磚的擺放方式很多。解題核心思路按列進(jìn)行狀態(tài)壓縮DP或DFS回溯。由于瓷磚是1x2的它的擺放只影響當(dāng)前列和下一列橫鋪或者當(dāng)前列的兩行豎鋪。這提示我們可以一列一列地遞推鋪設(shè)。定義每一列的“狀態(tài)”可以用一個數(shù)字表示該列兩行格子的鋪設(shè)情況和顏色。但這樣狀態(tài)會非常復(fù)雜因為要同時記錄是否被覆蓋以及顏色。一個更清晰的思路是DFS回溯 狀態(tài)哈希去重。我們模擬整個鋪設(shè)過程從左到右從上到下嘗試放置瓷磚。放置時檢查1. 是否超出邊界2. 目標(biāo)格子是否已被覆蓋3. 放置后是否會產(chǎn)生非法的2x2同色區(qū)域。4.2 DFS回溯實(shí)現(xiàn)與關(guān)鍵優(yōu)化我們用一個二維數(shù)組grid來表示網(wǎng)格初始為0表示未覆蓋。用1表示顏色A2表示顏色B。DFS函數(shù)參數(shù)至少包含當(dāng)前要放置的起點(diǎn)坐標(biāo)(x, y)。放置策略每次找到第一個未覆蓋的格子(x,y)嘗試兩種放置方式豎放如果x1 2且grid[x1][y]0則可以放置一塊豎磚。隨機(jī)或按順序賦予它一個顏色1或2。橫放如果y1 N且grid[x][y1]0則可以放置一塊橫磚。同樣賦予顏色。合法性檢查核心每次放置一塊新磚后需要檢查所有包含新磚格子的2x2區(qū)域。遍歷所有以新磚格子為右下角、左上角、左下角、右上角的2x2區(qū)域確保區(qū)域在網(wǎng)格內(nèi)檢查該區(qū)域內(nèi)四個格子是否都已覆蓋且顏色相同。如果存在這樣的區(qū)域則當(dāng)前放置非法需要回溯。去重難點(diǎn)由于顏色只是抽象的“A”和“B”方案“AABB”和“BBAA”如果只是顏色互換在題目中可能被視為同一種如果題目說明顏色不同視為不同則不去重。通常這類題目中顏色是具體的如紅藍(lán)互換后視為不同方案。但2017年這道題需要仔細(xì)審題。一個更嚴(yán)峻的去重問題是網(wǎng)格是2行的旋轉(zhuǎn)、對稱后相同的方案如何避免重復(fù)計數(shù)題目通常要求計算“本質(zhì)不同”的方案數(shù)。一個可靠的方法是當(dāng)整個網(wǎng)格鋪滿后將其狀態(tài)編碼成一個唯一字符串或數(shù)字例如將每一行連起來存入一個unordered_set中進(jìn)行去重。#include iostream #include cstring #include unordered_set using namespace std; int N; // 列數(shù)根據(jù)題目設(shè)定 int grid[2][12]; // 假設(shè)N最大為12 unordered_setstring schemes; // 用于去重 int ans 0; // 檢查以(i,j)為左上角的2x2區(qū)域是否同色非法 bool check(int x, int y) { // 檢查所有包含(x,y)的2x2區(qū)域 // 區(qū)域左上角可能為 (x-1, y-1), (x-1, y), (x, y-1), (x, y) // 但要確保區(qū)域在[0,1]行和[0, N-1]列內(nèi) for (int i max(0, x-1); i x i 1; i) { // i最多到0因為2行網(wǎng)格2x2區(qū)域的左上角行號只能是0 for (int j max(0, y-1); j y j N-1; j) { // j最多到N-2 // 現(xiàn)在(i,j)是可能的2x2區(qū)域左上角 if (grid[i][j] grid[i][j1] grid[i1][j] grid[i1][j1]) { if (grid[i][j] grid[i][j1] grid[i][j] grid[i1][j] grid[i][j] grid[i1][j1]) { return false; // 發(fā)現(xiàn)非法同色2x2 } } } } return true; } void dfs(int pos) { // 線性化位置pos x * N y if (pos 2 * N) { // 鋪滿了編碼狀態(tài)并去重 string key; for (int i 0; i 2; i) { for (int j 0; j N; j) { key char(0 grid[i][j]); } } if (schemes.find(key) schemes.end()) { schemes.insert(key); ans; } return; } int x pos / N; int y pos % N; // 如果當(dāng)前格子已覆蓋繼續(xù)下一個 if (grid[x][y]) { dfs(pos 1); return; } // 嘗試豎放 (顏色1) if (x 0 !grid[x1][y]) { // 豎放只能從第一行開始放 grid[x][y] grid[x1][y] 1; if (check(x, y) check(x1, y)) { dfs(pos 1); } grid[x][y] grid[x1][y] 0; // 回溯 } // 嘗試豎放 (顏色2) if (x 0 !grid[x1][y]) { grid[x][y] grid[x1][y] 2; if (check(x, y) check(x1, y)) { dfs(pos 1); } grid[x][y] grid[x1][y] 0; } // 嘗試橫放 (顏色1) if (y N-1 !grid[x][y1]) { grid[x][y] grid[x][y1] 1; if (check(x, y) check(x, y1)) { dfs(pos 1); } grid[x][y] grid[x][y1] 0; } // 嘗試橫放 (顏色2) if (y N-1 !grid[x][y1]) { grid[x][y] grid[x][y1] 2; if (check(x, y) check(x, y1)) { dfs(pos 1); } grid[x][y] grid[x][y1] 0; } } int main() { cin N; // 實(shí)際比賽時N是給定的這里假設(shè)輸入 memset(grid, 0, sizeof(grid)); dfs(0); cout ans endl; return 0; }踩坑記錄這道題我初次實(shí)現(xiàn)時效率極低N10都跑不出來。主要瓶頸在于檢查函數(shù)check調(diào)用過于頻繁每次放置后都全盤掃描檢查2x2區(qū)域是不現(xiàn)實(shí)的。優(yōu)化后只檢查與新放置格子相關(guān)的幾個2x2區(qū)域最多4個。搜索順序線性化位置(x,y)并按順序找到第一個空位放置比雙重循環(huán)更清晰也避免了重復(fù)搜索。去重編碼最初我使用了將整個網(wǎng)格轉(zhuǎn)為字符串的方法在N較大時字符串操作和哈希比較會成為瓶頸。對于狀態(tài)壓縮DP更好的方法是用一個長整型如long long的位運(yùn)算來編碼狀態(tài)但本題由于有顏色1和2需要至少2比特表示一個格子狀態(tài)編碼會復(fù)雜一些。提示在競賽中如果N不大比如8這種DFS哈希的方法在合理剪枝后是可行的。如果N更大比如15就必須用狀態(tài)壓縮DP了狀態(tài)設(shè)計為dp[i][mask]其中mask編碼了當(dāng)前列兩行的鋪設(shè)情況和顏色然后遞推下一列。但實(shí)現(xiàn)難度會高一個數(shù)量級。5. 賽題三對局匹配動態(tài)規(guī)劃與分組思想5.1 問題轉(zhuǎn)化與分組處理這道題是動態(tài)規(guī)劃的經(jīng)典應(yīng)用也涉及了巧妙的數(shù)學(xué)思想。題目描述大致是有N個玩家每個玩家有一個實(shí)力積分值X。系統(tǒng)會將積分值相差恰好為K的玩家匹配到一起進(jìn)行對局?，F(xiàn)在的問題是如果一些玩家同時在線他們可能會被匹配到。我們希望從中挑選出一個最大的玩家子集使得這個子集中任意兩名玩家的積分差都不等于K從而保證他們在線時永遠(yuǎn)不會被系統(tǒng)匹配到。輸入玩家積分?jǐn)?shù)組和差值K。輸出最大子集的大小。暴力思路不可行N可以很大10^5級別枚舉所有子集是2^N不可能。關(guān)鍵轉(zhuǎn)化將玩家按積分對K取模的結(jié)果進(jìn)行分組。 為什么因為如果兩個玩家的積分差為K那么他們除以K的余數(shù)一定相同。例如K2積分3和5差2它們除以2的余數(shù)都是1。積分4和6差2余數(shù)都是0。也就是說差值為K的玩家必然存在于同一個“余數(shù)分組”內(nèi)。不同余數(shù)分組之間的玩家積分差絕不可能是K因為積分差是K的倍數(shù)才會導(dǎo)致同余。因此問題從全局的一個大問題分解成了若干個獨(dú)立的子問題在每個余數(shù)分組內(nèi)選取一個最大的子集使得集合中任意兩個數(shù)的差不為K。由于分組間獨(dú)立最后將每個分組能選出的最大人數(shù)相加即可。5.2 分組內(nèi)的動態(tài)規(guī)劃模型現(xiàn)在問題簡化為對于一個分組假設(shè)余數(shù)為r里面有一系列積分值r, rK, r2K, r3K, ...。我們要從中選出一個子集不能選擇相鄰的項因為選了rmK就不能選r(m1)K和r(m-1)K否則差為K。這變成了一個經(jīng)典的打家劫舍或不相鄰元素最大和問題的變種。只不過這里的“價值”不是積分值本身而是擁有該積分值的玩家數(shù)量。因為可能有多個玩家積分相同。假設(shè)我們將該分組內(nèi)的積分值排序得到一個序列a[0], a[1], a[2], ...對應(yīng)的玩家數(shù)量為cnt[0], cnt[1], cnt[2], ...。定義dp[i]為考慮前i個積分值時能選出的最大玩家數(shù)。 狀態(tài)轉(zhuǎn)移方程為如果不選第i個積分值dp[i] dp[i-1]如果選第i個積分值因為不能選第i-1個所以dp[i] dp[i-2] cnt[i](當(dāng)i2時)對于i1的情況特殊處理dp[1] max(cnt[0], cnt[1])最終dp[last]就是這個分組內(nèi)能選出的最大人數(shù)。特殊情況K0。當(dāng)K0時分組條件積分差為0意味著所有積分相同的玩家都在一個組里并且他們之間都會發(fā)生匹配。那么在這個“組”里我們最多只能選擇一種積分的玩家并且應(yīng)該選擇玩家數(shù)量最多的那種積分。因為如果選了兩種不同積分此時差不為0因為K0時差為0才沖突他們之間不會沖突但題目要求是差為K的不能共存K0時就是積分相同的不能共存。所以對于K0問題簡化為找出哪個積分值的人數(shù)最多答案就是這個人數(shù)。5.3 C代碼實(shí)現(xiàn)與細(xì)節(jié)處理#include iostream #include vector #include map #include algorithm using namespace std; int main() { int N, K; cin N K; vectorint scores(N); mapint, int cnt_map; // 統(tǒng)計每個積分的人數(shù) for (int i 0; i N; i) { cin scores[i]; cnt_map[scores[i]]; } if (K 0) { // 特殊情況K0只能選一種積分選人數(shù)最多的 int max_cnt 0; for (auto p : cnt_map) { max_cnt max(max_cnt, p.second); } cout max_cnt endl; return 0; } // 通用情況K 0 // 用于存儲每個余數(shù)分組下的積分值 人數(shù)列表 mapint, vectorpairint, int groups; for (auto p : cnt_map) { int score p.first; int count p.second; int mod score % K; groups[mod].push_back({score, count}); } int total 0; // 處理每個余數(shù)分組 for (auto group : groups) { auto vec group.second; // vec里是(score, count) // 按積分值排序 sort(vec.begin(), vec.end()); int m vec.size(); if (m 0) continue; // 動態(tài)規(guī)劃 vectorint dp(m, 0); dp[0] vec[0].second; // 只有第一個積分值可選 if (m 1) { // 對于前兩個如果它們積分差為K則不能同時選 // 因為vec是按積分排序的且同余所以相鄰項差一定是K的倍數(shù)。 // 由于同余且排序相鄰的積分差就是K。 if (vec[1].first - vec[0].first K) { dp[1] max(vec[0].second, vec[1].second); } else { // 如果差不是K理論上在同余組內(nèi)排序后相鄰差就是K這里為了邏輯完整保留 dp[1] vec[0].second vec[1].second; } } for (int i 2; i m; i) { // 檢查當(dāng)前積分與上一個積分差是否為K if (vec[i].first - vec[i-1].first K) { // 不能同時選i和i-1 dp[i] max(dp[i-1], dp[i-2] vec[i].second); } else { // 可以同時選i和i-1 dp[i] dp[i-1] vec[i].second; } } total dp[m-1]; } cout total endl; return 0; }算法精講這個解法的核心在于“分組”思想將原問題從O(N2)的關(guān)聯(lián)中解脫出來變?yōu)槎鄠€O(M)的線性DP問題其中M是單個分組的長度。整體時間復(fù)雜度為O(N log N)主要用于排序和映射。一個極其重要的邊界條件在上述DP實(shí)現(xiàn)中我們假設(shè)了同一個余數(shù)分組內(nèi)積分值是等差數(shù)列公差為K。所以排序后相鄰元素的積分差一定是K嗎是的因為score % K r那么這些積分可以表示為r t*K(t為整數(shù))。排序后相鄰的t相差1所以積分差為K。因此if (vec[i].first - vec[i-1].first K)這個條件恒為真else分支永遠(yuǎn)不會執(zhí)行。代碼中可以簡化直接使用“不能選相鄰”的模型。我保留判斷是為了讓邏輯更清晰體現(xiàn)我們處理的是“差為K”這一條件。另一種更簡潔的DP寫法分組內(nèi)// vec是已經(jīng)按積分排序的積分人數(shù)列表相鄰積分差恒為K int m vec.size(); if (m 0) continue; vectorint dp(m1, 0); dp[0] 0; // 前0個元素最大人數(shù)為0 dp[1] vec[0].second; // 前1個元素只能選第一個 for (int i 2; i m; i) { // 考慮前i個元素對應(yīng)vec[0...i-1] // 不選第i個dp[i-1] // 選第i個dp[i-2] vec[i-1].second (因為不能選第i-1個) dp[i] max(dp[i-1], dp[i-2] vec[i-1].second); } total dp[m];這種寫法下標(biāo)處理更簡單是處理“不相鄰元素最大和”的標(biāo)準(zhǔn)DP寫法。6. 常見陷阱與調(diào)試心得實(shí)錄6.1 多組數(shù)據(jù)輸入與初始化藍(lán)橋杯的題目常常需要處理多組測試數(shù)據(jù)雖然國賽有時是單組。一個常見的坑是忘記在每組數(shù)據(jù)開始前清空全局變量和數(shù)據(jù)結(jié)構(gòu)。例如在“磁磚樣式”中g(shù)rid數(shù)組、ans計數(shù)器、schemes集合必須在處理每個新的N前重置。在“對局匹配”中cnt_map和groups也需要清空。使用C時如果變量定義在main函數(shù)內(nèi)則每次循環(huán)會自動重新創(chuàng)建如果是全局變量務(wù)必在循環(huán)體內(nèi)手動clear()或memset。// 錯誤示范全局變量 unordered_setstring schemes; int ans; void solve() { // ... 使用 schemes 和 ans ... // 處理完一組數(shù)據(jù)后如果沒有清空下一組數(shù)據(jù)會殘留上一組的結(jié)果 } // 正確做法 void solve() { unordered_setstring schemes; // 定義在函數(shù)內(nèi)自動管理 int ans 0; // ... 或者清空全局變量 ... // schemes.clear(); // ans 0; }6.2 整數(shù)溢出與數(shù)據(jù)類型選擇這是算法競賽中的經(jīng)典陷阱。在“對局匹配”中雖然最后的人數(shù)不會超過N10^5但DP過程中dp[i]的值可能累加不過仍在int范圍內(nèi)。但在其他題目尤其是涉及排列組合、路徑計數(shù)時結(jié)果可能非常大需要用到long long甚至高精度。例如有些題目結(jié)果需要對1e97取模這時不僅最終結(jié)果要用long long中間運(yùn)算也可能需要先轉(zhuǎn)為long long再取模防止乘法溢出。const int MOD 1e9 7; int a 1000000, b 1000000; // 錯誤乘法在int內(nèi)溢出然后才轉(zhuǎn)為long long取模 // int result (a * b) % MOD; // 正確先將乘數(shù)轉(zhuǎn)為long long long long result (1LL * a * b) % MOD;6.3 搜索與DP中的狀態(tài)設(shè)計誤區(qū)以“方格分割”為例狀態(tài)設(shè)計為visited[7][7]表示格點(diǎn)是否被訪問。一個誤區(qū)是只標(biāo)記當(dāng)前路徑點(diǎn)而忘了同步標(biāo)記對稱點(diǎn)導(dǎo)致搜索出的路徑不滿足對稱要求或者產(chǎn)生重復(fù)計數(shù)。在涉及對稱性、旋轉(zhuǎn)等去重問題時最好的辦法是在生成狀態(tài)的過程中就施加約束如第一步固定方向而不是生成所有狀態(tài)后再進(jìn)行復(fù)雜的去重判斷。在“磁磚樣式”的DFS中狀態(tài)是當(dāng)前的鋪設(shè)網(wǎng)格。如果直接使用網(wǎng)格數(shù)組進(jìn)行回溯每次遞歸調(diào)用都需要復(fù)制整個數(shù)組狀態(tài)開銷巨大。正確的做法是修改全局狀態(tài)數(shù)組并在回溯時恢復(fù)。對于更復(fù)雜、網(wǎng)格更大的問題則需要用狀態(tài)壓縮一個整數(shù)表示一行或一列的狀態(tài)來減少內(nèi)存和時間消耗。6.4 調(diào)試技巧輸出中間狀態(tài)與小數(shù)據(jù)驗證當(dāng)你的程序結(jié)果不對或者運(yùn)行超時時不要盲目盯著代碼看。小數(shù)據(jù)驗證自己設(shè)計幾個小的、手算能知道答案的測試用例。比如“方格分割”可以試試2x2的網(wǎng)格答案應(yīng)該是多少。用你的程序跑看結(jié)果是否匹配。輸出中間狀態(tài)在DFS或DP的關(guān)鍵步驟打印出當(dāng)前的選擇、狀態(tài)值。例如在“磁磚樣式”DFS中每放置一塊磚可以打印出當(dāng)前的grid看看鋪設(shè)邏輯是否符合預(yù)期。使用斷言assert在代碼中你認(rèn)為不變的條件處加入assert語句。例如在“對局匹配”分組時可以assert((vec[i].first - vec[i-1].first) % K 0)。這能幫你快速定位邏輯錯誤。對比暴力解對于小規(guī)模數(shù)據(jù)N8寫一個最樸素的、正確性顯而易見的暴力枚舉程序可能很慢用它來驗證你的優(yōu)化算法DP/搜索的結(jié)果。這是驗證算法正確性的黃金標(biāo)準(zhǔn)。6.5 賽場時間分配與代碼策略回顧這三道題它們分別代表了三種不同的題型和難度?！胺礁穹指睢笨嫉氖墙：退阉骷糁Α按糯u樣式”是更復(fù)雜的搜索與去重“對局匹配”則是動態(tài)規(guī)劃和問題轉(zhuǎn)化。在真實(shí)的賽場上合理的策略是快速通讀所有題目對每道題的難度、類型、可能耗時有個大致估計。先解決思路最清晰的。比如“對局匹配”一旦想到分組和不相鄰DP代碼實(shí)現(xiàn)相對直接調(diào)試也快。這種題目應(yīng)該優(yōu)先拿下。對于“方格分割”這類題如果短時間內(nèi)無法抽象出正確的模型不要死磕。先寫一個暴力搜索比如枚舉所有分割線再檢查獲取部分分?jǐn)?shù)N小的時候可能能過。標(biāo)記一下等做完其他題再回來深入思考?！按糯u樣式”屬于代碼實(shí)現(xiàn)細(xì)節(jié)多、容易出錯的題。如果時間緊張優(yōu)先保證正確性而不是追求最優(yōu)解。先實(shí)現(xiàn)一個基礎(chǔ)的DFS不帶高效剪枝和去重確保邏輯正確能過小數(shù)據(jù)。如果還有時間再逐步加入哈希去重、更高效的檢查等優(yōu)化。最后保持好的編碼習(xí)慣變量名清晰關(guān)鍵步驟寫注釋重復(fù)邏輯寫成函數(shù)。這不僅能減少錯誤在調(diào)試時也能節(jié)省大量時間。畢竟在高度緊張的比賽環(huán)境中清晰可讀的代碼是你最可靠的盟友。