1. 賽題復盤與整體策略剛結(jié)束的第十五屆藍橋杯省賽Python B組難度梯度設(shè)置得相當有意思既有送分的基礎(chǔ)題也有需要仔細琢磨的中等題最后壓軸的幾道更是對算法思維和代碼實現(xiàn)能力的雙重考驗。我這次拿到了78分雖然離頂尖高手還有距離但對于大多數(shù)志在省一或國賽入場券的選手來說這個分數(shù)段的分析和題解可能更具參考價值。這次比賽再次印證了一個道理在藍橋杯的賽場上暴力枚舉DFS/BFS、動態(tài)規(guī)劃DP、貪心、二分查找和簡單的數(shù)論知識是絕對的主力而Python選手的優(yōu)勢在于編碼速度和豐富的內(nèi)置庫但劣勢也很明顯——同樣的邏輯Python在極限數(shù)據(jù)下的運行時間壓力更大。所以策略的核心就是在有限的時間內(nèi)為每道題選擇最“經(jīng)濟”的解法能暴力拿部分分就先拿下有時間再優(yōu)化一眼能看出標準解法的力求一遍過。這次省賽的題目整體感覺是“新瓶裝舊酒”題型還是那些經(jīng)典題型比如日期處理、字符串操作、搜索、DP但題干包裝得更貼近實際應(yīng)用像“校園美食家”、“神奇的數(shù)組”這類題目需要你快速剝離背景抽象出模型。下面我就結(jié)合自己的考場思路和考后的復盤對每道題進行詳細的拆解重點講我當時怎么想的、怎么做的以及考后反思的更優(yōu)解。我會盡量還原考場上的真實思考過程包括那些“差點掉進去的坑”。2. 試題逐題精講與思路拆解2.1 基礎(chǔ)題穩(wěn)拿分的“定心丸”省賽的前幾題通常是用來穩(wěn)定軍心和熱身用的但千萬不能大意因為這里的任何失誤都是不可原諒的丟分。第一題日期計算這類題幾乎是藍橋杯的保留節(jié)目。題干可能會問“從某年某月某日到某年某月某日有多少天”或者“某天是星期幾”。核心考點有兩個一是閏年的判斷(year % 4 0 and year % 100 ! 0) or (year % 400 0)這個公式必須像條件反射一樣熟練二是月份天數(shù)的累加這里我強烈建議準備一個月份天數(shù)的列表month_days [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]并在閏年時將二月天數(shù)改為29。我的做法是寫一個函數(shù)days_from_start(year, month, day)計算從某個固定起點比如公元1年1月1日到目標日期的總天數(shù)兩個日期相減即可得到間隔。這樣做的好處是避免了復雜的邊界條件討論代碼不易出錯。第二題字符串處理或進制轉(zhuǎn)換今年考的是一道關(guān)于字符串重新排列的題。給定一個字符串按照特定規(guī)則重新排序后輸出。Python處理這種題優(yōu)勢巨大。關(guān)鍵點在于熟練掌握sorted()函數(shù)的key參數(shù)。例如如果需要按字符出現(xiàn)頻率降序、頻率相同按ASCII碼升序排列一句代碼就能搞定result .join(sorted(s, keylambda c: (-s.count(c), ord(c))))。但要注意在循環(huán)中反復調(diào)用s.count(c)效率是 O(n2)對于本題長度完全足夠但如果字符串很長更好的做法是用collections.Counter先統(tǒng)計頻率?？紙鰰r間緊我選擇了前者先確保正確性。注意基礎(chǔ)題務(wù)必使用最穩(wěn)妥、最熟悉的寫法。不要為了微小的性能提升去嘗試不熟悉的語法或庫一旦寫錯調(diào)試起來更耗時。2.2 中等題思維與實現(xiàn)的“分水嶺”從這幾題開始需要一些簡單的算法設(shè)計和優(yōu)化思想了。第三題搜索類DFS/BFS—— “校園美食家”這題名字很生活本質(zhì)是一個網(wǎng)格圖上的搜索問題。題目描述了一個校園地圖‘.’代表路‘#’代表障礙‘F’代表美食點。主人公從起點‘S’出發(fā)需要收集至少K個美食點問最短路徑長度。 我的考場思路狀態(tài)定義最直接的BFS狀態(tài)是(x, y)坐標。但這里還需要記錄收集到的美食點數(shù)量。所以狀態(tài)必須擴展為(x, y, count)其中count是當前已收集的美食點數(shù)。狀態(tài)轉(zhuǎn)移向四個方向移動如果新位置是‘F’則count1否則count不變。終止條件當count K時記錄當前步數(shù)此時BFS首次到達該狀態(tài)的步數(shù)就是最短路徑。去重訪問過的狀態(tài)(x, y, count)需要記錄避免重復入隊。這里我用了三維列表visited[x][y][count]來標記。from collections import deque def bfs(grid, K, start): m, n len(grid), len(grid[0]) # 找到起點S for i in range(m): for j in range(n): if grid[i][j] S: sx, sy i, j # visited[i][j][c] 表示在(i,j)位置且已收集c個美食點的狀態(tài)是否已訪問 visited [[[False]*(K1) for _ in range(n)] for _ in range(m)] q deque() q.append((sx, sy, 0, 0)) # (x, y, count, steps) visited[sx][sy][0] True dirs [(0,1),(0,-1),(1,0),(-1,0)] while q: x, y, cnt, steps q.popleft() if cnt K: return steps for dx, dy in dirs: nx, ny xdx, ydy if 0nxm and 0nyn and grid[nx][ny] ! #: new_cnt cnt if grid[nx][ny] F: new_cnt cnt 1 if new_cnt K: # 超過K個按K個算壓縮狀態(tài)空間 new_cnt K if not visited[nx][ny][new_cnt]: visited[nx][ny][new_cnt] True q.append((nx, ny, new_cnt, steps1)) return -1 # 如果無法收集到K個美食點踩坑點visited數(shù)組的第三維大小設(shè)為K1就夠了因為當收集數(shù)量大于等于K時目標就已達成可以統(tǒng)一視為K這樣能大幅減少狀態(tài)數(shù)避免內(nèi)存超限。這是BFS解決帶約束路徑問題的常用技巧。第四題動態(tài)規(guī)劃DP—— “最優(yōu)分配”題目大意有n個任務(wù)和m個資源單位每個任務(wù)需要消耗一定資源并產(chǎn)生一定價值求在資源限制下的最大總價值。這是一個經(jīng)典的0-1背包問題變種。 我的解題步驟立刻識別出是背包問題。資源總量m就是背包容量每個任務(wù)的任務(wù)消耗cost[i]是物品重量價值value[i]是物品價值。定義DP數(shù)組dp[j]表示使用恰好j單位資源時能獲得的最大價值。初始化dp[0]0其余為負無窮因為要求“恰好”使用但本題通常求不超過m的最大值初始化0即可。狀態(tài)轉(zhuǎn)移對于每個任務(wù)i倒序遍歷j從m到cost[i]dp[j] max(dp[j], dp[j - cost[i]] value[i])。最終答案max(dp)。n, m map(int, input().split()) cost [] value [] for _ in range(n): c, v map(int, input().split()) cost.append(c) value.append(v) dp [0] * (m 1) for i in range(n): for j in range(m, cost[i] - 1, -1): dp[j] max(dp[j], dp[j - cost[i]] value[i]) print(max(dp))心得DP題最關(guān)鍵的是準確定義狀態(tài)和寫出轉(zhuǎn)移方程。在考場上如果一時想不出最優(yōu)的DP定義可以先寫一個記憶化搜索DFS緩存這往往更直觀也能拿到不少分然后再有時間可以嘗試優(yōu)化成遞推DP。2.3 進階題優(yōu)化與剪枝的“試金石”這幾題需要更優(yōu)的算法才能通過全部測試用例。第五題二分查找 貪心驗證題目通常描述為將一個數(shù)組分成連續(xù)的K段每段有一個權(quán)重如最大值、和值要求最小化所有段權(quán)重的最大值。這類問題被稱為“最小化最大值問題”標準解法是二分答案。 解題框架二分答案答案即最大段權(quán)重肯定在數(shù)組最大值和數(shù)組總和之間。在這個范圍內(nèi)進行二分查找。貪心驗證給定一個候選答案mid判斷能否將數(shù)組分成不超過K段且每段的權(quán)重不超過mid。驗證方法是從頭開始累加一旦當前段權(quán)重超過mid就新開一段。如果需要的段數(shù)小于等于K則mid可行否則不可行。更新邊界如果mid可行說明答案可以更小或等于mid令right mid如果不可行說明答案必須更大令left mid 1。def can_split(nums, K, limit): 判斷在每段和不超過limit的情況下能否將nums分成K段 count 1 # 當前段數(shù) current_sum 0 for num in nums: if current_sum num limit: count 1 current_sum num if count K: # 段數(shù)已超 return False else: current_sum num return True def solve(nums, K): left, right max(nums), sum(nums) while left right: mid (left right) // 2 if can_split(nums, K, mid): right mid else: left mid 1 return left核心技巧二分查找的循環(huán)條件是while left right更新時right mid和left mid 1要配對這樣可以保證最終left就是答案且不會死循環(huán)。這是二分查找一個非常經(jīng)典的寫法。第六題數(shù)論與規(guī)律查找藍橋杯?？糋CD最大公約數(shù)、LCM最小公倍數(shù)、質(zhì)因數(shù)分解、同余等知識。今年的題涉及一個數(shù)列的構(gòu)造和查詢。對于這類題如果數(shù)據(jù)規(guī)模很大直接模擬必超時。我的策略是先寫一個暴力程序生成小規(guī)模的數(shù)據(jù)比如n20。觀察輸出結(jié)果尋找規(guī)律?？赡苄枰蛴〕鰯?shù)列的前若干項或者計算某些特定項的值。將找到的規(guī)律用數(shù)學公式或遞推式表達出來。用這個公式來編寫高效的程序。例如題目可能是定義數(shù)列 a[n] a[n-1] n * (某個與n互質(zhì)的函數(shù))然后問第N項的值。通過暴力打表你可能會發(fā)現(xiàn) a[n] 其實是 n*(n1)/2 的某個倍數(shù)或者與平方和有關(guān)。一旦找到規(guī)律代碼就變得非常簡單?？紙錾衔以谶@類題上花了較多時間觀察但一旦規(guī)律找到編碼就很快。2.4 壓軸題綜合能力的“競技場”最后兩題通常綜合了多種算法或者數(shù)據(jù)結(jié)構(gòu)要求較高。第七題復雜模擬 數(shù)據(jù)結(jié)構(gòu)優(yōu)化題目描述了一個稍復雜的規(guī)則需要對一組數(shù)據(jù)進行多輪操作。直接按照題意模擬在數(shù)據(jù)量大的情況下可能會超時。這里需要分析每次操作的本質(zhì)并用合適的數(shù)據(jù)結(jié)構(gòu)來加速。 常見優(yōu)化手段區(qū)間更新與查詢?nèi)绻婕皩?shù)組某個區(qū)間所有元素加一個值然后查詢考慮使用差分數(shù)組。差分數(shù)組能在O(1)時間內(nèi)完成區(qū)間加減最后再通過前綴和還原原數(shù)組。頻繁查找最值如果需要動態(tài)維護一個集合的最大值/最小值并支持添加刪除Python的heapq小頂堆是利器。如果需要同時維護最大最小可以考慮使用兩個堆或者使用SortedList但藍橋杯環(huán)境可能沒有sortedcontainers庫需謹慎。集合與映射關(guān)系大量使用in操作時用set或dict代替list。我在一道題中遇到了需要維護一個動態(tài)列表并頻繁刪除中間元素的情況。使用list的pop(i)操作是O(n)的會超時。解決方案是采用“懶惰刪除”策略用一個布爾數(shù)組deleted標記元素是否被刪除實際并不從列表中移除。只有當被刪除元素積累到一定程度比如超過一半或者它位于我們關(guān)心的位置時才進行一次集中的清理。這本質(zhì)是一種用空間換時間的權(quán)衡。第八題高級圖論或狀態(tài)壓縮DP這是拉開差距的題目。我這次遇到的是一個狀態(tài)壓縮DP狀壓DP的變種。題目涉及選擇若干個節(jié)點滿足某些約束求最優(yōu)解。當節(jié)點數(shù)N在20以內(nèi)時就要考慮狀壓DP了。 狀壓DP的核心是用一個整數(shù)的二進制位來表示一個集合。例如mask 13 (二進制1101)表示選擇了第0、2、3號節(jié)點從右往左數(shù)。 解題步驟定義狀態(tài)dp[mask]表示當選擇的節(jié)點集合為mask時所能得到的某種最優(yōu)值如最大收益、最小成本。狀態(tài)轉(zhuǎn)移通常從已知狀態(tài)dp[mask]出發(fā)嘗試添加一個不在mask中的節(jié)點i形成新狀態(tài)new_mask mask | (1i)并更新dp[new_mask]。轉(zhuǎn)移時需要檢查添加節(jié)點i是否合法是否與mask中的節(jié)點沖突等。初始化與答案dp[0]通常有確定值如0。最終答案在所有可能的mask中取最優(yōu)。n 10 # 假設(shè)有10個節(jié)點 dp [-float(inf)] * (1 n) dp[0] 0 # 初始化一個都不選時收益為0 # 預(yù)處理一些信息比如每個節(jié)點的價值val[i]或者節(jié)點間的沖突關(guān)系conflict[i][j] for mask in range(1 n): if dp[mask] 0: # 無效狀態(tài) continue for i in range(n): if mask (1 i): # 節(jié)點i已在集合中 continue # 檢查合法性例如節(jié)點i是否與mask中所有節(jié)點都不沖突 ok True for j in range(n): if mask (1 j) and conflict[i][j]: ok False break if ok: new_mask mask | (1 i) dp[new_mask] max(dp[new_mask], dp[mask] val[i]) ans max(dp) # 最終答案難點狀壓DP的難點在于狀態(tài)設(shè)計和轉(zhuǎn)移條件的梳理。在考場上如果時間不夠可以嘗試用DFS剪枝來求解小規(guī)模數(shù)據(jù)拿到部分分數(shù)。對于這題我由于時間關(guān)系只完成了狀態(tài)設(shè)計和基礎(chǔ)轉(zhuǎn)移一些復雜的約束條件沒來得及完全處理估計丟了不少分。3. 考場時間分配與策略復盤拿到78分除了題目本身的理解和編碼時間分配策略至關(guān)重要。下面是我的時間分配復盤供大家參考0-30分鐘快速通讀所有題目標記出難度。通常A~D是基礎(chǔ)題E~G是中等題H~J是難題。我首先用15~20分鐘把A~D題全部AC建立信心保證基礎(chǔ)分拿穩(wěn)。30-90分鐘主攻E~G題。這部分是得分的關(guān)鍵。每道題思考時間控制在10-15分鐘。如果10分鐘內(nèi)沒有清晰思路先寫一個暴力解法DFS、枚舉提交確保拿到部分分然后做標記繼續(xù)下一題。我在“校園美食家”搜索題上花了較多時間調(diào)試BFS的狀態(tài)維度用了約25分鐘。90-150分鐘集中精力攻克H、I題。這時要有所取舍。我判斷I題狀壓DP我更有把握于是先攻I題?；?0分鐘推導狀態(tài)和轉(zhuǎn)移方程并寫出了主要框架。J題通常最難則直接寫了一個最樸素的暴力程序能過多少樣例算多少。最后30分鐘不再開新題。做三件事1) 檢查所有已提交題目的代碼有無明顯的低級錯誤如數(shù)組越界、變量名寫錯。2) 回過頭看那些只拿了部分分的題思考優(yōu)化方法嘗試改進。3) 確保所有題目的文件輸入輸出格式正確藍橋杯是OJ形式但有時需要input()讀取。血淚教訓永遠不要在一道題上卡死超過30分鐘。藍橋杯是積分制5道題各拿80%的分比4道題AC而1道題0分要劃算得多。先保證廣度再追求深度。4. Python備賽技巧與環(huán)境配置工欲善其事必先利其器。Python選手在備賽時除了刷題還有一些環(huán)境和技術(shù)上的細節(jié)要注意。4.1 常用模板與代碼片段在比賽開始前我會在編輯器中準備好一些常用模板節(jié)省時間快速輸入對于大量數(shù)據(jù)輸入使用sys.stdin.read().split()比循環(huán)調(diào)用input()快得多。import sys data sys.stdin.read().split() # 然后按需轉(zhuǎn)換為int等類型遞歸深度與棧DFS遞歸深了可能爆?？梢栽O(shè)置遞歸深度或使用迭代棧。import sys sys.setrecursionlimit(1000000) # 設(shè)置遞歸深度無窮大定義INF float(inf)或INF 10**18。方向數(shù)組dirs [(0,1),(1,0),(0,-1),(-1,0)]用于二維網(wǎng)格的上下左右移動。4.2 調(diào)試與測試技巧藍橋杯比賽時沒有本地判題機但提供樣例。如何高效利用樣例完全復現(xiàn)樣例首先確保你的程序能完全通過題目給出的樣例。不僅要結(jié)果對如果題目要求輸出格式如空格、換行也要一模一樣。設(shè)計邊界測試思考輸入的極限情況。例如數(shù)組為空n0、所有元素相同、數(shù)字極大/極小等。在腦子里模擬運行或者用代碼簡單生成測試。對拍如果時間允許對于不確定的題可以寫一個絕對正確但很慢的暴力程序brute_force.py和你的優(yōu)化程序solve.py進行隨機輸入對比。這在平時練習時是發(fā)現(xiàn)邏輯錯誤的神器。4.3 Python性能優(yōu)化淺談Python慢是共識但在算法競賽中通過一些技巧可以規(guī)避大部分性能問題避免全局變量在函數(shù)內(nèi)部訪問局部變量比訪問全局變量快。盡量將主邏輯封裝在solve()函數(shù)內(nèi)。使用list代替deque當隊列操作非常頻繁且簡單時用list和兩個指針模擬隊列可能比collections.deque更快但deque在從兩端增刪時更通用。減少函數(shù)調(diào)用在深度循環(huán)中頻繁調(diào)用自定義函數(shù)或len()、range()會有開銷?？梢允孪葘en(arr)存入變量或者將簡單的函數(shù)邏輯內(nèi)聯(lián)。使用PyPy3提交藍橋杯環(huán)境通常提供Python3和PyPy3解釋器。PyPy3對純Python代碼有極佳的JIT優(yōu)化尤其是循環(huán)密集型的程序速度可能提升數(shù)倍。如果題目沒有明確要求使用特定解釋器無腦選PyPy3。我的大部分提交都是用的PyPy3。5. 從省賽到國賽的備賽建議對于已經(jīng)拿下省賽并瞄準國賽的同學接下來的訓練需要更有針對性。5.1 知識體系查漏補缺根據(jù)省賽暴露的弱點重點加強。如果動態(tài)規(guī)劃薄弱就專項練習線性DP、區(qū)間DP、樹形DP、狀壓DP的經(jīng)典模型背包、LIS、LCS、編輯距離、石子合并等。如果圖論題發(fā)怵就刷最短路Dijkstra, SPFA、最小生成樹Kruskal, Prim、拓撲排序、網(wǎng)絡(luò)流基礎(chǔ)的題目。5.2 進行限時模擬賽找歷年國賽真題或高質(zhì)量模擬賽嚴格按照4小時的時間進行全真模擬。訓練自己在高壓下的讀題、構(gòu)思、編碼、調(diào)試能力。賽后不僅要看錯題更要復盤時間分配是否合理哪道題浪費了時間哪道題應(yīng)該更早放棄。5.3 學習優(yōu)秀題解與代碼在藍橋杯官網(wǎng)、各大OJ平臺或社區(qū)如CSDN、知乎上尋找高分選手的題解。重點看他們的思路分析和代碼實現(xiàn)技巧。同樣一道題別人的代碼可能更簡潔、更高效。學習他們是如何定義狀態(tài)的如何設(shè)計循環(huán)的用了哪些Python特有的技巧如列表推導式、itertools庫等。5.4 保持手感與心態(tài)考前一周每天保持一定量的刷題但強度不宜過大主要是維持手感。復習常用模板和易錯點。比賽時的心態(tài)至關(guān)重要遇到難題不要慌相信自己的訓練成果按照既定策略能拿一分是一分。記住藍橋杯的排名不僅取決于你解決了多少難題更取決于你在所有題目上的總得分穩(wěn)扎穩(wěn)打才是王道。這次省賽78分算是一個對自己階段性學習的肯定也看到了在復雜DP和優(yōu)化技巧上的不足。編程競賽就像爬山每一步都算數(shù)。把每次比賽暴露的問題當成進步的階梯持續(xù)練習和總結(jié)國賽場上定能有更好的發(fā)揮。最后分享一個我自己的小習慣每次寫完一道題的代碼即使樣例過了也會在心里快速過一遍幾個關(guān)鍵的邊界條件這個“心理測試”幫我避免了好幾次粗心導致的提交錯誤。