橋杯沖刺：真題解析心法與進(jìn)制轉(zhuǎn)換、交換瓶子、博弈問(wèn)題實(shí)戰(zhàn))
1. 賽前沖刺的“真題”價(jià)值不止是刷題距離藍(lán)橋杯比賽還有最后幾天很多同學(xué)的狀態(tài)可能和我當(dāng)年一樣題庫(kù)刷了不少但心里還是沒(méi)底總覺(jué)得還差點(diǎn)什么。這時(shí)候最常見(jiàn)的做法就是瘋狂找“真題”來(lái)刷試圖通過(guò)題海戰(zhàn)術(shù)抓住最后一根稻草。但以我參加過(guò)幾屆比賽和后來(lái)帶隊(duì)的經(jīng)驗(yàn)來(lái)看最后這個(gè)階段對(duì)“真題”的理解深度遠(yuǎn)比刷題的數(shù)量重要得多。很多人把“真題解析”簡(jiǎn)單地等同于“看答案”這是最大的誤區(qū)。真正的“真題解析”核心在于“解析”二字。它不是一個(gè)讓你背下答案的過(guò)程而是一個(gè)讓你徹底理解出題人思路、題目考察的本質(zhì)以及自己知識(shí)體系漏洞的絕佳機(jī)會(huì)。比如你看到一道關(guān)于“36進(jìn)制”轉(zhuǎn)換的題目如果只是記住了轉(zhuǎn)換的代碼模板那下次題目變成“62進(jìn)制”數(shù)字大小寫字母或者涉及進(jìn)制下的運(yùn)算時(shí)你可能還是會(huì)卡殼。但如果你通過(guò)這道題徹底理解了“任意進(jìn)制轉(zhuǎn)換”的核心是“除基取余逆序排列”以及字符與數(shù)值的映射關(guān)系那么這一類問(wèn)題對(duì)你來(lái)說(shuō)都將不再是障礙。再比如“交換瓶子”這類問(wèn)題它表面上是一個(gè)簡(jiǎn)單的模擬題但深層次可能考察的是“圖論中的環(huán)”或者“置換群”的思想。如果你只滿足于用兩層循環(huán)暴力交換AC了事那就錯(cuò)過(guò)了提升思維層次的關(guān)鍵一步。真題的價(jià)值就在于它是一面鏡子能照出你到底是“背題家”還是“解題家”。在沖刺階段我們應(yīng)該用真題來(lái)“查漏”和“悟道”而不是機(jī)械地“刷量”。2. 從“36進(jìn)制”問(wèn)題拆解任意進(jìn)制轉(zhuǎn)換的通用心法很多同學(xué)一看到“36進(jìn)制”就覺(jué)得是冷門考點(diǎn)心生畏懼。其實(shí)它只是進(jìn)制轉(zhuǎn)換這個(gè)經(jīng)典問(wèn)題的一個(gè)具體實(shí)例。我們完全可以通過(guò)它建立起解決所有進(jìn)制轉(zhuǎn)換問(wèn)題的通用框架。2.1 核心原理除基取余與乘基累加進(jìn)制轉(zhuǎn)換無(wú)非兩類其他進(jìn)制轉(zhuǎn)十進(jìn)制和十進(jìn)制轉(zhuǎn)其他進(jìn)制。1. 其他進(jìn)制轉(zhuǎn)十進(jìn)制乘基累加法這是最符合我們直覺(jué)的。對(duì)于一個(gè)R進(jìn)制的數(shù)S例如36進(jìn)制的“1AZ”我們從左到右從高位到低位處理每一位。核心公式是十進(jìn)制結(jié)果 十進(jìn)制結(jié)果 * R 當(dāng)前位對(duì)應(yīng)的十進(jìn)制值。初始化結(jié)果ans 0。遍歷字符串S的每個(gè)字符c將字符c轉(zhuǎn)換為對(duì)應(yīng)的數(shù)值v。對(duì)于36進(jìn)制0-9對(duì)應(yīng)0-9A-Z對(duì)應(yīng)10-35。執(zhí)行運(yùn)算ans ans * 36 v。遍歷結(jié)束ans即為十進(jìn)制結(jié)果。這個(gè)過(guò)程就像剝洋蔥每剝一層處理一位都把之前的結(jié)果放大R倍然后加上新一層的價(jià)值。2. 十進(jìn)制轉(zhuǎn)其他進(jìn)制除基取余法這是反向過(guò)程。給定一個(gè)十進(jìn)制數(shù)N要轉(zhuǎn)換為R進(jìn)制。初始化一個(gè)空列表用于存放結(jié)果。當(dāng)N 0時(shí)循環(huán)執(zhí)行計(jì)算N % R得到余數(shù)這個(gè)余數(shù)就是目標(biāo)進(jìn)制下的最低位數(shù)字。將余數(shù)轉(zhuǎn)換為對(duì)應(yīng)的字符如10轉(zhuǎn)為‘A’并存入結(jié)果列表。更新N N / R整除。循環(huán)結(jié)束后將結(jié)果列表逆序連接成字符串即為R進(jìn)制表示。注意這里最容易出錯(cuò)的就是“逆序”。因?yàn)槲覀兪窍鹊玫阶畹臀蛔詈蟮玫阶罡呶凰员仨毞崔D(zhuǎn)。很多同學(xué)在緊張時(shí)忘了這一步導(dǎo)致結(jié)果完全錯(cuò)誤。2.2 代碼實(shí)現(xiàn)與關(guān)鍵細(xì)節(jié)理解了原理代碼就水到渠成。這里以36進(jìn)制為例給出一個(gè)健壯的實(shí)現(xiàn)并附上關(guān)鍵注釋。def char_to_val(c: str) - int: 將字符轉(zhuǎn)換為對(duì)應(yīng)的數(shù)值支持0-9, A-Z if 0 c 9: return ord(c) - ord(0) elif A c Z: return ord(c) - ord(A) 10 # 如果題目擴(kuò)展到小寫字母可以再加一個(gè)分支 else: raise ValueError(fInvalid character for base-36: {c}) def val_to_char(v: int) - str: 將數(shù)值轉(zhuǎn)換為對(duì)應(yīng)的字符支持0-35 if 0 v 9: return chr(v ord(0)) elif 10 v 35: return chr(v - 10 ord(A)) else: raise ValueError(fInvalid value for base-36: {v}) def base36_to_decimal(s: str) - int: 36進(jìn)制字符串轉(zhuǎn)十進(jìn)制整數(shù) ans 0 for ch in s: v char_to_val(ch) ans ans * 36 v # 核心乘基累加 return ans def decimal_to_base36(num: int) - str: 十進(jìn)制整數(shù)轉(zhuǎn)36進(jìn)制字符串 if num 0: return 0 # 邊界情況處理 result_chars [] while num 0: remainder num % 36 result_chars.append(val_to_char(remainder)) num // 36 # 核心除基更新 # 結(jié)果列表是逆序的先得到的是低位需要反轉(zhuǎn) return .join(reversed(result_chars)) # 測(cè)試 test_str 1AZ dec_val base36_to_decimal(test_str) print(f36進(jìn)制 {test_str} 轉(zhuǎn)十進(jìn)制: {dec_val}) # 輸出: 1691 print(f十進(jìn)制 {dec_val} 轉(zhuǎn)回36進(jìn)制: {decimal_to_base36(dec_val)}) # 輸出: 1AZ實(shí)操心得與避坑指南邊界條件永遠(yuǎn)記得處理num0的情況。在decimal_to_base36函數(shù)中如果輸入是0while循環(huán)根本不會(huì)進(jìn)入會(huì)返回空字符串這顯然是錯(cuò)誤的。所以必須單獨(dú)判斷。大小寫問(wèn)題藍(lán)橋杯題目通常明確說(shuō)明使用大寫字母A-Z。但有些在線判題系統(tǒng)或自己練習(xí)時(shí)題目可能要求小寫。務(wù)必看清題目描述調(diào)整char_to_val和val_to_char函數(shù)中的字符范圍。一個(gè)常見(jiàn)的技巧是使用str.upper()或str.lower()在輸入時(shí)統(tǒng)一格式。負(fù)數(shù)處理標(biāo)準(zhǔn)的進(jìn)制轉(zhuǎn)換通常不考慮負(fù)數(shù)或者將負(fù)號(hào)單獨(dú)處理只對(duì)絕對(duì)值進(jìn)行轉(zhuǎn)換。如果題目涉及負(fù)數(shù)一定要先判斷正負(fù)記錄符號(hào)轉(zhuǎn)換其絕對(duì)值最后再加上符號(hào)。長(zhǎng)整數(shù)與溢出當(dāng)進(jìn)制較大或數(shù)字很長(zhǎng)時(shí)轉(zhuǎn)換后的十進(jìn)制數(shù)可能非常大超出普通int范圍在Python中沒(méi)問(wèn)題但在C/Java中需使用long long或BigInteger。這是題目常見(jiàn)的陷阱用來(lái)區(qū)分選手是否考慮了數(shù)據(jù)范圍。掌握了這個(gè)通用心法無(wú)論題目變成62進(jìn)制、16進(jìn)制還是任何奇葩進(jìn)制你都能從容應(yīng)對(duì)。核心就是那兩個(gè)函數(shù)char_to_val和val_to_char以及兩個(gè)核心操作乘基累加與除基取余逆序。3. “交換瓶子”的三種視角從暴力模擬到圖論洞察“交換瓶子”是一道非常經(jīng)典的藍(lán)橋杯真題題意大致是有N個(gè)瓶子編號(hào)1-N初始時(shí)亂序排列。每次操作可以交換任意兩個(gè)瓶子的位置。問(wèn)至少需要多少次交換才能使瓶子按順序排列即第i個(gè)位置放編號(hào)為i的瓶子。很多人第一反應(yīng)是暴力模擬從第一個(gè)位置開(kāi)始如果位置i上的瓶子編號(hào)不是i就找到編號(hào)為i的瓶子假設(shè)在位置j然后交換位置i和j的瓶子。這個(gè)算法是正確的時(shí)間復(fù)雜度是O(N2)。但是這道題的精妙之處在于它至少有三種不同層次的解法對(duì)應(yīng)著三種不同的思維深度。3.1 解法一直接選擇交換貪心模擬這是最直觀的解法上面已經(jīng)描述過(guò)。我們直接給出代碼和步驟分析。def min_swaps_direct(arr): 直接交換法每次將當(dāng)前位置i上的數(shù)換成本該在這個(gè)位置的數(shù)。 arr: 列表表示瓶子的初始排列假設(shè)編號(hào)從1開(kāi)始。 arr [0] arr # 為了方便讓下標(biāo)從1開(kāi)始arr[0]無(wú)用 n len(arr) - 1 swaps 0 for i in range(1, n 1): while arr[i] ! i: # 如果位置i上的瓶子不對(duì) # 找到本該在位置i的瓶子編號(hào)為i的瓶子現(xiàn)在在哪里 j arr[i] # 注意因?yàn)閍rr[i]的值就是另一個(gè)位置的編號(hào)這里是個(gè)技巧 # 交換位置i和位置j的瓶子 arr[i], arr[j] arr[j], arr[i] swaps 1 return swaps # 示例初始排列 [3, 1, 2] # 過(guò)程i1, arr[1]3 !1, 找到編號(hào)1在位置2交換arr[1]和arr[2] - [1,3,2], swaps1 # i1, arr[1]1 1, 跳過(guò) # i2, arr[2]3 !2, 找到編號(hào)2在位置3交換arr[2]和arr[3] - [1,2,3], swaps2 # 最終結(jié)果2次交換。為什么這個(gè)方法是正確的因?yàn)槊看谓粨Q都至少讓一個(gè)瓶子編號(hào)為i的瓶子回到了它的正確位置。并且這個(gè)瓶子回到正確位置后就不會(huì)再被移動(dòng)。所以最壞情況下每個(gè)位置最多被“糾正”一次雖然糾正它時(shí)可能移動(dòng)了其他瓶子總交換次數(shù)不會(huì)超過(guò)N-1次。這是一種貪心策略保證了局部最優(yōu)盡快讓當(dāng)前瓶子歸位能導(dǎo)向全局最優(yōu)總交換次數(shù)最少。3.2 解法二置換分解與環(huán)理論這是本題更優(yōu)雅、更高效的解法時(shí)間復(fù)雜度O(N)。它將排列看作一個(gè)置換并分解成若干個(gè)環(huán)。核心思想把排列arr看作一個(gè)映射i - arr[i]表示“位置i上的瓶子去了哪個(gè)位置”。更準(zhǔn)確地說(shuō)是“編號(hào)為i的瓶子目前所在的位置是arr[i]”不這里容易混淆。我們重新定義建立一個(gè)數(shù)組pos其中pos[bottle_id] current_position即編號(hào)為 bottle_id 的瓶子當(dāng)前所在的位置。但題目給的是arr[position] bottle_id。兩者是互逆的。為了用環(huán)的理論我們通常使用后者構(gòu)建圖對(duì)于每個(gè)位置i從i向arr[i]連一條有向邊。這樣會(huì)形成若干個(gè)有向環(huán)。例如排列[3, 1, 2]位置1期望放1號(hào)瓶放著3號(hào)瓶1 - 3位置2期望放2號(hào)瓶放著1號(hào)瓶2 - 1位置3期望放3號(hào)瓶放著2號(hào)瓶3 - 2連接起來(lái)是1-3-2-1這是一個(gè)長(zhǎng)度為3的環(huán)。關(guān)鍵結(jié)論對(duì)于一個(gè)長(zhǎng)度為k的環(huán)最少需要k-1次交換才能將環(huán)上所有瓶子歸位。為什么你可以想象環(huán)上的瓶子形成了一個(gè)“循環(huán)依賴”需要打破這個(gè)環(huán)。通過(guò)k-1次交換可以將環(huán)拆解成k個(gè)自環(huán)每個(gè)位置都指向自己。因此總的最少交換次數(shù) 所有環(huán)的 (環(huán)長(zhǎng) - 1) 之和N - 環(huán)的個(gè)數(shù)。def min_swaps_by_cycles(arr): 通過(guò)計(jì)算環(huán)的個(gè)數(shù)來(lái)求解最少交換次數(shù) n len(arr) visited [False] * n cycle_count 0 for i in range(n): if not visited[i]: # 開(kāi)始追蹤一個(gè)新的環(huán) j i while not visited[j]: visited[j] True j arr[j] - 1 # 因?yàn)閍rr中編號(hào)從1開(kāi)始轉(zhuǎn)換為0-based索引 cycle_count 1 # 最少交換次數(shù) 元素總數(shù) - 環(huán)的個(gè)數(shù) return n - cycle_count # 示例arr [3, 1, 2] # i0 (位置1), 未訪問(wèn)開(kāi)始追蹤: 0-2 (arr[0]-12), 2-1 (arr[2]-11), 1-0 (arr[1]-10)形成一個(gè)環(huán)。visited了0,2,1。cycle_count1。 # i1, 已訪問(wèn)跳過(guò)。 # i2, 已訪問(wèn)跳過(guò)。 # n3, cycle_count1, 結(jié)果3-12。這種解法的優(yōu)勢(shì)是思維層次高代碼簡(jiǎn)潔并且其原理可以推廣到許多其他關(guān)于排列和交換的問(wèn)題上。3.3 解法對(duì)比與思維升華特性直接交換法 (解法一)環(huán)分解法 (解法二)時(shí)間復(fù)雜度O(N2)O(N)空間復(fù)雜度O(1) (原地修改)O(N) (訪問(wèn)標(biāo)記數(shù)組)思維難度較低直觀模擬較高需要圖論/置換概念代碼復(fù)雜度中等有嵌套循環(huán)較低單層循環(huán)核心考察點(diǎn)貪心策略、模擬實(shí)現(xiàn)能力數(shù)學(xué)抽象、問(wèn)題轉(zhuǎn)化能力適用場(chǎng)景數(shù)據(jù)規(guī)模較小 (N ≤ 10?)數(shù)據(jù)規(guī)模任意通用性強(qiáng)在競(jìng)賽中如果N不大比如103級(jí)別兩種方法都能AC。但環(huán)分解法無(wú)疑是更優(yōu)解它展示了將具體操作問(wèn)題抽象為數(shù)學(xué)模型的能力。這提醒我們?cè)谒⒄骖}時(shí)不能滿足于AC。要多問(wèn)一句有沒(méi)有更優(yōu)的解法這道題的本質(zhì)是什么比如“交換瓶子”的本質(zhì)是計(jì)算排列中環(huán)的個(gè)數(shù)。這種洞察力才是通過(guò)刷真題真正要鍛煉的。4. 真題演練的深度步驟以“高僧斗法”類博弈問(wèn)題為例藍(lán)橋杯真題中不乏一些有趣的博弈問(wèn)題比如“高僧斗法”、“取石子游戲”等。這類題目往往不是考復(fù)雜的算法而是考邏輯推理和尋找必勝策略的能力。以“高僧斗法”Nim博弈的變種為例我們來(lái)拆解如何深度解析一道真題。題目通常簡(jiǎn)化描述為一行棋盤上放置了多個(gè)棋子代表高僧兩人輪流移動(dòng)任一棋子向右移動(dòng)任意格不能跨越其他棋子無(wú)法移動(dòng)者輸。問(wèn)先手是否必勝。4.1 第一步理解規(guī)則并轉(zhuǎn)化為模型首先必須摒棄“高僧”這個(gè)背景將其抽象為純粹的數(shù)學(xué)模型。我們發(fā)現(xiàn)棋子之間是獨(dú)立的嗎不是因?yàn)橐粋€(gè)棋子的移動(dòng)會(huì)改變它和后面棋子的間距。關(guān)鍵觀察將棋子兩兩配對(duì)從左到右第1和第2個(gè)一對(duì)第3和第4個(gè)一對(duì)...。對(duì)于每一對(duì)棋子它們之間的空格數(shù)就是這個(gè)“游戲”的一個(gè)“子局面”。為什么可以兩兩配對(duì)因?yàn)橐苿?dòng)一個(gè)棋子時(shí)它要么是配對(duì)中的左邊棋子增加間距要么是右邊棋子減少間距。這很像一個(gè)“取石子”游戲每一對(duì)的空格數(shù)就是一堆石子每次操作可以從一堆石子中取走任意正數(shù)顆移動(dòng)左僧或放入任意正數(shù)顆移動(dòng)右僧不放入是不允許的因?yàn)槠遄又荒芟蛴乙苿?dòng)。所以移動(dòng)左僧是增加間距增加石子移動(dòng)右僧是減少間距取走石子。這變成了一個(gè)不太標(biāo)準(zhǔn)的游戲。實(shí)際上這是經(jīng)典的階梯博弈Staircase Nim。更標(biāo)準(zhǔn)的解法是只考慮奇數(shù)位置從1開(kāi)始計(jì)數(shù)的棋子與它后面相鄰棋子之間的空格數(shù)。將這些空格數(shù)視為Nim游戲中的一堆堆石子。那么移動(dòng)一個(gè)棋子等價(jià)于從某一堆石子中取走任意正數(shù)量的石子。4.2 第二步推導(dǎo)必勝策略對(duì)于經(jīng)典的Nim游戲有一個(gè)著名的結(jié)論當(dāng)且僅當(dāng)所有堆石子數(shù)的異或XOR和為0時(shí)先手必?cái)》駝t先手必勝。那么對(duì)于這個(gè)“高僧斗法”問(wèn)題我們?nèi)〕鏊衅鏀?shù)索引的棋子第135...個(gè)與其后一個(gè)棋子之間的空格數(shù)組成一個(gè)數(shù)組a。計(jì)算xor_sum a[0] ^ a[1] ^ ... ^ a[k]。如果xor_sum 0先手必?cái)》駝t先手必勝。為什么這是理解的關(guān)鍵而不是死記結(jié)論 可以將棋盤看作一個(gè)階梯奇數(shù)位置的棋子是“關(guān)鍵棋子”。整個(gè)游戲的勝負(fù)態(tài)等價(jià)于這些關(guān)鍵棋子與其后棋子間距構(gòu)成的Nim游戲。其證明需要用到博弈論的“SG函數(shù)”和“局面等效”概念對(duì)于沖刺階段我們可以先接受這個(gè)結(jié)論但必須理解其操作含義如果異或和非零先手可以通過(guò)移動(dòng)某個(gè)關(guān)鍵棋子改變其與后一棋子的間距使得新的異或和變?yōu)?從而將必?cái)B(tài)丟給對(duì)手。4.3 第三步代碼實(shí)現(xiàn)與驗(yàn)證def can_win(positions): 判斷先手是否必勝。 positions: 一個(gè)列表表示棋子所在的格子編號(hào)已按升序排列。 例如: [1, 5, 9] 表示三個(gè)棋子分別在1,5,9格。 # 計(jì)算奇數(shù)索引棋子0-based索引中的偶數(shù)索引與其后一棋子的間距 xor_sum 0 for i in range(0, len(positions) - 1, 2): # 步長(zhǎng)為2取偶數(shù)索引 distance positions[i 1] - positions[i] - 1 # 兩者之間的空格數(shù) xor_sum ^ distance return xor_sum ! 0 # 測(cè)試 print(can_win([1, 5, 9])) # 棋子位置1,5,9。間距(5-1-1)3, (9-5-1)3? 注意我們只取奇數(shù)位(第1個(gè))的間距3。xor_sum3 !0先手必勝。 print(can_win([1, 5, 8, 10])) # 棋子位置1,5,8,10。奇數(shù)位間距(5-1-1)3, (10-8-1)1。xor_sum3^12 !0先手必勝。 print(can_win([1, 2])) # 棋子位置1,2。奇數(shù)位間距(2-1-1)0。xor_sum0先手必?cái) Ｉ疃冉馕龅膬r(jià)值體現(xiàn)如果只是背下了“異或和為0必?cái) 钡慕Y(jié)論題目稍微一變就可能出錯(cuò)。例如如果棋子不是放在格子上而是放在線上間隔不同或者移動(dòng)規(guī)則改變可以向左移動(dòng)。通過(guò)上面的三步分析我們不僅知道了結(jié)論更理解了如何建模將具體場(chǎng)景轉(zhuǎn)化為棋子間距。如何轉(zhuǎn)化識(shí)別出這是階梯博弈并提取關(guān)鍵間距奇數(shù)位。如何應(yīng)用通用定理套用Nim游戲的結(jié)論。如何驗(yàn)證通過(guò)小規(guī)模測(cè)試用例驗(yàn)證邏輯。這樣即使遇到新的變種題你也有了分析和推導(dǎo)的武器而不是只能祈禱考到原題。5. 沖刺階段的高效真題使用方法論最后幾天時(shí)間寶貴如何最大化真題的效用我總結(jié)了一個(gè)“四步真題深度利用法”親測(cè)有效。5.1 第一步限時(shí)模擬還原考場(chǎng)壓力找一套往年真題設(shè)定好比賽時(shí)長(zhǎng)通常是4小時(shí)完全模擬考場(chǎng)環(huán)境不查資料、不調(diào)試IDE只用記事本和命令行、不中途休息。這一步的目的是暴露問(wèn)題。你可能會(huì)發(fā)現(xiàn)時(shí)間分配不合理、讀題速度慢、代碼調(diào)試能力弱、簡(jiǎn)單題粗心出錯(cuò)等問(wèn)題。這些問(wèn)題只有在高壓下才會(huì)顯現(xiàn)平時(shí)松散刷題是發(fā)現(xiàn)不了的。5.2 第二步精細(xì)復(fù)盤分類整理錯(cuò)題模擬結(jié)束后不要只看分?jǐn)?shù)。對(duì)每一道題進(jìn)行精細(xì)復(fù)盤AC的題你的解法是否最優(yōu)時(shí)間復(fù)雜度、空間復(fù)雜度是否還有提升空間代碼是否足夠簡(jiǎn)潔清晰部分得分的題是哪個(gè)測(cè)試點(diǎn)沒(méi)過(guò)是邊界條件、特殊數(shù)據(jù)還是算法邏輯有漏洞嘗試構(gòu)造能觸發(fā)錯(cuò)誤的數(shù)據(jù)。不會(huì)做的題卡在哪里是完全沒(méi)思路還是思路錯(cuò)誤將這道題涉及的知識(shí)點(diǎn)標(biāo)記出來(lái)。建議建立一個(gè)錯(cuò)題本但不是抄題而是記錄題目核心模型如區(qū)間調(diào)度、最短路徑、動(dòng)態(tài)規(guī)劃、搜索。你的錯(cuò)誤思路和正確思路的對(duì)比。關(guān)鍵突破口哪一句話或哪個(gè)條件讓你豁然開(kāi)朗。易錯(cuò)點(diǎn)數(shù)據(jù)范圍、初始化、下標(biāo)從0還是1開(kāi)始等。5.3 第三步專題突破彌補(bǔ)知識(shí)短板根據(jù)錯(cuò)題本你會(huì)發(fā)現(xiàn)自己的薄弱環(huán)節(jié)。最后幾天不適合再系統(tǒng)學(xué)習(xí)新算法但可以進(jìn)行專題強(qiáng)化。例如如果動(dòng)態(tài)規(guī)劃DP總是丟分就集中刷3-5道經(jīng)典DP真題如01背包、最長(zhǎng)公共子序列、矩陣連乘等總結(jié)狀態(tài)定義和轉(zhuǎn)移方程的套路。如果圖論題總是超時(shí)就重點(diǎn)復(fù)習(xí)一下Dijkstra堆優(yōu)化、Floyd、并查集的模板代碼。5.4 第四步提煉模板構(gòu)建肌肉記憶對(duì)于高頻考點(diǎn)和常用算法準(zhǔn)備好自己的“代碼模板”。注意是自己的模板不是網(wǎng)上直接抄的。你要理解每一行代碼的作用并經(jīng)過(guò)多次敲打形成肌肉記憶。例如快速排序/歸并排序二分查找及其變種找第一個(gè)大于等于x的位置并查集路徑壓縮、按秩合并Dijkstra算法使用優(yōu)先隊(duì)列Floyd算法KMP字符串匹配快速冪算法在考場(chǎng)上遇到相關(guān)題目你可以像填空一樣快速將模板適配到具體問(wèn)題節(jié)省大量時(shí)間并減少低級(jí)錯(cuò)誤。最后幾天的心理建議停止刷新題尤其是難題。重心放在回顧錯(cuò)題、熟悉模板和調(diào)整心態(tài)上。保證睡眠飲食清淡。進(jìn)入考場(chǎng)后前10分鐘快速瀏覽所有題目按“易-中-難”做好時(shí)間規(guī)劃。通常有“簽到題”務(wù)必先拿下建立信心。遇到卡殼的題果斷標(biāo)記后跳過(guò)不要死磕。記住藍(lán)橋杯是比賽目標(biāo)是多得分而不是解決所有問(wèn)題。 藍(lán)橋杯沖刺：真題解析心法與進(jìn)制轉(zhuǎn)換、交換瓶子、博弈問(wèn)題實(shí)戰(zhàn)
1. 賽前沖刺的“真題”價(jià)值不止是刷題距離藍(lán)橋杯比賽還有最后幾天很多同學(xué)的狀態(tài)可能和我當(dāng)年一樣題庫(kù)刷了不少但心里還是沒(méi)底總覺(jué)得還差點(diǎn)什么。這時(shí)候最常見(jiàn)的做法就是瘋狂找“真題”來(lái)刷試圖通過(guò)題海戰(zhàn)術(shù)抓住最后一根稻草。但以我參加過(guò)幾屆比賽和后來(lái)帶隊(duì)的經(jīng)驗(yàn)來(lái)看最后這個(gè)階段對(duì)“真題”的理解深度遠(yuǎn)比刷題的數(shù)量重要得多。很多人把“真題解析”簡(jiǎn)單地等同于“看答案”這是最大的誤區(qū)。真正的“真題解析”核心在于“解析”二字。它不是一個(gè)讓你背下答案的過(guò)程而是一個(gè)讓你徹底理解出題人思路、題目考察的本質(zhì)以及自己知識(shí)體系漏洞的絕佳機(jī)會(huì)。比如你看到一道關(guān)于“36進(jìn)制”轉(zhuǎn)換的題目如果只是記住了轉(zhuǎn)換的代碼模板那下次題目變成“62進(jìn)制”數(shù)字大小寫字母或者涉及進(jìn)制下的運(yùn)算時(shí)你可能還是會(huì)卡殼。但如果你通過(guò)這道題徹底理解了“任意進(jìn)制轉(zhuǎn)換”的核心是“除基取余逆序排列”以及字符與數(shù)值的映射關(guān)系那么這一類問(wèn)題對(duì)你來(lái)說(shuō)都將不再是障礙。再比如“交換瓶子”這類問(wèn)題它表面上是一個(gè)簡(jiǎn)單的模擬題但深層次可能考察的是“圖論中的環(huán)”或者“置換群”的思想。如果你只滿足于用兩層循環(huán)暴力交換AC了事那就錯(cuò)過(guò)了提升思維層次的關(guān)鍵一步。真題的價(jià)值就在于它是一面鏡子能照出你到底是“背題家”還是“解題家”。在沖刺階段我們應(yīng)該用真題來(lái)“查漏”和“悟道”而不是機(jī)械地“刷量”。2. 從“36進(jìn)制”問(wèn)題拆解任意進(jìn)制轉(zhuǎn)換的通用心法很多同學(xué)一看到“36進(jìn)制”就覺(jué)得是冷門考點(diǎn)心生畏懼。其實(shí)它只是進(jìn)制轉(zhuǎn)換這個(gè)經(jīng)典問(wèn)題的一個(gè)具體實(shí)例。我們完全可以通過(guò)它建立起解決所有進(jìn)制轉(zhuǎn)換問(wèn)題的通用框架。2.1 核心原理除基取余與乘基累加進(jìn)制轉(zhuǎn)換無(wú)非兩類其他進(jìn)制轉(zhuǎn)十進(jìn)制和十進(jìn)制轉(zhuǎn)其他進(jìn)制。1. 其他進(jìn)制轉(zhuǎn)十進(jìn)制乘基累加法這是最符合我們直覺(jué)的。對(duì)于一個(gè)R進(jìn)制的數(shù)S例如36進(jìn)制的“1AZ”我們從左到右從高位到低位處理每一位。核心公式是十進(jìn)制結(jié)果 十進(jìn)制結(jié)果 * R 當(dāng)前位對(duì)應(yīng)的十進(jìn)制值。初始化結(jié)果ans 0。遍歷字符串S的每個(gè)字符c將字符c轉(zhuǎn)換為對(duì)應(yīng)的數(shù)值v。對(duì)于36進(jìn)制0-9對(duì)應(yīng)0-9A-Z對(duì)應(yīng)10-35。執(zhí)行運(yùn)算ans ans * 36 v。遍歷結(jié)束ans即為十進(jìn)制結(jié)果。這個(gè)過(guò)程就像剝洋蔥每剝一層處理一位都把之前的結(jié)果放大R倍然后加上新一層的價(jià)值。2. 十進(jìn)制轉(zhuǎn)其他進(jìn)制除基取余法這是反向過(guò)程。給定一個(gè)十進(jìn)制數(shù)N要轉(zhuǎn)換為R進(jìn)制。初始化一個(gè)空列表用于存放結(jié)果。當(dāng)N 0時(shí)循環(huán)執(zhí)行計(jì)算N % R得到余數(shù)這個(gè)余數(shù)就是目標(biāo)進(jìn)制下的最低位數(shù)字。將余數(shù)轉(zhuǎn)換為對(duì)應(yīng)的字符如10轉(zhuǎn)為‘A’并存入結(jié)果列表。更新N N / R整除。循環(huán)結(jié)束后將結(jié)果列表逆序連接成字符串即為R進(jìn)制表示。注意這里最容易出錯(cuò)的就是“逆序”。因?yàn)槲覀兪窍鹊玫阶畹臀蛔詈蟮玫阶罡呶凰员仨毞崔D(zhuǎn)。很多同學(xué)在緊張時(shí)忘了這一步導(dǎo)致結(jié)果完全錯(cuò)誤。2.2 代碼實(shí)現(xiàn)與關(guān)鍵細(xì)節(jié)理解了原理代碼就水到渠成。這里以36進(jìn)制為例給出一個(gè)健壯的實(shí)現(xiàn)并附上關(guān)鍵注釋。def char_to_val(c: str) - int: 將字符轉(zhuǎn)換為對(duì)應(yīng)的數(shù)值支持0-9, A-Z if 0 c 9: return ord(c) - ord(0) elif A c Z: return ord(c) - ord(A) 10 # 如果題目擴(kuò)展到小寫字母可以再加一個(gè)分支 else: raise ValueError(fInvalid character for base-36: {c}) def val_to_char(v: int) - str: 將數(shù)值轉(zhuǎn)換為對(duì)應(yīng)的字符支持0-35 if 0 v 9: return chr(v ord(0)) elif 10 v 35: return chr(v - 10 ord(A)) else: raise ValueError(fInvalid value for base-36: {v}) def base36_to_decimal(s: str) - int: 36進(jìn)制字符串轉(zhuǎn)十進(jìn)制整數(shù) ans 0 for ch in s: v char_to_val(ch) ans ans * 36 v # 核心乘基累加 return ans def decimal_to_base36(num: int) - str: 十進(jìn)制整數(shù)轉(zhuǎn)36進(jìn)制字符串 if num 0: return 0 # 邊界情況處理 result_chars [] while num 0: remainder num % 36 result_chars.append(val_to_char(remainder)) num // 36 # 核心除基更新 # 結(jié)果列表是逆序的先得到的是低位需要反轉(zhuǎn) return .join(reversed(result_chars)) # 測(cè)試 test_str 1AZ dec_val base36_to_decimal(test_str) print(f36進(jìn)制 {test_str} 轉(zhuǎn)十進(jìn)制: {dec_val}) # 輸出: 1691 print(f十進(jìn)制 {dec_val} 轉(zhuǎn)回36進(jìn)制: {decimal_to_base36(dec_val)}) # 輸出: 1AZ實(shí)操心得與避坑指南邊界條件永遠(yuǎn)記得處理num0的情況。在decimal_to_base36函數(shù)中如果輸入是0while循環(huán)根本不會(huì)進(jìn)入會(huì)返回空字符串這顯然是錯(cuò)誤的。所以必須單獨(dú)判斷。大小寫問(wèn)題藍(lán)橋杯題目通常明確說(shuō)明使用大寫字母A-Z。但有些在線判題系統(tǒng)或自己練習(xí)時(shí)題目可能要求小寫。務(wù)必看清題目描述調(diào)整char_to_val和val_to_char函數(shù)中的字符范圍。一個(gè)常見(jiàn)的技巧是使用str.upper()或str.lower()在輸入時(shí)統(tǒng)一格式。負(fù)數(shù)處理標(biāo)準(zhǔn)的進(jìn)制轉(zhuǎn)換通常不考慮負(fù)數(shù)或者將負(fù)號(hào)單獨(dú)處理只對(duì)絕對(duì)值進(jìn)行轉(zhuǎn)換。如果題目涉及負(fù)數(shù)一定要先判斷正負(fù)記錄符號(hào)轉(zhuǎn)換其絕對(duì)值最后再加上符號(hào)。長(zhǎng)整數(shù)與溢出當(dāng)進(jìn)制較大或數(shù)字很長(zhǎng)時(shí)轉(zhuǎn)換后的十進(jìn)制數(shù)可能非常大超出普通int范圍在Python中沒(méi)問(wèn)題但在C/Java中需使用long long或BigInteger。這是題目常見(jiàn)的陷阱用來(lái)區(qū)分選手是否考慮了數(shù)據(jù)范圍。掌握了這個(gè)通用心法無(wú)論題目變成62進(jìn)制、16進(jìn)制還是任何奇葩進(jìn)制你都能從容應(yīng)對(duì)。核心就是那兩個(gè)函數(shù)char_to_val和val_to_char以及兩個(gè)核心操作乘基累加與除基取余逆序。3. “交換瓶子”的三種視角從暴力模擬到圖論洞察“交換瓶子”是一道非常經(jīng)典的藍(lán)橋杯真題題意大致是有N個(gè)瓶子編號(hào)1-N初始時(shí)亂序排列。每次操作可以交換任意兩個(gè)瓶子的位置。問(wèn)至少需要多少次交換才能使瓶子按順序排列即第i個(gè)位置放編號(hào)為i的瓶子。很多人第一反應(yīng)是暴力模擬從第一個(gè)位置開(kāi)始如果位置i上的瓶子編號(hào)不是i就找到編號(hào)為i的瓶子假設(shè)在位置j然后交換位置i和j的瓶子。這個(gè)算法是正確的時(shí)間復(fù)雜度是O(N2)。但是這道題的精妙之處在于它至少有三種不同層次的解法對(duì)應(yīng)著三種不同的思維深度。3.1 解法一直接選擇交換貪心模擬這是最直觀的解法上面已經(jīng)描述過(guò)。我們直接給出代碼和步驟分析。def min_swaps_direct(arr): 直接交換法每次將當(dāng)前位置i上的數(shù)換成本該在這個(gè)位置的數(shù)。 arr: 列表表示瓶子的初始排列假設(shè)編號(hào)從1開(kāi)始。 arr [0] arr # 為了方便讓下標(biāo)從1開(kāi)始arr[0]無(wú)用 n len(arr) - 1 swaps 0 for i in range(1, n 1): while arr[i] ! i: # 如果位置i上的瓶子不對(duì) # 找到本該在位置i的瓶子編號(hào)為i的瓶子現(xiàn)在在哪里 j arr[i] # 注意因?yàn)閍rr[i]的值就是另一個(gè)位置的編號(hào)這里是個(gè)技巧 # 交換位置i和位置j的瓶子 arr[i], arr[j] arr[j], arr[i] swaps 1 return swaps # 示例初始排列 [3, 1, 2] # 過(guò)程i1, arr[1]3 !1, 找到編號(hào)1在位置2交換arr[1]和arr[2] - [1,3,2], swaps1 # i1, arr[1]1 1, 跳過(guò) # i2, arr[2]3 !2, 找到編號(hào)2在位置3交換arr[2]和arr[3] - [1,2,3], swaps2 # 最終結(jié)果2次交換。為什么這個(gè)方法是正確的因?yàn)槊看谓粨Q都至少讓一個(gè)瓶子編號(hào)為i的瓶子回到了它的正確位置。并且這個(gè)瓶子回到正確位置后就不會(huì)再被移動(dòng)。所以最壞情況下每個(gè)位置最多被“糾正”一次雖然糾正它時(shí)可能移動(dòng)了其他瓶子總交換次數(shù)不會(huì)超過(guò)N-1次。這是一種貪心策略保證了局部最優(yōu)盡快讓當(dāng)前瓶子歸位能導(dǎo)向全局最優(yōu)總交換次數(shù)最少。3.2 解法二置換分解與環(huán)理論這是本題更優(yōu)雅、更高效的解法時(shí)間復(fù)雜度O(N)。它將排列看作一個(gè)置換并分解成若干個(gè)環(huán)。核心思想把排列arr看作一個(gè)映射i - arr[i]表示“位置i上的瓶子去了哪個(gè)位置”。更準(zhǔn)確地說(shuō)是“編號(hào)為i的瓶子目前所在的位置是arr[i]”不這里容易混淆。我們重新定義建立一個(gè)數(shù)組pos其中pos[bottle_id] current_position即編號(hào)為 bottle_id 的瓶子當(dāng)前所在的位置。但題目給的是arr[position] bottle_id。兩者是互逆的。為了用環(huán)的理論我們通常使用后者構(gòu)建圖對(duì)于每個(gè)位置i從i向arr[i]連一條有向邊。這樣會(huì)形成若干個(gè)有向環(huán)。例如排列[3, 1, 2]位置1期望放1號(hào)瓶放著3號(hào)瓶1 - 3位置2期望放2號(hào)瓶放著1號(hào)瓶2 - 1位置3期望放3號(hào)瓶放著2號(hào)瓶3 - 2連接起來(lái)是1-3-2-1這是一個(gè)長(zhǎng)度為3的環(huán)。關(guān)鍵結(jié)論對(duì)于一個(gè)長(zhǎng)度為k的環(huán)最少需要k-1次交換才能將環(huán)上所有瓶子歸位。為什么你可以想象環(huán)上的瓶子形成了一個(gè)“循環(huán)依賴”需要打破這個(gè)環(huán)。通過(guò)k-1次交換可以將環(huán)拆解成k個(gè)自環(huán)每個(gè)位置都指向自己。因此總的最少交換次數(shù) 所有環(huán)的 (環(huán)長(zhǎng) - 1) 之和N - 環(huán)的個(gè)數(shù)。def min_swaps_by_cycles(arr): 通過(guò)計(jì)算環(huán)的個(gè)數(shù)來(lái)求解最少交換次數(shù) n len(arr) visited [False] * n cycle_count 0 for i in range(n): if not visited[i]: # 開(kāi)始追蹤一個(gè)新的環(huán) j i while not visited[j]: visited[j] True j arr[j] - 1 # 因?yàn)閍rr中編號(hào)從1開(kāi)始轉(zhuǎn)換為0-based索引 cycle_count 1 # 最少交換次數(shù) 元素總數(shù) - 環(huán)的個(gè)數(shù) return n - cycle_count # 示例arr [3, 1, 2] # i0 (位置1), 未訪問(wèn)開(kāi)始追蹤: 0-2 (arr[0]-12), 2-1 (arr[2]-11), 1-0 (arr[1]-10)形成一個(gè)環(huán)。visited了0,2,1。cycle_count1。 # i1, 已訪問(wèn)跳過(guò)。 # i2, 已訪問(wèn)跳過(guò)。 # n3, cycle_count1, 結(jié)果3-12。這種解法的優(yōu)勢(shì)是思維層次高代碼簡(jiǎn)潔并且其原理可以推廣到許多其他關(guān)于排列和交換的問(wèn)題上。3.3 解法對(duì)比與思維升華特性直接交換法 (解法一)環(huán)分解法 (解法二)時(shí)間復(fù)雜度O(N2)O(N)空間復(fù)雜度O(1) (原地修改)O(N) (訪問(wèn)標(biāo)記數(shù)組)思維難度較低直觀模擬較高需要圖論/置換概念代碼復(fù)雜度中等有嵌套循環(huán)較低單層循環(huán)核心考察點(diǎn)貪心策略、模擬實(shí)現(xiàn)能力數(shù)學(xué)抽象、問(wèn)題轉(zhuǎn)化能力適用場(chǎng)景數(shù)據(jù)規(guī)模較小 (N ≤ 10?)數(shù)據(jù)規(guī)模任意通用性強(qiáng)在競(jìng)賽中如果N不大比如103級(jí)別兩種方法都能AC。但環(huán)分解法無(wú)疑是更優(yōu)解它展示了將具體操作問(wèn)題抽象為數(shù)學(xué)模型的能力。這提醒我們?cè)谒⒄骖}時(shí)不能滿足于AC。要多問(wèn)一句有沒(méi)有更優(yōu)的解法這道題的本質(zhì)是什么比如“交換瓶子”的本質(zhì)是計(jì)算排列中環(huán)的個(gè)數(shù)。這種洞察力才是通過(guò)刷真題真正要鍛煉的。4. 真題演練的深度步驟以“高僧斗法”類博弈問(wèn)題為例藍(lán)橋杯真題中不乏一些有趣的博弈問(wèn)題比如“高僧斗法”、“取石子游戲”等。這類題目往往不是考復(fù)雜的算法而是考邏輯推理和尋找必勝策略的能力。以“高僧斗法”Nim博弈的變種為例我們來(lái)拆解如何深度解析一道真題。題目通常簡(jiǎn)化描述為一行棋盤上放置了多個(gè)棋子代表高僧兩人輪流移動(dòng)任一棋子向右移動(dòng)任意格不能跨越其他棋子無(wú)法移動(dòng)者輸。問(wèn)先手是否必勝。4.1 第一步理解規(guī)則并轉(zhuǎn)化為模型首先必須摒棄“高僧”這個(gè)背景將其抽象為純粹的數(shù)學(xué)模型。我們發(fā)現(xiàn)棋子之間是獨(dú)立的嗎不是因?yàn)橐粋€(gè)棋子的移動(dòng)會(huì)改變它和后面棋子的間距。關(guān)鍵觀察將棋子兩兩配對(duì)從左到右第1和第2個(gè)一對(duì)第3和第4個(gè)一對(duì)...。對(duì)于每一對(duì)棋子它們之間的空格數(shù)就是這個(gè)“游戲”的一個(gè)“子局面”。為什么可以兩兩配對(duì)因?yàn)橐苿?dòng)一個(gè)棋子時(shí)它要么是配對(duì)中的左邊棋子增加間距要么是右邊棋子減少間距。這很像一個(gè)“取石子”游戲每一對(duì)的空格數(shù)就是一堆石子每次操作可以從一堆石子中取走任意正數(shù)顆移動(dòng)左僧或放入任意正數(shù)顆移動(dòng)右僧不放入是不允許的因?yàn)槠遄又荒芟蛴乙苿?dòng)。所以移動(dòng)左僧是增加間距增加石子移動(dòng)右僧是減少間距取走石子。這變成了一個(gè)不太標(biāo)準(zhǔn)的游戲。實(shí)際上這是經(jīng)典的階梯博弈Staircase Nim。更標(biāo)準(zhǔn)的解法是只考慮奇數(shù)位置從1開(kāi)始計(jì)數(shù)的棋子與它后面相鄰棋子之間的空格數(shù)。將這些空格數(shù)視為Nim游戲中的一堆堆石子。那么移動(dòng)一個(gè)棋子等價(jià)于從某一堆石子中取走任意正數(shù)量的石子。4.2 第二步推導(dǎo)必勝策略對(duì)于經(jīng)典的Nim游戲有一個(gè)著名的結(jié)論當(dāng)且僅當(dāng)所有堆石子數(shù)的異或XOR和為0時(shí)先手必?cái)》駝t先手必勝。那么對(duì)于這個(gè)“高僧斗法”問(wèn)題我們?nèi)〕鏊衅鏀?shù)索引的棋子第135...個(gè)與其后一個(gè)棋子之間的空格數(shù)組成一個(gè)數(shù)組a。計(jì)算xor_sum a[0] ^ a[1] ^ ... ^ a[k]。如果xor_sum 0先手必?cái)》駝t先手必勝。為什么這是理解的關(guān)鍵而不是死記結(jié)論 可以將棋盤看作一個(gè)階梯奇數(shù)位置的棋子是“關(guān)鍵棋子”。整個(gè)游戲的勝負(fù)態(tài)等價(jià)于這些關(guān)鍵棋子與其后棋子間距構(gòu)成的Nim游戲。其證明需要用到博弈論的“SG函數(shù)”和“局面等效”概念對(duì)于沖刺階段我們可以先接受這個(gè)結(jié)論但必須理解其操作含義如果異或和非零先手可以通過(guò)移動(dòng)某個(gè)關(guān)鍵棋子改變其與后一棋子的間距使得新的異或和變?yōu)?從而將必?cái)B(tài)丟給對(duì)手。4.3 第三步代碼實(shí)現(xiàn)與驗(yàn)證def can_win(positions): 判斷先手是否必勝。 positions: 一個(gè)列表表示棋子所在的格子編號(hào)已按升序排列。 例如: [1, 5, 9] 表示三個(gè)棋子分別在1,5,9格。 # 計(jì)算奇數(shù)索引棋子0-based索引中的偶數(shù)索引與其后一棋子的間距 xor_sum 0 for i in range(0, len(positions) - 1, 2): # 步長(zhǎng)為2取偶數(shù)索引 distance positions[i 1] - positions[i] - 1 # 兩者之間的空格數(shù) xor_sum ^ distance return xor_sum ! 0 # 測(cè)試 print(can_win([1, 5, 9])) # 棋子位置1,5,9。間距(5-1-1)3, (9-5-1)3? 注意我們只取奇數(shù)位(第1個(gè))的間距3。xor_sum3 !0先手必勝。 print(can_win([1, 5, 8, 10])) # 棋子位置1,5,8,10。奇數(shù)位間距(5-1-1)3, (10-8-1)1。xor_sum3^12 !0先手必勝。 print(can_win([1, 2])) # 棋子位置1,2。奇數(shù)位間距(2-1-1)0。xor_sum0先手必?cái) Ｉ疃冉馕龅膬r(jià)值體現(xiàn)如果只是背下了“異或和為0必?cái) 钡慕Y(jié)論題目稍微一變就可能出錯(cuò)。例如如果棋子不是放在格子上而是放在線上間隔不同或者移動(dòng)規(guī)則改變可以向左移動(dòng)。通過(guò)上面的三步分析我們不僅知道了結(jié)論更理解了如何建模將具體場(chǎng)景轉(zhuǎn)化為棋子間距。如何轉(zhuǎn)化識(shí)別出這是階梯博弈并提取關(guān)鍵間距奇數(shù)位。如何應(yīng)用通用定理套用Nim游戲的結(jié)論。如何驗(yàn)證通過(guò)小規(guī)模測(cè)試用例驗(yàn)證邏輯。這樣即使遇到新的變種題你也有了分析和推導(dǎo)的武器而不是只能祈禱考到原題。5. 沖刺階段的高效真題使用方法論最后幾天時(shí)間寶貴如何最大化真題的效用我總結(jié)了一個(gè)“四步真題深度利用法”親測(cè)有效。5.1 第一步限時(shí)模擬還原考場(chǎng)壓力找一套往年真題設(shè)定好比賽時(shí)長(zhǎng)通常是4小時(shí)完全模擬考場(chǎng)環(huán)境不查資料、不調(diào)試IDE只用記事本和命令行、不中途休息。這一步的目的是暴露問(wèn)題。你可能會(huì)發(fā)現(xiàn)時(shí)間分配不合理、讀題速度慢、代碼調(diào)試能力弱、簡(jiǎn)單題粗心出錯(cuò)等問(wèn)題。這些問(wèn)題只有在高壓下才會(huì)顯現(xiàn)平時(shí)松散刷題是發(fā)現(xiàn)不了的。5.2 第二步精細(xì)復(fù)盤分類整理錯(cuò)題模擬結(jié)束后不要只看分?jǐn)?shù)。對(duì)每一道題進(jìn)行精細(xì)復(fù)盤AC的題你的解法是否最優(yōu)時(shí)間復(fù)雜度、空間復(fù)雜度是否還有提升空間代碼是否足夠簡(jiǎn)潔清晰部分得分的題是哪個(gè)測(cè)試點(diǎn)沒(méi)過(guò)是邊界條件、特殊數(shù)據(jù)還是算法邏輯有漏洞嘗試構(gòu)造能觸發(fā)錯(cuò)誤的數(shù)據(jù)。不會(huì)做的題卡在哪里是完全沒(méi)思路還是思路錯(cuò)誤將這道題涉及的知識(shí)點(diǎn)標(biāo)記出來(lái)。建議建立一個(gè)錯(cuò)題本但不是抄題而是記錄題目核心模型如區(qū)間調(diào)度、最短路徑、動(dòng)態(tài)規(guī)劃、搜索。你的錯(cuò)誤思路和正確思路的對(duì)比。關(guān)鍵突破口哪一句話或哪個(gè)條件讓你豁然開(kāi)朗。易錯(cuò)點(diǎn)數(shù)據(jù)范圍、初始化、下標(biāo)從0還是1開(kāi)始等。5.3 第三步專題突破彌補(bǔ)知識(shí)短板根據(jù)錯(cuò)題本你會(huì)發(fā)現(xiàn)自己的薄弱環(huán)節(jié)。最后幾天不適合再系統(tǒng)學(xué)習(xí)新算法但可以進(jìn)行專題強(qiáng)化。例如如果動(dòng)態(tài)規(guī)劃DP總是丟分就集中刷3-5道經(jīng)典DP真題如01背包、最長(zhǎng)公共子序列、矩陣連乘等總結(jié)狀態(tài)定義和轉(zhuǎn)移方程的套路。如果圖論題總是超時(shí)就重點(diǎn)復(fù)習(xí)一下Dijkstra堆優(yōu)化、Floyd、并查集的模板代碼。5.4 第四步提煉模板構(gòu)建肌肉記憶對(duì)于高頻考點(diǎn)和常用算法準(zhǔn)備好自己的“代碼模板”。注意是自己的模板不是網(wǎng)上直接抄的。你要理解每一行代碼的作用并經(jīng)過(guò)多次敲打形成肌肉記憶。例如快速排序/歸并排序二分查找及其變種找第一個(gè)大于等于x的位置并查集路徑壓縮、按秩合并Dijkstra算法使用優(yōu)先隊(duì)列Floyd算法KMP字符串匹配快速冪算法在考場(chǎng)上遇到相關(guān)題目你可以像填空一樣快速將模板適配到具體問(wèn)題節(jié)省大量時(shí)間并減少低級(jí)錯(cuò)誤。最后幾天的心理建議停止刷新題尤其是難題。重心放在回顧錯(cuò)題、熟悉模板和調(diào)整心態(tài)上。保證睡眠飲食清淡。進(jìn)入考場(chǎng)后前10分鐘快速瀏覽所有題目按“易-中-難”做好時(shí)間規(guī)劃。通常有“簽到題”務(wù)必先拿下建立信心。遇到卡殼的題果斷標(biāo)記后跳過(guò)不要死磕。記住藍(lán)橋杯是比賽目標(biāo)是多得分而不是解決所有問(wèn)題。