1. 項目概述一場算法競賽的深度復盤“藍橋杯”這個名字對于國內(nèi)計算機相關(guān)專業(yè)的學生和算法愛好者來說絕對不陌生。它不僅僅是一場考試更像是一個檢驗編程思維、算法功底和臨場應變能力的試煉場。國賽作為這場系列賽事的最高舞臺其題目往往兼具深度、廣度和巧思。今天我想和大家深入復盤的是第十二屆藍橋杯國賽 Java 大學 B 組簡稱 JavaB的“day10”題目。請注意這里“day10”并非指比賽日期而極有可能是某位選手或機構(gòu)在整理真題時對某一道具體題目的內(nèi)部編號或指代。我們將以此為契機不局限于一道題而是系統(tǒng)性地拆解國賽級別題目的典型特征、解題思路的構(gòu)建過程、編碼實現(xiàn)中的精妙細節(jié)以及那些只有真正在賽場上踩過坑才能領(lǐng)悟到的經(jīng)驗。對于正在備賽的選手這篇文章將為你提供一份超越題解本身的“戰(zhàn)術(shù)指南”對于算法愛好者這是一次窺探高水平競賽題目設計邏輯的絕佳機會而對于普通開發(fā)者其中涉及的優(yōu)化思想、邊界處理技巧同樣能反哺到日常的開發(fā)工作中。我們將從題目場景還原開始逐步深入到核心算法模型的識別、多種解法的對比與取舍最后分享實戰(zhàn)編碼時如何規(guī)避陷阱、提升效率。這不僅僅是一篇解題報告更是一次思維模式的訓練。2. 國賽題目典型特征與破題思路國賽級別的題目尤其是 JavaB 組的壓軸題或中高難度題通常不會考察單一、直白的知識點。它們更像是精心設計的“綜合謎題”往往具有以下幾個顯著特征理解這些特征是成功破題的第一步。2.1 場景包裝與本質(zhì)抽象出題人擅長將經(jīng)典的算法問題包裹在一個新穎的、有時甚至是生活化的場景之下。例如題目描述可能關(guān)于“植物生長”、“網(wǎng)絡信號覆蓋”、“物資調(diào)度”或“圖形變換”。選手的首要任務就是“撥開迷霧”識別出場景背后的數(shù)學模型或經(jīng)典算法問題。這需要扎實的算法知識儲備和強大的抽象能力。以“路徑規(guī)劃”類場景為例題目可能描述為“機器人從能源站出發(fā)收集散落在網(wǎng)格中的電池并返回基地求最短時間”。這本質(zhì)上很可能是一個旅行商問題TSP的變種或者是BFS廣度優(yōu)先搜索求最短路徑與狀態(tài)壓縮DP的結(jié)合。關(guān)鍵在于你要迅速將“機器人”、“電池”、“障礙物”等實體抽象為圖論中的“節(jié)點”、“必須訪問的點集”、“不可通過的點”。注意國賽題目有時會在經(jīng)典模型上增加“約束條件”比如收集物品有順序要求、移動有特殊消耗規(guī)則等。這時不能生搬硬套模板而需要在經(jīng)典算法框架上進行適配性修改。2.2 數(shù)據(jù)規(guī)模的暗示與算法選擇題目給出的數(shù)據(jù)范圍如 n, m 1000或 k 20是選擇算法的決定性依據(jù)。這是藍橋杯以及大多數(shù)算法競賽一個非常友好的設計它直接告訴你暴力搜索能否通過暗示你應該使用多項式時間復雜度的算法還是指數(shù)級的。小規(guī)模n 20強烈暗示可能用到狀態(tài)壓縮動態(tài)規(guī)劃或深度優(yōu)先搜索配合剪枝。中等規(guī)模n 1000通常指向O(n2)或O(n log n)的算法如動態(tài)規(guī)劃、二分答案、貪心、并查集、最短路等。大規(guī)模n 10?必須使用O(n log n)或O(n)的算法如貪心、樹狀數(shù)組/線段樹、前綴和、雙指針、單調(diào)棧/隊列等。對于“day10”這類國賽題其數(shù)據(jù)規(guī)模往往會將時間復雜度卡在O(n log n)到O(n2)之間需要非常精細的實現(xiàn)。例如一個 O(n2) 的算法當 n5000 時運算量是 2.5*10?在 Java 下經(jīng)過良好優(yōu)化或許能勉強通過藍橋杯評測機性能尚可但如果 n10000達到 10? 量級就非常危險了。這時一個 O(n log n) 的解法如排序后處理就安全得多。2.3 對邊界條件和特殊情況的極致考察這是區(qū)分普通選手和高水平選手的關(guān)鍵。國賽題目中邊界情況往往不是“有沒有”的問題而是“有多少種”和“多隱蔽”的問題。數(shù)值邊界整數(shù)溢出特別是使用int時結(jié)果或中間值可能超過 21億、浮點數(shù)精度誤差比較相等時使用1e-6容差、數(shù)組下標越界從0開始還是1開始。邏輯邊界空輸入怎么處理所有元素都相同怎么辦目標值不存在怎么辦圖不連通怎么辦DP的初始狀態(tài)如何設定才能覆蓋所有情況題意隱含邊界“非負整數(shù)”包含0嗎“嚴格遞增”和“非遞減”區(qū)別巨大。題目說“可以重復經(jīng)過某個點”那是否意味著需要處理環(huán)在思考解法時必須同步思考這些邊界。一個穩(wěn)健的做法是在草稿紙上單獨列出所有你能想到的特殊情況并在編寫代碼時逐一處理或確認其被算法覆蓋。3. 核心算法工具箱與實戰(zhàn)應用面對一個抽象的國賽問題我們需要一個清晰的思維鏈條讀題 - 抽象模型 - 根據(jù)數(shù)據(jù)規(guī)模選擇算法 - 設計細節(jié) - 編碼 - 測試邊界。下面我們結(jié)合一些國賽常見題型拆解這個鏈條。3.1 動態(tài)規(guī)劃從線性DP到狀態(tài)壓縮動態(tài)規(guī)劃是國賽的絕對重頭戲。其難點在于狀態(tài)定義和轉(zhuǎn)移方程的設計。經(jīng)典題型最長公共子序列/子串、背包問題、區(qū)間DP、樹形DP、狀態(tài)壓縮DP。實戰(zhàn)案例剖析假設“day10”題目是一個復雜的路徑/選擇問題涉及多個維度如時間、位置、資源狀態(tài)。我們可以這樣思考狀態(tài)定義這是最關(guān)鍵的一步。狀態(tài)必須能夠唯一描述一個“子問題”的局面。通常使用dp[i][j][k]...的形式。例如dp[i][j]處理到前 i 個物品當前容量為 j 時的最大價值01背包。dp[i][j]字符串 A 前 i 個字符和字符串 B 前 j 個字符的最長公共子序列長度。dp[mask][i]當前已訪問的點集狀態(tài)為mask狀態(tài)壓縮最后停留在點 i 的最短路徑TSP。 對于更復雜的問題狀態(tài)維度可能更多。定義狀態(tài)時要問自己知道了這個狀態(tài)能否通過某種決策轉(zhuǎn)移到下一個狀態(tài)狀態(tài)轉(zhuǎn)移方程用數(shù)學公式描述狀態(tài)之間的關(guān)系。思考要達到當前狀態(tài)dp[state]可能從哪些前驅(qū)狀態(tài)dp[prev_state]經(jīng)過什么決策消耗什么獲得什么轉(zhuǎn)移而來寫出這個方程。初始化和邊界dp[0]或dp[起點狀態(tài)]的值是多少哪些狀態(tài)是非法/不可達的通常初始化為一個極大或極小值如Integer.MAX_VALUE/2或-1計算順序確保在計算dp[state]時它所依賴的所有dp[prev_state]都已經(jīng)被計算出來。這通常決定了循環(huán)的嵌套順序。實操心得在競賽中如果DP思路卡殼可以嘗試先寫一個記憶化搜索遞歸緩存。這更符合人類的思維模式從大問題分解到小問題更容易保證正確性。在思路清晰后再轉(zhuǎn)化為遞推形式的DP以獲得更好的性能。對于Java要注意遞歸深度可能導致的棧溢出以及記憶化搜索中緩存數(shù)據(jù)結(jié)構(gòu)如HashMap的開銷。3.2 搜索與剪枝當暴力成為藝術(shù)深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS是解決“求解所有可能方案”或“最短步數(shù)”問題的利器。但國賽的數(shù)據(jù)規(guī)模通常不允許純粹的暴力枚舉因此“剪枝”技術(shù)至關(guān)重要。BFS核心應用層序遍歷、最短路徑在無權(quán)圖中、狀態(tài)空間搜索如華容道、八數(shù)碼。使用Queue實現(xiàn)注意訪問標記visited數(shù)組或集合以避免重復訪問和死循環(huán)。DFS與剪枝策略可行性剪枝當前路徑已經(jīng)不可能達到目標提前返回。例如在求和問題中當前和加上剩余所有數(shù)的最大和仍小于目標值。最優(yōu)性剪枝當前路徑的“代價”已經(jīng)超過了目前找到的最優(yōu)解提前返回。順序性剪枝為了避免生成重復的排列組合在搜索時規(guī)定一個順序如從小到大枚舉對于重復元素在同一層搜索中只選擇第一個。對稱性剪枝如果問題存在對稱性可以只搜索一種情況。啟發(fā)式搜索A*在BFS基礎上使用優(yōu)先隊列并定義一個估價函數(shù)優(yōu)先擴展“希望更大”的節(jié)點可以顯著加快找到最優(yōu)解的速度。實戰(zhàn)編碼細節(jié)// DFS 模板示例 - 排列問題 void dfs(int[] nums, ListInteger path, boolean[] used, ListListInteger result) { if (path.size() nums.length) { // 終止條件 result.add(new ArrayList(path)); // 注意創(chuàng)建新列表 return; } for (int i 0; i nums.length; i) { if (used[i]) continue; // 訪問標記 if (i 0 nums[i] nums[i-1] !used[i-1]) continue; // 重復元素剪枝 used[i] true; path.add(nums[i]); dfs(nums, path, used, result); // 遞歸 path.remove(path.size() - 1); // 回溯 used[i] false; } }注意在Java中遞歸深度過深通常幾千層可能導致StackOverflowError。對于極端深度的搜索考慮使用顯式的棧Stack進行迭代實現(xiàn)。另外path等對象在加入結(jié)果集時一定要new ArrayList(path)進行拷貝否則后續(xù)回溯修改會影響已存儲的結(jié)果。3.3 圖論與高級數(shù)據(jù)結(jié)構(gòu)國賽題目中圖論問題常以“網(wǎng)絡”、“關(guān)系”、“連通性”的形式出現(xiàn)。除了基礎的DFS/BFS遍歷以下算法必須熟練掌握最短路徑Dijkstra算法非負權(quán)圖使用PriorityQueue最小堆實現(xiàn)時間復雜度 O((VE) log V)。關(guān)鍵點每次從堆中取出當前距離最短的點用它來松弛其鄰居。需要dist[]數(shù)組和visited標記或通過判斷dist[u]是否等于當前從堆中取出的值來實現(xiàn)。Floyd算法多源最短路三重循環(huán)代碼簡單但復雜度 O(V3)僅適用于頂點數(shù)較少V 500的情況。最小生成樹Kruskal算法并查集邊排序和Prim算法。Kruskal在邊數(shù)適中時實現(xiàn)更簡單。拓撲排序判斷有向圖是否有環(huán)、安排任務順序?？梢杂肂FS計算入度或DFS實現(xiàn)。并查集處理動態(tài)連通性問題的高效數(shù)據(jù)結(jié)構(gòu)。務必掌握路徑壓縮和按秩合并兩種優(yōu)化否則在鏈狀結(jié)構(gòu)下會退化為 O(n)。class UnionFind { int[] parent; int[] rank; // 或 size[] UnionFind(int n) { parent new int[n]; for(int i0; in; i) parent[i]i; rank new int[n]; } int find(int x) { // 路徑壓縮 if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } boolean union(int x, int y) { // 按秩合并 int rootX find(x), rootY find(y); if (rootX rootY) return false; if (rank[rootX] rank[rootY]) parent[rootX] rootY; else if (rank[rootX] rank[rootY]) parent[rootY] rootX; else { parent[rootY] rootX; rank[rootX]; } return true; } }樹狀數(shù)組與線段樹當問題涉及頻繁的“區(qū)間求和”與“單點更新”或“區(qū)間更新”時必須使用這些 O(log n) 的數(shù)據(jù)結(jié)構(gòu)來替代 O(n) 的暴力方法。這是國賽區(qū)分度的重要考點。線段樹功能更強大但代碼復雜樹狀數(shù)組代碼簡潔但功能相對受限主要用于前綴和操作。4. 從思路到AC完整解題流程與編碼實現(xiàn)假設我們面對一道虛構(gòu)的、符合國賽難度的“day10”題目來演練從讀題到AC的全過程。題目描述示例在一個 n x m 的網(wǎng)格中每個格子有高度h[i][j]。你從左上角 (1,1) 出發(fā)想去右下角 (n,m)。每次可以向上、下、左、右四個方向移動但只能移動到高度不高于當前格子的相鄰格子。此外你擁有一次“跳躍”能力可以瞬間移動到任意一個高度嚴格低于當前格子的位置。求從起點到終點的最少移動次數(shù)普通移動和跳躍都算一次移動。1 n, m 10000 h[i][j] 10^9。4.1 問題分析與模型抽象抽象模型這是一個在網(wǎng)格圖上的最短路徑問題。圖的節(jié)點是每個格子邊有兩種普通邊從格子A到相鄰格子B當且僅當h[B] h[A]代價為1。跳躍邊從格子A到任意格子B當且僅當h[B] h[A]代價為1。 目標求從起點到終點的最短路徑最少邊數(shù)。數(shù)據(jù)規(guī)模n, m 1000節(jié)點總數(shù)最多 10?。這意味著 O(N2) 的算法1012完全不可行。必須尋找 O(N log N) 或與邊數(shù)相關(guān)的算法。由于“跳躍邊”是任意點對之間的如果顯式構(gòu)建所有跳躍邊邊數(shù)將達到 O(N2)同樣爆炸。關(guān)鍵洞察“跳躍”能力非常強大但它有嚴格的高度下降限制。我們可以將問題轉(zhuǎn)化最短路徑 min( 不使用跳躍的最短路 使用一次跳躍的最短路 )。不使用跳躍就是一個簡單的BFS但只能在高度不上升的鄰域內(nèi)移動。使用一次跳躍路徑形態(tài)為起點 - (經(jīng)過若干普通邊) - 跳躍起點 P - (跳躍) - 跳躍終點 Q - (經(jīng)過若干普通邊) - 終點。 問題轉(zhuǎn)化為找到一對格子(P, Q)滿足h[Q] h[P]使得dist_start[P] 1 dist_end[Q]最小。其中dist_start[X]是從起點通過普通邊到達X的最短距離dist_end[X]是從X通過普通邊到達終點的最短距離這可以通過反向BFS從終點出發(fā)計算。4.2 算法設計與優(yōu)化計算 dist_start 和 dist_end執(zhí)行兩次受限的BFS。BFS隊列使用LinkedList訪問標記使用二維boolean數(shù)組。在BFS過程中只有滿足高度條件的鄰居才能入隊。尋找最優(yōu)跳躍對 (P, Q)最樸素的想法是枚舉所有P和Q檢查高度條件并計算dist_start[P] 1 dist_end[Q]取最小值。這是 O(N2)不可行。優(yōu)化對于每個可能作為跳躍起點P的格子我們想快速找到能使dist_start[P] 1 dist_end[Q]最小化的跳躍終點Q且h[Q] h[P]。 我們可以按高度處理。將所有格子按高度升序排序。維護一個數(shù)據(jù)結(jié)構(gòu)如變量在遍歷高度較低的格子時記錄它們dist_end的最小值。然后當遍歷到一個高度較高的格子作為P時所有高度比它低的格子都已經(jīng)被處理過我們可以直接獲取到min_dist_end從而快速計算dist_start[P] 1 min_dist_end。具體步驟將格子放入列表按高度h升序排序高度相同時任意順序。初始化min_dist_end INF。遍歷排序后的列表當前格子作為跳躍終點Q的候選更新min_dist_end Math.min(min_dist_end, dist_end[Q])。當前格子作為跳躍起點P的候選如果min_dist_end不是 INF說明存在比它低的格子則用dist_start[P] 1 min_dist_end更新全局答案。注意在同一高度內(nèi)格子既可能作Q也可能作P但題目要求h[Q] h[P]嚴格小于。因此我們需要將相同高度的格子作為一組來處理先統(tǒng)一用這一組的格子更新min_dist_end然后再用這一組的格子作為P來更新答案?；蛘咴谂判驎r將高度作為第一關(guān)鍵字再引入一個第二關(guān)鍵字來區(qū)分處理順序。最終答案ans min( dist_start[終點], 使用一次跳躍的最優(yōu)值 )。4.3 代碼實現(xiàn)與關(guān)鍵細節(jié)import java.util.*; public class Main { static int INF 0x3f3f3f3f; // 一個較大的數(shù)表示無窮大 static int[][] dirs {{0,1},{1,0},{0,-1},{-1,0}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(), m sc.nextInt(); int[][] h new int[n][m]; for (int i0; in; i) for (int j0; jm; j) h[i][j] sc.nextInt(); // 計算從起點出發(fā)的普通移動最短距離 int[][] distFromStart bfs(n, m, h, 0, 0, false); // 計算從終點出發(fā)的普通移動最短距離反向圖 int[][] distFromEnd bfs(n, m, h, n-1, m-1, true); // 處理跳躍 Listint[] cells new ArrayList(); for (int i0; in; i) { for (int j0; jm; j) { cells.add(new int[]{i, j, h[i][j]}); } } // 按高度升序排序高度相同則按坐標可任意 cells.sort((a,b)-{ if (a[2] ! b[2]) return a[2] - b[2]; if (a[0] ! b[0]) return a[0] - b[0]; return a[1] - b[1]; }); int ans distFromStart[n-1][m-1]; // 不使用跳躍的答案 int minDistEnd INF; // 按高度分組處理確保嚴格小于 int i 0; while (i cells.size()) { int j i; int currentHeight cells.get(i)[2]; // 階段1: 將當前高度格子作為Q更新minDistEnd while (j cells.size() cells.get(j)[2] currentHeight) { int x cells.get(j)[0], y cells.get(j)[1]; if (distFromEnd[x][y] INF) { minDistEnd Math.min(minDistEnd, distFromEnd[x][y]); } j; } // 階段2: 將當前高度格子作為P更新答案 int k i; while (k j) { int x cells.get(k)[0], y cells.get(k)[1]; if (distFromStart[x][y] INF minDistEnd INF) { ans Math.min(ans, distFromStart[x][y] 1 minDistEnd); } k; } i j; // 移動到下一個高度組 } System.out.println(ans INF ? -1 : ans); } // BFS計算最短距離reverse為true表示從終點向起點走判斷條件相反 static int[][] bfs(int n, int m, int[][] h, int sx, int sy, boolean reverse) { int[][] dist new int[n][m]; for (int i0; in; i) Arrays.fill(dist[i], INF); dist[sx][sy] 0; Queueint[] queue new LinkedList(); queue.offer(new int[]{sx, sy}); while (!queue.isEmpty()) { int[] cur queue.poll(); int x cur[0], y cur[1]; for (int[] d : dirs) { int nx x d[0], ny y d[1]; if (nx0 || nxn || ny0 || nym) continue; // 核心移動條件判斷 boolean canMove reverse ? (h[nx][ny] h[x][y]) : (h[nx][ny] h[x][y]); if (canMove dist[nx][ny] INF) { dist[nx][ny] dist[x][y] 1; queue.offer(new int[]{nx, ny}); } } } return dist; } }關(guān)鍵細節(jié)解讀INF的設置使用0x3f3f3f3f是一個技巧它大約等于10^9量級且兩個這樣的數(shù)相加不會溢出成負數(shù)。BFS中的移動條件reverse參數(shù)巧妙處理了正向和反向搜索時高度判斷條件的反轉(zhuǎn)。按高度分組處理這是保證“嚴格小于”條件的關(guān)鍵。我們先將同一高度的所有格子作為“終點Q”更新minDistEnd然后再將它們作為“起點P”來嘗試更新答案。這樣同一高度的格子之間不會互相作為跳躍的起終點。時間復雜度兩次BFS是 O(nm)排序是 O(N log N)其中 N nm 10^6。排序的 log N 大約為 20整體在可接受范圍內(nèi)。5. 賽場實戰(zhàn)技巧與避坑指南在高壓的比賽環(huán)境中思路清晰和代碼穩(wěn)健同樣重要。以下是我從多次競賽中總結(jié)出的血淚經(jīng)驗。5.1 輸入輸出與性能優(yōu)化藍橋杯允許使用Scanner但對于數(shù)據(jù)量巨大的題目如10^5行以上Scanner會非常慢可能導致超時。必須掌握的快速IOimport java.io.*; import java.util.*; public class Main { static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st new StreamTokenizer(br); static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out)); static int nextInt() throws IOException { st.nextToken(); return (int)st.nval; } static double nextDouble() throws IOException { st.nextToken(); return st.nval; } static String next() throws IOException { st.nextToken(); return st.sval; } public static void main(String[] args) throws IOException { // 使用 nextInt() 讀取整數(shù)比 Scanner.nextInt() 快數(shù)倍 int n nextInt(); // ... 解題邏輯 pw.println(ans); // 輸出 pw.flush(); // 最后刷新緩沖區(qū) } }注意StreamTokenizer的sval讀取字符串時默認以空格、制表符、換行符為分隔且會將單詞解析為數(shù)字。對于純字符串輸入有時需要調(diào)整st.wordChars()或使用BufferedReader.readLine()。其他性能貼士避免頻繁創(chuàng)建對象在循環(huán)內(nèi)盡量減少new操作如使用數(shù)組而非ArrayList存儲中間狀態(tài)重復使用對象。使用靜態(tài)數(shù)組在Java中靜態(tài)數(shù)組的訪問速度遠快于ArrayList。如果數(shù)據(jù)規(guī)模已知優(yōu)先用int[]而非ListInteger?？臻g換時間合理使用緩存、預計算如前綴和來避免重復計算。5.2 調(diào)試與測試策略比賽環(huán)境沒有IDE調(diào)試基本靠打印和腦補。一套高效的調(diào)試策略至關(guān)重要。小數(shù)據(jù)驗證編寫代碼后首先用題目中的樣例輸入測試。如果樣例不過立即用最簡單的小數(shù)據(jù)比如n1,2手動模擬在關(guān)鍵步驟打印變量值System.err.println打印到標準錯誤不影響評測。邊界測試自己構(gòu)造極端數(shù)據(jù)最大值/最小值n1000, m1000所有高度為0或10^9。特殊形狀所有格子高度相同、高度嚴格遞增/遞減。無解情況起點終點不連通在普通移動和跳躍下都不連通。對拍如果時間允許寫一個絕對正確但低效的暴力程序例如DFS枚舉所有路徑用于在小數(shù)據(jù)規(guī)模下n,m5與你的優(yōu)化程序進行隨機大量測試比對結(jié)果。5.3 常見“坑點”速查表坑點類別具體表現(xiàn)預防/解決方法整數(shù)溢出中間結(jié)果或最終結(jié)果超過int范圍約21億。使用long類型進行計算。檢查乘法、累加操作。數(shù)組越界訪問dp[n]或arr[n]而數(shù)組大小為n。牢記數(shù)組下標從0開始。循環(huán)條件用 length而非 length。多開幾個空間如new int[n5]有時能避免差1錯誤?？罩羔?空集合對未初始化的對象或空List進行操作。初始化所有引用變量。在調(diào)用list.get()前檢查!list.isEmpty()。浮點數(shù)比較使用直接比較兩個double。使用Math.abs(a - b) 1e-6或1e-12這樣的極小值作為容差。BFS/DFS未標記導致重復訪問、死循環(huán)或棧溢出。在節(jié)點入隊/入棧時立即標記為已訪問。多組數(shù)據(jù)未初始化處理完一組數(shù)據(jù)后靜態(tài)變量或全局數(shù)組未清空影響下一組。將變量定義在main函數(shù)內(nèi)或每組數(shù)據(jù)開始時重新初始化。遞歸過深導致StackOverflowError。改用迭代顯式?；驒z查遞歸深度是否合理。算法選擇錯誤使用了錯誤時間復雜度的算法導致超時。嚴格根據(jù)數(shù)據(jù)規(guī)模選擇算法。10^5的數(shù)據(jù)必須用O(n log n)或更優(yōu)。題意理解偏差“至少”和“至多”“不高于”和“低于”混淆。仔細讀題將關(guān)鍵條件用筆圈出來。用樣例驗證自己的理解。5.4 時間分配與心態(tài)管理一場比賽4小時10道題左右。合理的時間分配是前1小時快速瀏覽所有題目標記出最有思路的簡單題和中等題先解決它們以建立信心。中間2小時主攻中高難度題每道題思考編碼控制在30-45分鐘內(nèi)。如果超過45分鐘還沒有清晰思路或調(diào)試不通果斷保存當前代碼切換題目。最后1小時用于解決難題、檢查已做題目的邊界情況、優(yōu)化可能超時的代碼。遇到難題時不要慌張?；氐絾栴}本質(zhì)重新審視數(shù)據(jù)范圍嘗試最樸素的暴力方法哪怕只能過小數(shù)據(jù)這往往能幫助你發(fā)現(xiàn)規(guī)律。如果一道題始終無法AC確保至少拿到部分分數(shù)藍橋杯有部分分。最重要的是保持穩(wěn)定的心態(tài)一道題的失利不影響全局。