1. 從“拼接”二字說起算法競(jìng)賽中的經(jīng)典題型與思維陷阱“拼接”這個(gè)詞聽起來平平無奇像是手工課上的剪紙游戲。但在算法競(jìng)賽尤其是像藍(lán)橋杯國(guó)賽這樣的頂級(jí)舞臺(tái)上它往往意味著一個(gè)需要深度思考、精巧建模的綜合性難題。第十屆藍(lán)橋杯國(guó)賽的這道“拼接”題正是這類問題的典型代表。它不會(huì)直接給你一堆碎片讓你去拼圖而是將“拼接”的概念抽象成數(shù)學(xué)模型考察選手對(duì)數(shù)據(jù)結(jié)構(gòu)、動(dòng)態(tài)規(guī)劃、圖論乃至貪心策略的綜合運(yùn)用能力。很多初次接觸此類題目的同學(xué)容易陷入一個(gè)誤區(qū)一看到“拼接”腦海里立刻浮現(xiàn)出具體的、有形狀的物體拼接場(chǎng)景然后試圖用復(fù)雜的幾何或搜索算法去模擬。這常常會(huì)走入死胡同因?yàn)楦?jìng)賽題目的核心在于“抽象”和“轉(zhuǎn)化”。這里的“拼接”更可能指的是將若干元素?cái)?shù)字、字符串、區(qū)間、狀態(tài)等以某種規(guī)則組合起來形成一個(gè)新的、符合特定條件的整體并求解最優(yōu)解如最小代價(jià)、最大價(jià)值、方案數(shù)等。這道題之所以能出現(xiàn)在國(guó)賽必然有其挑戰(zhàn)性。它可能涉及狀態(tài)定義、狀態(tài)轉(zhuǎn)移方程的巧妙設(shè)計(jì)以及對(duì)問題本質(zhì)的深刻洞察。解決它需要的不僅是熟練的編碼能力更是拆解問題、建立模型、優(yōu)化算法的系統(tǒng)性思維。接下來我將以一個(gè)算法競(jìng)賽老兵的視角帶大家深入這道題可能存在的幾種核心考察方向并手把手還原解題的完整思考鏈路與實(shí)現(xiàn)細(xì)節(jié)。2. 題型可能性分析與核心建模思路拆解面對(duì)一個(gè)只有標(biāo)題的題目我們首先要做的是進(jìn)行“題型考古”和“思路發(fā)散”?；谒{(lán)橋杯國(guó)賽歷年風(fēng)格和“拼接”這個(gè)關(guān)鍵詞我們可以推測(cè)出幾種最有可能的命題方向。理解這些方向本身就是一種重要的競(jìng)賽能力。2.1 方向一基于字符串或序列的最優(yōu)拼接問題這是最直觀的方向。題目可能給出若干個(gè)字符串或數(shù)字序列以及一個(gè)“拼接”的代價(jià)函數(shù)。例如將字符串A和B拼接在一起代價(jià)可能與A的后綴和B的前綴的匹配度如最長(zhǎng)公共部分有關(guān)目標(biāo)是以最小總代價(jià)將所有字符串拼接成一個(gè)長(zhǎng)串。核心建模這本質(zhì)上可以轉(zhuǎn)化為一個(gè)經(jīng)典的“旅行商問題TSP”變種或“最優(yōu)哈密頓路徑”問題。我們可以將每個(gè)字符串看作圖中的一個(gè)“節(jié)點(diǎn)”。如果我們將字符串i接在字符串j的后面那么它們之間邊的權(quán)重w[j][i]可以是j的后綴與i的前綴的重疊長(zhǎng)度求最大重疊時(shí)代價(jià)就是負(fù)的重疊長(zhǎng)度或者是需要額外添加的字符數(shù)最小添加字符數(shù)。問題轉(zhuǎn)化我們的目標(biāo)是找到一個(gè)遍歷所有節(jié)點(diǎn)恰好一次的路徑使得路徑的總權(quán)重最優(yōu)最大重疊或最小新增。對(duì)于小規(guī)模數(shù)據(jù)n 15可以直接使用狀態(tài)壓縮動(dòng)態(tài)規(guī)劃DP來解決。定義dp[state][i]表示當(dāng)前已經(jīng)拼接了state狀態(tài)集合中的字符串且最后一個(gè)拼接的是字符串i時(shí)的最優(yōu)值。然后進(jìn)行狀態(tài)轉(zhuǎn)移。注意這里有一個(gè)極易忽略的坑點(diǎn)——初始狀態(tài)。拼接需要一個(gè)起點(diǎn)這個(gè)起點(diǎn)可能是不需要前置代價(jià)的。通常我們需要初始化所有單個(gè)字符串作為起點(diǎn)的情況即dp[1i][i] 0如果代價(jià)是新增字符數(shù)則初始代價(jià)為該字符串長(zhǎng)度本身或0需根據(jù)題意確定。2.2 方向二區(qū)間覆蓋或線段拼接問題題目可能給出大量的小區(qū)間要求通過拼接可理解為合并、連接這些區(qū)間形成最少數(shù)量的、連續(xù)的大區(qū)間或者覆蓋一個(gè)指定范圍。核心建模這更偏向于貪心算法。經(jīng)典的“區(qū)間覆蓋”或“區(qū)間合并”問題。首先將所有區(qū)間按照左端點(diǎn)排序。然后嘗試進(jìn)行拼接維護(hù)當(dāng)前已經(jīng)覆蓋到的最右端點(diǎn)current_end。遍歷排序后的區(qū)間如果當(dāng)前區(qū)間的左端點(diǎn) current_end 1根據(jù)題意決定是否能無縫拼接還是允許有間隙那么就可以將其拼接進(jìn)來并更新current_end max(current_end, 當(dāng)前區(qū)間右端點(diǎn))。如果不能拼接則說明需要開始一個(gè)新的“大區(qū)間”。關(guān)鍵點(diǎn)辨析“拼接”在此處的具體規(guī)則至關(guān)重要。是必須端點(diǎn)重合才能拼還是只要區(qū)間有交集甚至只需相鄰就能拼這直接決定了貪心策略中判斷條件的、或關(guān)系需要從題目描述中仔細(xì)甄別。2.3 方向三數(shù)字或積木的拼接問題DP/DFS給出一些帶有數(shù)字的積木或卡片上面有數(shù)字或特定屬性。拼接規(guī)則可能是只有相鄰面數(shù)字滿足某種算術(shù)關(guān)系如相等、和為素?cái)?shù)、是倍數(shù)關(guān)系時(shí)才能拼接。求最長(zhǎng)能拼接的長(zhǎng)度或所有可能的拼接方案數(shù)。核心建模這類似于一個(gè)在特定約束條件下的“序列生成”問題?？梢杂蒙疃葍?yōu)先搜索DFS配合記憶化搜索Memoization來解決本質(zhì)上也是一種動(dòng)態(tài)規(guī)劃。定義dfs(last, state)表示上一個(gè)使用的積木是last當(dāng)前已使用的積木集合為state時(shí)能繼續(xù)獲得的最大長(zhǎng)度或方案數(shù)。轉(zhuǎn)移時(shí)遍歷所有未使用的積木i判斷l(xiāng)ast與i是否滿足拼接條件若滿足則進(jìn)行遞歸。優(yōu)化技巧當(dāng)積木數(shù)量較多n20時(shí)狀態(tài)壓縮可能空間不足。此時(shí)需要觀察題目是否具有特殊性質(zhì)。例如如果拼接只與最后一個(gè)積木的屬性有關(guān)或許可以按照屬性分類使用基于“最后一個(gè)積木類型”的DP將狀態(tài)數(shù)從2^n降低到n*kk為屬性種類。3. 以“字符串最小拼接代價(jià)”為例的深度解題實(shí)錄我們選取可能性最高的第一種方向——“字符串最小拼接代價(jià)”作為藍(lán)本進(jìn)行一場(chǎng)完整的解題推演。假設(shè)題目描述經(jīng)分析后確定為給定N個(gè)字符串S[i]每次可以將一個(gè)字符串A拼接在另一個(gè)字符串B后面前提是B的某個(gè)后綴與A的某個(gè)前綴相等。拼接時(shí)重疊部分只保留一份。求將所有字符串拼接成一個(gè)字符串時(shí)最終字符串的最小長(zhǎng)度。3.1 第一步問題抽象與圖論建模我們首先要將文字描述轉(zhuǎn)化為嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型。定義重疊度對(duì)于任意兩個(gè)字符串i和ji可以等于j但通常自身拼接無意義我們定義overlap[i][j]為將j拼在i后面時(shí)i的后綴與j的前綴的最大匹配長(zhǎng)度。注意這里求的是最大重疊因?yàn)橹丿B部分越長(zhǎng)最終字符串長(zhǎng)度就越短。計(jì)算重疊度如何高效計(jì)算overlap[i][j]一個(gè)樸素的方法是枚舉所有可能的匹配長(zhǎng)度len從min(len(S[i]), len(S[j]))向下枚舉判斷S[i][-len:]是否等于S[j][:len]。復(fù)雜度為O(N^2 * L^2)在N和L字符串平均長(zhǎng)度不大時(shí)可行。更優(yōu)的方法是使用字符串哈希Rabin-Karp可以在O(L)時(shí)間內(nèi)計(jì)算任意兩個(gè)字符串的最大重疊將總預(yù)處理復(fù)雜度降至O(N^2 * L)。構(gòu)建圖模型每個(gè)字符串是一個(gè)節(jié)點(diǎn)。從節(jié)點(diǎn)i到節(jié)點(diǎn)j有一條有向邊邊的權(quán)重cost[i][j] len(S[j]) - overlap[i][j]。這個(gè)權(quán)重的含義是當(dāng)把j拼在i后面時(shí)新增的字符串長(zhǎng)度。問題轉(zhuǎn)化我們的目標(biāo)是找到一條路徑這條路徑訪問每個(gè)節(jié)點(diǎn)恰好一次哈密頓路徑并且使得路徑上所有邊的權(quán)重之和即總新增長(zhǎng)度最小。最終字符串的總長(zhǎng)度 路徑起點(diǎn)的字符串長(zhǎng)度 路徑上所有邊的權(quán)重之和。由于起點(diǎn)字符串長(zhǎng)度是固定的最小化總長(zhǎng)度等價(jià)于最小化權(quán)重和。至此一個(gè)模糊的“拼接”問題被清晰轉(zhuǎn)化為了經(jīng)典的有向圖最小權(quán)哈密頓路徑問題。3.2 第二步算法選擇與狀態(tài)壓縮DP設(shè)計(jì)哈密頓路徑問題是NP-Hard的但對(duì)于N 20的量級(jí)藍(lán)橋杯國(guó)賽常見范圍我們可以使用狀態(tài)壓縮動(dòng)態(tài)規(guī)劃來求解。狀態(tài)定義設(shè)dp[state][i]表示當(dāng)前已經(jīng)訪問拼接了state所代表的集合中的字符串并且路徑的最后一個(gè)節(jié)點(diǎn)最后拼接的字符串是i時(shí)所產(chǎn)生的最小新增長(zhǎng)度即權(quán)重和。state是一個(gè)二進(jìn)制數(shù)其第k位為1表示字符串k已被訪問。狀態(tài)初始化對(duì)于每個(gè)字符串i它都可以作為路徑的起點(diǎn)。作為起點(diǎn)時(shí)沒有“新增長(zhǎng)度”但題目要求最終總長(zhǎng)起點(diǎn)字符串本身的長(zhǎng)度是必須計(jì)入的。我們可以這樣初始化dp[1i][i] 0。這里0表示從起點(diǎn)i開始目前新增長(zhǎng)度為0。最終答案需要加上起點(diǎn)字符串的長(zhǎng)度。狀態(tài)轉(zhuǎn)移方程對(duì)于當(dāng)前狀態(tài)dp[state][i]我們嘗試尋找下一個(gè)未訪問的節(jié)點(diǎn)j即state的第j位為0。新的狀態(tài)new_state state | (1j)。轉(zhuǎn)移方程為dp[new_state][j] min(dp[new_state][j], dp[state][i] cost[i][j])其中cost[i][j] len(S[j]) - overlap[i][j]。最終答案遍歷所有節(jié)點(diǎn)i作為終點(diǎn)計(jì)算total_len len(S[start]) dp[(1N)-1][i]。但這里有個(gè)問題我們不知道起點(diǎn)start是什么。一個(gè)巧妙的處理方式是在初始化時(shí)dp[1i][i]并不設(shè)為0而是設(shè)為len(S[i])表示以i為起點(diǎn)的當(dāng)前總長(zhǎng)度。那么轉(zhuǎn)移方程變?yōu)閐p[new_state][j] min(..., dp[state][i] len(S[j]) - overlap[i][j])。這樣dp[state][i]始終記錄的是構(gòu)成當(dāng)前狀態(tài)路徑的總長(zhǎng)度。最終答案就是min(dp[(1N)-1][i])其中i遍歷所有節(jié)點(diǎn)。關(guān)鍵細(xì)節(jié)在計(jì)算overlap[i][j]時(shí)必須注意ij的情況。通常一個(gè)字符串不能拼接在自己后面除非題目特別允許。我們可以將overlap[i][i]設(shè)為0或者在實(shí)際轉(zhuǎn)移時(shí)判斷i ! j。3.3 第三步代碼實(shí)現(xiàn)與關(guān)鍵優(yōu)化以下是基于上述DP思路的C代碼框架包含了預(yù)處理和DP核心。#include iostream #include vector #include string #include cstring #include algorithm using namespace std; const int INF 0x3f3f3f3f; // 計(jì)算字符串a(chǎn)的后綴與b的前綴的最大重疊長(zhǎng)度 int calcOverlap(const string a, const string b) { int max_len min(a.length(), b.length()); // 從可能的最大長(zhǎng)度開始嘗試 for(int len max_len; len 0; --len) { if(a.substr(a.length() - len) b.substr(0, len)) { return len; } } return 0; // 無重疊 } int main() { int N; cin N; vectorstring strs(N); for(int i 0; i N; i) { cin strs[i]; } // 1. 預(yù)處理overlap和cost矩陣 vectorvectorint cost(N, vectorint(N, 0)); for(int i 0; i N; i) { for(int j 0; j N; j) { if(i j) { cost[i][j] strs[i].length(); // 自己接自己相當(dāng)于新增整個(gè)串長(zhǎng)度通常不會(huì)用到 } else { int ol calcOverlap(strs[i], strs[j]); cost[i][j] strs[j].length() - ol; } } } // 2. 狀態(tài)壓縮DP int full_state (1 N) - 1; vectorvectorint dp(1 N, vectorint(N, INF)); // 初始化每個(gè)字符串作為起點(diǎn) for(int i 0; i N; i) { dp[1 i][i] strs[i].length(); // 記錄總長(zhǎng)度 } // 狀態(tài)轉(zhuǎn)移 for(int state 1; state full_state; state) { for(int i 0; i N; i) { if(dp[state][i] INF) continue; // 當(dāng)前狀態(tài)不可達(dá) if(!(state (1 i))) continue; // i不在狀態(tài)中理論上不會(huì)發(fā)生 // 嘗試將j拼接在i后面 for(int j 0; j N; j) { if(state (1 j)) continue; // j已經(jīng)在路徑中 int new_state state | (1 j); dp[new_state][j] min(dp[new_state][j], dp[state][i] cost[i][j]); } } } // 3. 尋找答案 int ans INF; for(int i 0; i N; i) { ans min(ans, dp[full_state][i]); } cout ans endl; return 0; }復(fù)雜度分析預(yù)處理overlap的復(fù)雜度為O(N^2 * L^2)DP部分的復(fù)雜度為O(2^N * N^2)。當(dāng)N20時(shí)2^N ≈ 100萬N^2400總運(yùn)算量在4億左右在C的競(jìng)賽環(huán)境中通常處于時(shí)間限制的臨界點(diǎn)但經(jīng)過優(yōu)化如使用哈希預(yù)處理overlap通?？梢訟C。4. 進(jìn)階討論性能優(yōu)化與特殊邊界處理上面的解法是標(biāo)準(zhǔn)解法但在競(jìng)賽中我們還需要考慮優(yōu)化和邊界情況這是區(qū)分普通選手和高水平選手的關(guān)鍵。4.1 優(yōu)化一字符串去重與包含關(guān)系處理在實(shí)際輸入中可能存在某個(gè)字符串是另一個(gè)字符串的子串的情況。例如字符串集合中有“abc”和“abcd”。在最優(yōu)拼接中“abc”很可能沒有存在的必要因?yàn)槭褂谩癮bcd”完全可以覆蓋它。因此一個(gè)重要的預(yù)處理步驟是去除被其他字符串包含的字符串。這可以在讀入數(shù)據(jù)后通過雙重循環(huán)比較來實(shí)現(xiàn)將完全是其他字符串子串的字符串標(biāo)記刪除。這能有效減少問題規(guī)模N。踩坑點(diǎn)去除子串時(shí)需要謹(jǐn)慎。如果題目要求必須使用所有字符串則不能去除。只有當(dāng)題目目標(biāo)是形成最短的包含所有字符串信息的超級(jí)字符串時(shí)如本題去除子串才是安全的。務(wù)必根據(jù)題意判斷。4.2 優(yōu)化二使用字符串哈希加速Overlap計(jì)算在計(jì)算overlap[i][j]時(shí)我們使用了substr方法這會(huì)產(chǎn)生子串拷貝效率較低。使用字符串哈希如Rabin-Karp哈希可以在O(1)時(shí)間內(nèi)判斷任意兩個(gè)子串是否相等。具體做法為每個(gè)字符串預(yù)處理其前綴哈希數(shù)組。要判斷S[i]的長(zhǎng)度為len的后綴是否等于S[j]的長(zhǎng)度為len的前綴只需比較S[i]的后綴哈希值和S[j]的前綴哈希值是否相等。這樣可以將計(jì)算所有overlap[i][j]的復(fù)雜度從O(N^2 * L^2)降低到O(N^2 * L)。4.3 邊界情況與測(cè)試用例設(shè)計(jì)自己設(shè)計(jì)測(cè)試用例是驗(yàn)證程序魯棒性的好習(xí)慣單字符串輸入N1程序應(yīng)能正確輸出該字符串的長(zhǎng)度。無重疊所有字符串彼此間無任何重疊部分。此時(shí)最優(yōu)拼接就是任意順序連接所有字符串總長(zhǎng)度為所有字符串長(zhǎng)度之和。你的DP結(jié)果應(yīng)該等于這個(gè)和。完全包含如[“abc”, “abcd”, “bc”]。預(yù)處理后應(yīng)能去除“abc”和“bc”最終答案應(yīng)為“abcd”的長(zhǎng)度4。循環(huán)重疊如[“abc”, “bcd”, “cde”]可以拼接成“abcde”總長(zhǎng)5。你的DP需要能找到這條鏈。重復(fù)字符串如果題目允許使用重復(fù)字符串通常不允許需要特殊處理。一般題目會(huì)說明所有字符串兩兩不同。4.4 內(nèi)存與時(shí)間優(yōu)化技巧對(duì)于N20dp[120][20]的內(nèi)存大約是2^20 * 20 * 4 bytes ≈ 80MB這在競(jìng)賽規(guī)定的256MB或512MB內(nèi)存限制下是可行的。如果N更大如22內(nèi)存可能吃緊。此時(shí)可以采用滾動(dòng)數(shù)組優(yōu)化因?yàn)闋顟B(tài)轉(zhuǎn)移只從較小的state轉(zhuǎn)移到較大的new_state但實(shí)現(xiàn)起來稍復(fù)雜。另一種思路是使用Meet-in-the-Middle折半搜索技術(shù)。將字符串集分成兩半分別計(jì)算每半部分所有可能的拼接順序和結(jié)果最終字符串及其長(zhǎng)度然后嘗試將兩半的結(jié)果拼接起來。這可以將指數(shù)復(fù)雜度從O(2^N)降低到O(2^(N/2))適用于N稍大的情況如N30但實(shí)現(xiàn)難度較高。5. 舉一反三如何應(yīng)對(duì)未知的具體題目雖然我們以“字符串拼接”為例進(jìn)行了深入分析但實(shí)際比賽中題目可能是我們討論過的其他方向甚至是它們的結(jié)合。面對(duì)一個(gè)未知的“拼接”題你應(yīng)該遵循以下思維流程精讀題目提取關(guān)鍵規(guī)則“拼接”的具體定義是什么對(duì)象是什么數(shù)字、字符串、區(qū)間、方塊拼接的許可條件是什么相鄰相等、和為素?cái)?shù)、區(qū)間相交優(yōu)化目標(biāo)是什么最短長(zhǎng)度、最少塊數(shù)、最大價(jià)值嘗試抽象與轉(zhuǎn)化立即思考能否將問題轉(zhuǎn)化為已知的經(jīng)典模型。涉及“所有元素用一次” - 想到排列、哈密頓路徑/回路。涉及“合并相鄰項(xiàng)” - 想到區(qū)間合并、石子合并類區(qū)間DP。涉及“選擇與順序” - 想到動(dòng)態(tài)規(guī)劃、貪心。對(duì)象間有依賴關(guān)系 - 想到圖論建模DAG上的DP、拓?fù)渑判颉Ｔu(píng)估數(shù)據(jù)范圍這是選擇算法的決定性因素。N 10或15暴力DFS/回溯可能可行。N 20或22狀態(tài)壓縮DP是首選。N 1000通常需要O(N^2)或O(N log N)的DP或貪心。N很大10^5通常需要O(N)或O(N log N)的貪心或線性DP。設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)根據(jù)模型和數(shù)據(jù)范圍選定主算法。同時(shí)思考需要預(yù)計(jì)算哪些信息如重疊度、相鄰關(guān)系矩陣。編寫代碼與調(diào)試先寫出核心邏輯框架用簡(jiǎn)單的樣例測(cè)試。然后構(gòu)造邊界用例進(jìn)行測(cè)試。優(yōu)化與再思考如果時(shí)間或空間超限回到步驟2和3思考是否有更優(yōu)的模型或算法。題目是否隱藏了特殊性質(zhì)如單調(diào)性、貪心選擇性可以簡(jiǎn)化問題這道“拼接”題就像算法競(jìng)賽中的一個(gè)微縮盆景它考察了你將生活概念抽象為數(shù)學(xué)模型的能力對(duì)經(jīng)典算法模型的熟悉度以及面對(duì)復(fù)雜問題時(shí)的系統(tǒng)化拆解思維。它不要求你寫出多么高深莫測(cè)的代碼但要求你的思考必須嚴(yán)密、清晰、直達(dá)本質(zhì)。這種能力正是在一次次這樣的題目訓(xùn)練中積累起來的。當(dāng)你再看到類似“拼接”、“覆蓋”、“組合”這樣的字眼時(shí)希望你的腦海中能立刻浮現(xiàn)出幾種可能的圖景并擁有了一套拆解它們的工具箱。這才是競(jìng)賽帶給我們的比獎(jiǎng)牌更持久的東西。