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