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