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