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