1. 國(guó)賽沖刺從“臨時(shí)抱佛腳”到有效復(fù)盤距離藍(lán)橋杯國(guó)賽的日子越來(lái)越近很多同學(xué)可能和我當(dāng)年一樣陷入了“知識(shí)好像都會(huì)但真題一做就懵”的狀態(tài)。這時(shí)候漫無(wú)目的地刷題或者焦慮地翻看教材效果往往不佳。真正高效的“抱佛腳”應(yīng)該是針對(duì)性的、有策略的復(fù)盤。今天我就以第十一屆藍(lán)橋杯軟件類國(guó)賽B組的部分真題為例和大家一起做一次深度的“考后復(fù)盤”。這不僅僅是講幾道題怎么做更重要的是拆解當(dāng)時(shí)考場(chǎng)上的解題思路、容易掉入的陷阱以及如何從一道題延伸到一類題的通用解法。無(wú)論你是即將參賽還是在為未來(lái)的編程競(jìng)賽做準(zhǔn)備這種“以戰(zhàn)代練”的復(fù)盤方式都能幫你快速抓住重點(diǎn)提升臨場(chǎng)應(yīng)變能力。我們常說(shuō)“不要只看答案要看過(guò)程”但在時(shí)間緊迫的備賽階段如何最高效地“看過(guò)程”呢我的經(jīng)驗(yàn)是聚焦于那些“差一點(diǎn)就能做出來(lái)”或者“思路完全跑偏”的題目。對(duì)于已經(jīng)熟練掌握的題型快速過(guò)一遍確保無(wú)誤即可而對(duì)于那些讓你感到棘手、看了答案才恍然大悟的題則需要投入80%的精力去剖析。本次選擇的幾道題在數(shù)據(jù)結(jié)構(gòu)應(yīng)用、數(shù)學(xué)思維和動(dòng)態(tài)規(guī)劃優(yōu)化方面都非常有代表性涵蓋了國(guó)賽B組中上難度題目的典型特征。通過(guò)拆解它們我們不僅能補(bǔ)上知識(shí)漏洞更能訓(xùn)練一種“解題直覺(jué)”——在時(shí)間壓力下快速判斷題目類型并選取最合適的策略。2. 真題拆解一矩陣計(jì)數(shù)中的組合數(shù)學(xué)思維這道題通常描述為一個(gè)N x M的矩陣每個(gè)格子可以填0或1但要求任意一個(gè)2x2的子矩陣中1的個(gè)數(shù)為偶數(shù)個(gè)比如0個(gè)、2個(gè)或4個(gè)。問(wèn)滿足條件的矩陣總共有多少種。初看此題很多同學(xué)會(huì)下意識(shí)地想用DFS深度優(yōu)先搜索去枚舉所有矩陣然后檢查每個(gè)2x2子矩陣。但稍微計(jì)算一下就會(huì)發(fā)現(xiàn)即使N和M只有10總狀態(tài)數(shù)也高達(dá)2^(100)這是一個(gè)天文數(shù)字暴力枚舉絕對(duì)行不通。2.1 核心思路轉(zhuǎn)化從全局約束到行間遞推這道題的精妙之處在于它將一個(gè)二維的、全局性的約束條件轉(zhuǎn)化為了行與行之間的局部遞推關(guān)系。我們不妨這樣思考首先確定第一行。第一行可以任意填寫0或1沒(méi)有任何來(lái)自“上方”的2x2子矩陣約束。假設(shè)矩陣寬度為M那么第一行有 2^M 種可能。關(guān)鍵來(lái)了當(dāng)?shù)谝恍写_定后第二行該如何填寫考慮矩陣前兩行形成的若干個(gè)2x2子矩陣。對(duì)于第j列1 ≤ j ≤ M-1由第一行的第j、j1格和第二行的第j、j1格組成的2x2子矩陣其1的個(gè)數(shù)必須為偶數(shù)。設(shè)第一行的第j和第j1格的值分別為a_j和a_{j1}0或1設(shè)第二行對(duì)應(yīng)格子的值為b_j和b_{j1}。那么約束條件為(a_j a_{j1} b_j b_{j1}) % 2 0。這個(gè)等式可以變形(b_j b_{j1}) % 2 (a_j a_{j1}) % 2。注意等式右邊由已經(jīng)確定的第一行決定是一個(gè)已知的常數(shù)0或1。這意味著對(duì)于第二行任意相鄰兩個(gè)格子b_j和b_{j1}的和的奇偶性被固定了這實(shí)際上構(gòu)成了一組關(guān)于第二行元素的約束方程。2.2 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)基于上面的分析我們可以用狀態(tài)壓縮DP來(lái)求解。定義dp[i][state]表示處理到第i行且第i行的狀態(tài)為state一個(gè)M位的二進(jìn)制數(shù)1表示填10表示填0時(shí)滿足前i行所有2x2子矩陣約束的方案數(shù)。狀態(tài)轉(zhuǎn)移的核心是行間兼容性檢查。對(duì)于第i-1行的狀態(tài)prev_state和第i行的狀態(tài)curr_state我們需要檢查它們組成的每一個(gè)2x2子矩陣是否滿足1的個(gè)數(shù)為偶數(shù)。具體來(lái)說(shuō)對(duì)于所有列j (0 ≤ j M-1)檢查bitCount(prev_statej 3) bitCount(curr_statej 3)是否為偶數(shù)。 其中(prev_statej 3)提取了第i-1行第j和j1位的二進(jìn)制值00, 01, 10, 11bitCount是計(jì)算其中1的個(gè)數(shù)。初始化dp[1][state] 1對(duì)于所有可能的state即2^M種因?yàn)榈谝恍腥我狻?最終答案sum(dp[N][state])對(duì)所有的state求和。注意這里有一個(gè)巨大的優(yōu)化點(diǎn)和易錯(cuò)點(diǎn)。M可能達(dá)到10那么狀態(tài)數(shù)就是1024N也可能較大直接兩重循環(huán)遍歷prev_state和curr_state1024 * 1024再乘以N和M在時(shí)間上可能勉強(qiáng)過(guò)關(guān)但并非最優(yōu)。更常見(jiàn)的優(yōu)化是預(yù)處理兼容關(guān)系。我們可以預(yù)先計(jì)算出對(duì)于每一個(gè)狀態(tài)prev_state有哪些curr_state是與之兼容的即滿足所有2x2約束。這樣在DP轉(zhuǎn)移時(shí)只需要遍歷兼容的下一行狀態(tài)可以大幅減少計(jì)算量。在考場(chǎng)上想到用DP是第一步能想到預(yù)處理兼容性則是區(qū)分代碼能否在規(guī)定時(shí)間和內(nèi)存內(nèi)運(yùn)行通過(guò)的關(guān)鍵。2.3 從特例到通解思維模式的建立這道題教會(huì)我們一種非常重要的解題模式將二維矩陣的全局相鄰約束轉(zhuǎn)化為行或列之間的線性遞推關(guān)系。一旦建立了這種遞推無(wú)論是用狀態(tài)壓縮DP還是用更進(jìn)一步的矩陣快速冪如果N特別大問(wèn)題就從一個(gè)無(wú)從下手的組合計(jì)數(shù)變成了一個(gè)有清晰步驟的算法問(wèn)題。遇到類似的“棋盤填充”或“矩陣計(jì)數(shù)”問(wèn)題首先應(yīng)該嘗試尋找這種行/列之間的局部決定性關(guān)系。3. 真題拆解二本質(zhì)上升序列的動(dòng)態(tài)規(guī)劃與去重這是一道經(jīng)典的字符串問(wèn)題通常描述為給定一個(gè)字符串可能由小寫字母組成需要找出其所有本質(zhì)不同的上升子序列的數(shù)量。這里“上升”指的是子序列中每個(gè)字符的ASCII碼嚴(yán)格遞增即后一個(gè)字符大于前一個(gè)字符。“本質(zhì)不同”指的是即使子序列在原串中的下標(biāo)選擇不同但只要得到的字符串相同就視為同一個(gè)。例如字符串 “abc”其本質(zhì)不同的上升子序列有”a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”共7個(gè)。注意 “aa” 這樣的序列因?yàn)樽址粐?yán)格遞增所以不被計(jì)入。3.1 錯(cuò)誤思路警示直接DFS枚舉的陷阱最直觀的想法是用DFS回溯枚舉所有可能的子序列用一個(gè)Set來(lái)存儲(chǔ)結(jié)果字符串以實(shí)現(xiàn)去重。這種方法對(duì)于長(zhǎng)度非常短比如小于15的字符串或許可行但藍(lán)橋杯國(guó)賽的數(shù)據(jù)規(guī)模必然會(huì)讓這種指數(shù)級(jí)復(fù)雜度的算法超時(shí)。我們必須尋找多項(xiàng)式時(shí)間的解法。3.2 動(dòng)態(tài)規(guī)劃定義與狀態(tài)轉(zhuǎn)移正確的解法是動(dòng)態(tài)規(guī)劃。定義dp[i]表示以字符串中第i個(gè)字符s[i]作為結(jié)尾的本質(zhì)不同的上升子序列的個(gè)數(shù)。注意這里“結(jié)尾”是必須包含s[i]。 那么如何計(jì)算dp[i]呢 對(duì)于一個(gè)上升子序列它的最后一個(gè)字符是s[i]。那么它的前一個(gè)字符可以是任何在i之前且字符值小于s[i]的字符s[j] (j i 且 s[j] s[i])。所有以s[j]結(jié)尾的上升子序列后面加上s[i]就構(gòu)成了新的以s[i]結(jié)尾的上升子序列。 因此一個(gè)初步的轉(zhuǎn)移方程是dp[i] 1 sum(dp[j])對(duì)于所有滿足j i 且 s[j] s[i]的j。 這里的1代表子序列只包含s[i]本身的情況。3.3 核心難點(diǎn)如何去重上述轉(zhuǎn)移方程有一個(gè)致命問(wèn)題重復(fù)計(jì)數(shù)?？紤]字符串 “abac”。計(jì)算dp[3](對(duì)應(yīng)字符 ‘c’)。j0: s[0]’a’ ‘c’dp[0]代表以’a’結(jié)尾的序列比如 “a”。加上’c’后得到 “ac”。j1: s[1]’b’ ‘c’dp[1]代表以’b’結(jié)尾的序列比如 “b”, “ab”。加上’c’后得到 “bc”, “abc”。j2: s[2]’a’ ‘c’dp[2]代表以’a’結(jié)尾的序列。注意這里又出現(xiàn)了以’a’結(jié)尾的序列它會(huì)包括 “a”和j0重復(fù)以及可能由更早的字符與這個(gè)’a’形成的序列。如果簡(jiǎn)單相加序列 “ac” 會(huì)被計(jì)算兩次一次來(lái)自j0的’a’一次來(lái)自j2的’a’。問(wèn)題的根源在于相同的字符出現(xiàn)在不同位置但它們作為子序列的結(jié)尾所能形成的序列集合可能是相同的。為了解決去重我們需要改變DP的定義。正確定義dp[i]表示以字符’a’i 作為結(jié)尾的本質(zhì)不同的上升子序列的個(gè)數(shù)。這里我們不再以下標(biāo)為維度而是以字符本身為維度。因?yàn)樽址ǔＪ怯邢薜谋热?6個(gè)小寫字母。狀態(tài)轉(zhuǎn)移初始化所有dp[char]0。順序遍歷原字符串的每一個(gè)字符c。對(duì)于當(dāng)前字符c我們需要更新dp[c]。以c結(jié)尾的新子序列從哪里來(lái)首先是子序列”c”本身所以至少增加1。其次所有由小于c的字符x結(jié)尾的子序列后面加上c都能形成新的以c結(jié)尾的子序列。所以dp[c]需要加上所有dp[x](x c)。但是注意在遍歷過(guò)程中dp[c]可能已經(jīng)被之前的同一個(gè)字符c更新過(guò)。如果我們簡(jiǎn)單累加當(dāng)同一個(gè)字符再次出現(xiàn)時(shí)它會(huì)重復(fù)累加之前已經(jīng)計(jì)算過(guò)的、以小于c的字符結(jié)尾的序列。例如 “abac”遍歷到第二個(gè)’a’時(shí)如果直接dp[‘a(chǎn)’] 1 sum(dp[x] for x ‘a(chǎn)’)就會(huì)錯(cuò)誤地把dp[‘a(chǎn)’]從1變成2重復(fù)計(jì)算了單個(gè)’a’。正確的更新方法當(dāng)遍歷到字符c時(shí)我們不是累加而是重新計(jì)算dp[c]。因?yàn)橐詂結(jié)尾的所有本質(zhì)不同子序列只由當(dāng)前及之前出現(xiàn)過(guò)的、小于c的字符決定與之前出現(xiàn)的c本身無(wú)關(guān)相同的序列結(jié)尾字符其代表的集合是唯一的。所以new_count 1 sum(dp[x] for x c)然后令dp[c] new_count。最終答案就是所有dp[char]的總和。3.4 算法實(shí)現(xiàn)與復(fù)雜度分析s input().strip() # 假設(shè)字符集為小寫字母 dp [0] * 26 total 0 for ch in s: idx ord(ch) - ord(a) # 計(jì)算以當(dāng)前字符結(jié)尾的新增子序列數(shù) new_seq 1 # 字符本身 for i in range(idx): # 遍歷所有比當(dāng)前字符小的字符 new_seq dp[i] # 直接賦值而非累加這是去重的關(guān)鍵 dp[idx] new_seq result sum(dp) print(result)時(shí)間復(fù)雜度為 O(N * |Σ|)其中 |Σ| 是字符集大小這里是26對(duì)于字符串長(zhǎng)度N在10^5量級(jí)都完全可行。這道題的關(guān)鍵在于理解DP狀態(tài)以“字符值”而非“下標(biāo)”定義以及通過(guò)“重新賦值”而非“累加”來(lái)巧妙地去重。這是處理“本質(zhì)不同子序列”計(jì)數(shù)的一個(gè)非常經(jīng)典的技巧。4. 真題拆解三畫廊布局中的幾何與貪心這類問(wèn)題通常描述為一個(gè)長(zhǎng)廊一維線段的兩側(cè)墻上需要懸掛不同大小的畫作每幅畫有一個(gè)固定的懸掛點(diǎn)釘子的位置距離長(zhǎng)廊一端的位置以及畫的中心到其懸掛點(diǎn)的水平距離可以理解為畫的“半徑”或半寬。畫是矩形懸掛后其左右兩側(cè)會(huì)超出懸掛點(diǎn)。要求所有畫作不能相互重疊即使分屬兩側(cè)墻壁因?yàn)楫嬂扔袑挾纫部赡茉诳臻g上沖突這里通常是假設(shè)兩側(cè)的畫互不干擾只考慮同側(cè)。問(wèn)最多能懸掛多少幅畫。這實(shí)際上是一個(gè)**活動(dòng)選擇問(wèn)題Activity Selection Problem**的變種。我們可以將每一幅畫看作一個(gè)“活動(dòng)”這個(gè)活動(dòng)占據(jù)一段區(qū)間[懸掛點(diǎn) - 半寬 懸掛點(diǎn) 半寬]?；顒?dòng)的“開(kāi)始時(shí)間”就是區(qū)間左端點(diǎn)“結(jié)束時(shí)間”就是區(qū)間右端點(diǎn)。問(wèn)題轉(zhuǎn)化為在一條直線上對(duì)于一側(cè)的墻選擇盡可能多的不重疊的區(qū)間。4.1 標(biāo)準(zhǔn)貪心算法的直接應(yīng)用對(duì)于經(jīng)典的活動(dòng)選擇問(wèn)題貪心策略是每次選擇結(jié)束時(shí)間最早的活動(dòng)。證明思路是這樣可以為后續(xù)活動(dòng)留下盡可能多的空閑時(shí)間。 因此對(duì)于一側(cè)墻壁的畫作算法步驟如下計(jì)算每一幅畫占據(jù)的區(qū)間[l, r]其中l(wèi) position - half_width,r position half_width。將所有區(qū)間按照右端點(diǎn)r從小到大排序。初始化當(dāng)前已選區(qū)間的結(jié)束時(shí)間end -inf。遍歷排序后的區(qū)間列表如果當(dāng)前區(qū)間的左端點(diǎn)lend說(shuō)明它不與已選區(qū)間沖突則選擇它并更新end 當(dāng)前區(qū)間的右端點(diǎn) r。否則跳過(guò)該區(qū)間。這樣我們就能得到單側(cè)墻壁最多能懸掛的畫作數(shù)量。對(duì)于兩側(cè)墻壁由于通常假設(shè)畫作只在同側(cè)可能沖突兩側(cè)是獨(dú)立的所以只需要分別對(duì)兩側(cè)的畫作執(zhí)行上述貪心算法然后將結(jié)果相加即可。4.2 邊界情況與細(xì)節(jié)處理在實(shí)際編碼和思考中有幾個(gè)細(xì)節(jié)需要特別注意精度問(wèn)題畫作的懸掛點(diǎn)和半寬可能是浮點(diǎn)數(shù)。在比較l end時(shí)由于浮點(diǎn)數(shù)計(jì)算可能存在微小的精度誤差直接使用或可能不穩(wěn)定。更穩(wěn)健的做法是引入一個(gè)極小的容忍度eps如1e-9或者如果題目輸入是整數(shù)將所有長(zhǎng)度單位乘以2轉(zhuǎn)化為整數(shù)運(yùn)算可以徹底避免浮點(diǎn)數(shù)問(wèn)題。例如將半寬乘以2這樣區(qū)間端點(diǎn)都是整數(shù)比較起來(lái)更安全。區(qū)間包含關(guān)系考慮兩幅畫A和B如果A的區(qū)間完全包含了B的區(qū)間按照結(jié)束時(shí)間排序可能A的結(jié)束時(shí)間晚于B。但貪心算法會(huì)選擇結(jié)束早的B這依然是正確的因?yàn)檫x擇B之后A就因?yàn)闆_突被排除了但這并不影響最終的最大數(shù)量。貪心算法的正確性保證了這一點(diǎn)。兩側(cè)干擾的變種如果題目升級(jí)考慮畫廊的寬度兩側(cè)的畫作如果太“厚”突出墻面過(guò)多可能會(huì)在走廊中間空間發(fā)生碰撞。這就變成了一個(gè)二維的區(qū)間選擇問(wèn)題難度會(huì)大大增加通常需要更復(fù)雜的離散化或動(dòng)態(tài)規(guī)劃。但在藍(lán)橋杯B組國(guó)賽中大概率是考察對(duì)經(jīng)典貪心算法的識(shí)別和應(yīng)用能力即兩側(cè)獨(dú)立處理。4.3 貪心策略的證明與思維延伸為什么“選結(jié)束最早的”總是最優(yōu)我們可以用“替換法”來(lái)簡(jiǎn)單理解假設(shè)有一個(gè)最優(yōu)解其選擇的第一個(gè)活動(dòng)不是結(jié)束最早的。那么我們可以把這個(gè)最優(yōu)解中的第一個(gè)活動(dòng)替換成結(jié)束最早的那個(gè)活動(dòng)因?yàn)榻Y(jié)束最早的活動(dòng)與后面活動(dòng)的兼容性至少不會(huì)更差。替換后仍然是一個(gè)合法解且選擇的活動(dòng)數(shù)量沒(méi)有減少。因此總存在一個(gè)以“結(jié)束最早活動(dòng)”開(kāi)始的最優(yōu)解。這奠定了貪心選擇的基礎(chǔ)。這道題的價(jià)值在于它把生活中一個(gè)看似是布局規(guī)劃的問(wèn)題抽象成了一個(gè)非常經(jīng)典的算法模型。在競(jìng)賽中快速識(shí)別出題目背后的經(jīng)典模型活動(dòng)選擇、區(qū)間調(diào)度能節(jié)省大量的思考時(shí)間直接套用經(jīng)過(guò)驗(yàn)證的正確解法。拿到題目后先問(wèn)自己這是否可以轉(zhuǎn)化為區(qū)間不重疊問(wèn)題這是提高解題速度的關(guān)鍵一步。5. 真題拆解四補(bǔ)給網(wǎng)絡(luò)中的最小生成樹(shù)變體問(wèn)題場(chǎng)景常描述為有N個(gè)據(jù)點(diǎn)需要建立補(bǔ)給線路道路連接它們。不同據(jù)點(diǎn)間的直接建路成本不同。此外在一些據(jù)點(diǎn)可以建立“核心樞紐”核心樞紐之間可以以固定低成本甚至零成本互聯(lián)。目標(biāo)是讓所有據(jù)點(diǎn)直接或間接連通且總成本最低。這明顯是一個(gè)圖論中的最小生成樹(shù)MST問(wèn)題但加入了“核心樞紐”這個(gè)特殊點(diǎn)。如果沒(méi)有核心樞紐就是標(biāo)準(zhǔn)的求完全圖的最小生成樹(shù)Prim或Kruskal算法。核心樞紐的引入相當(dāng)于增加了幾個(gè)“超級(jí)節(jié)點(diǎn)”這些超級(jí)節(jié)點(diǎn)之間的連接成本極低。5.1 圖模型構(gòu)建與“超級(jí)源點(diǎn)”技巧最清晰的思路是重構(gòu)圖模型。我們可以引入一個(gè)虛擬的“超級(jí)源點(diǎn)”S。所有可以建設(shè)核心樞紐的據(jù)點(diǎn)都與這個(gè)超級(jí)源點(diǎn)S連接一條邊邊的權(quán)值就是在該據(jù)點(diǎn)建設(shè)核心樞紐的成本如果題目給出。如果核心樞紐之間互聯(lián)成本為0那么所有與S相連的節(jié)點(diǎn)彼此間就可以通過(guò)S以0成本連通。但更常見(jiàn)且巧妙的簡(jiǎn)化是將每個(gè)核心樞紐視為一個(gè)已有的連通分量。在Kruskal算法初始化時(shí)直接把所有核心樞紐據(jù)點(diǎn)放入同一個(gè)并查集集合中即讓它們的根節(jié)點(diǎn)相同。因?yàn)楹诵臉屑~之間被視為已經(jīng)以0成本連通了。5.2 基于Kruskal算法的解決方案具體步驟如下讀入所有據(jù)點(diǎn)的坐標(biāo)計(jì)算兩兩之間的歐幾里得距離或給定的成本作為邊的權(quán)值。這樣我們得到了一個(gè)包含N*(N-1)/2條邊的完全圖邊集E。初始化并查集每個(gè)據(jù)點(diǎn)自成一體。關(guān)鍵步驟將所有被選為核心樞紐的據(jù)點(diǎn)在并查集中進(jìn)行合并。例如假設(shè)據(jù)點(diǎn)1, 3, 5是核心樞紐那么執(zhí)行union(1,3),union(1,5)。這之后據(jù)點(diǎn)1、3、5就屬于同一個(gè)連通分量了相當(dāng)于它們之間已經(jīng)建立了0成本的連接。將邊集E按照權(quán)值從小到大排序。遍歷排序后的邊集。對(duì)于每條邊(u, v, w)如果find(u)!find(v)說(shuō)明u和v不在同一個(gè)連通分量中連接它們不會(huì)形成環(huán)。將這條邊加入最小生成樹(shù)總成本total_cost w并在并查集中執(zhí)行union(u, v)。當(dāng)并查集中只剩下一個(gè)連通分量時(shí)或者已選中N-1條邊時(shí)算法結(jié)束total_cost即為答案。5.3 算法正確性分析與復(fù)雜度為什么這樣做是正確的Kruskal算法的核心是每次選擇不會(huì)構(gòu)成環(huán)的最小權(quán)值邊。我們?cè)谒惴ㄩ_(kāi)始前通過(guò)并查集預(yù)先合并了核心樞紐節(jié)點(diǎn)這等價(jià)于在圖中預(yù)先添加了若干條權(quán)值為0的邊連接了所有核心樞紐。算法在執(zhí)行時(shí)會(huì)自動(dòng)忽略那些連接已連通的核心樞紐的邊因?yàn)閒ind(u) find(v)同時(shí)當(dāng)需要連接一個(gè)普通據(jù)點(diǎn)和核心樞紐群時(shí)它會(huì)選擇成本最小的那條邊。這完全符合題意核心樞紐間免費(fèi)互聯(lián)其他據(jù)點(diǎn)以最小成本接入這個(gè)網(wǎng)絡(luò)。時(shí)間復(fù)雜度主要在于邊集的排序O(M log M)其中 M N*(N-1)/2即 O(N^2 log N)。對(duì)于N在1000左右的規(guī)模這個(gè)復(fù)雜度是可以接受的。如果N更大例如10^4那么N^2條邊將無(wú)法存儲(chǔ)和排序此時(shí)就需要更高效的算法如基于Prim算法并利用幾何性質(zhì)進(jìn)行優(yōu)化但這通常超出了B組國(guó)賽的考察范圍。5.4 實(shí)戰(zhàn)心得與擴(kuò)展思考這道題是“最小生成樹(shù)”模板題的一個(gè)典型變種。它考察的是選手能否靈活運(yùn)用并理解MST算法的本質(zhì)而不是死記模板。在考場(chǎng)上遇到圖論連通問(wèn)題并且有“特殊節(jié)點(diǎn)”或“初始連通塊”時(shí)要立刻想到并查集的預(yù)處理技巧。一個(gè)常見(jiàn)的思維陷阱是試圖先為所有核心樞紐單獨(dú)建一個(gè)零成本的全連接子網(wǎng)然后再考慮其他點(diǎn)。這種思路容易導(dǎo)致代碼復(fù)雜。而使用并查集進(jìn)行“預(yù)連接”則優(yōu)雅地將特殊條件融入了標(biāo)準(zhǔn)Kruskal流程中代碼改動(dòng)極小僅多了幾行初始化合并操作。這提醒我們對(duì)經(jīng)典算法的深刻理解往往體現(xiàn)在用最小的改動(dòng)解決新的變體問(wèn)題。在復(fù)習(xí)時(shí)不僅要會(huì)寫Kruskal和Prim的板子更要理解其每一步操作的意義這樣才能在遇到諸如“有部分初始邊”、“有特殊連通要求”的變體時(shí)做到游刃有余。