1. 賽題回顧與整體策略復(fù)盤(pán)又到了一年一度復(fù)盤(pán)藍(lán)橋杯的時(shí)候。作為一項(xiàng)在國(guó)內(nèi)高校計(jì)算機(jī)相關(guān)專業(yè)中頗具影響力的賽事藍(lán)橋杯Java組的題目向來(lái)以“基礎(chǔ)扎實(shí)、思維靈活、貼近應(yīng)用”著稱。2022年的第十三屆省賽Java B組整體難度保持了其一貫的風(fēng)格前幾道題考察基本功中間部分考驗(yàn)算法思維和編碼實(shí)現(xiàn)最后幾題則是綜合能力的試金石。很多同學(xué)考完后感覺(jué)“會(huì)做但沒(méi)全對(duì)”或者“思路有但代碼寫(xiě)不出來(lái)”這恰恰反映了從“知道”到“熟練寫(xiě)出無(wú)Bug代碼”之間的鴻溝。這篇復(fù)盤(pán)我將結(jié)合當(dāng)年的題目不僅給出解題思路更會(huì)深入剖析編碼實(shí)現(xiàn)中的那些“坑”以及如何構(gòu)建一套穩(wěn)健的解題策略。無(wú)論你是即將參賽的選手還是想通過(guò)真題提升算法能力的開(kāi)發(fā)者希望這些從實(shí)戰(zhàn)中沉淀下來(lái)的經(jīng)驗(yàn)?zāi)軐?duì)你有所啟發(fā)。2. 基礎(chǔ)題穩(wěn)扎穩(wěn)打的“送分”環(huán)節(jié)省賽的開(kāi)局幾道題通常旨在幫助選手熱身并建立信心但“送分題”不等于“白給題”細(xì)節(jié)決定成敗。2.1 日期計(jì)算與進(jìn)制轉(zhuǎn)換類這類題目通常直接但要求絕對(duì)的準(zhǔn)確性和對(duì)API的熟悉度。例如可能有一題要求計(jì)算從某年某月某日到另一日期的天數(shù)差。核心陷阱在于對(duì)閏年的判斷和月份天數(shù)的處理。很多同學(xué)會(huì)自己手寫(xiě)判斷邏輯這固然可以但更容易出錯(cuò)。更穩(wěn)健的做法是直接使用Java標(biāo)準(zhǔn)庫(kù)中的java.time.LocalDate類。這個(gè)類在Java 8引入完美處理了歷法復(fù)雜性。import java.time.LocalDate; import java.time.temporal.ChronoUnit; public class DateCalculation { public static void main(String[] args) { LocalDate start LocalDate.of(1949, 10, 1); LocalDate end LocalDate.of(2022, 4, 9); long days ChronoUnit.DAYS.between(start, end); System.out.println(days); } }實(shí)操心得在競(jìng)賽環(huán)境中雖然java.time包非?？煽康珓?wù)必確認(rèn)比賽環(huán)境支持的Java版本。絕大多數(shù)情況下藍(lán)橋杯環(huán)境已支持Java 8。使用標(biāo)準(zhǔn)庫(kù)能極大減少邊界條件錯(cuò)誤如2月、大小月把精力留給更復(fù)雜的題目。另一類基礎(chǔ)題是進(jìn)制轉(zhuǎn)換比如將十進(jìn)制數(shù)轉(zhuǎn)換為七進(jìn)制后求各位數(shù)字之和。這里的關(guān)鍵是掌握“除基取余法”的循環(huán)寫(xiě)法并注意處理數(shù)字0的情況。public static int sumInBase7(int n) { if (n 0) return 0; // 易漏點(diǎn)輸入為0時(shí)循環(huán)不會(huì)執(zhí)行需要單獨(dú)處理 int sum 0; while (n 0) { sum n % 7; // 取余得到當(dāng)前最低位 n / 7; // 去掉已處理的最低位 } return sum; }避坑提示循環(huán)條件while (n 0)在輸入為0時(shí)會(huì)直接跳過(guò)導(dǎo)致返回錯(cuò)誤的0如果題目要求0的各位和是0則正確但有時(shí)題目語(yǔ)境下0的轉(zhuǎn)換結(jié)果“0”的各位和也是0邏輯上一致。最安全的做法是像上面一樣顯式判斷或者在循環(huán)中使用do-while結(jié)構(gòu)但要注意do-while在n0時(shí)也會(huì)執(zhí)行一次需要根據(jù)題意調(diào)整。2.2 字符串處理與模擬字符串操作是Java的強(qiáng)項(xiàng)也是高頻考點(diǎn)。題目可能涉及統(tǒng)計(jì)特定字符出現(xiàn)次數(shù)、字符串翻轉(zhuǎn)、子串查找等。這里容易失分的地方在于對(duì)輸入數(shù)據(jù)的處理。例如題目要求讀入一行可能包含空格的字符串進(jìn)行處理。如果簡(jiǎn)單地使用Scanner.next()它會(huì)以空格為分隔符無(wú)法讀取整行。正確的做法是Scanner sc new Scanner(System.in); // 在讀取數(shù)字后如果需要讀取后續(xù)行要注意吸收換行符 int n sc.nextInt(); sc.nextLine(); // 吸收掉數(shù)字后的換行符這是非常關(guān)鍵的步驟。 String line sc.nextLine(); // 現(xiàn)在可以正確讀取整行字符串經(jīng)驗(yàn)之談在混合使用nextInt(),nextDouble()和nextLine()時(shí)忘記“吸收換行符”是新手最常犯的錯(cuò)誤之一。養(yǎng)成一個(gè)習(xí)慣在每次使用nextLine()讀取字符串前如果前面有用其他nextXxx()方法就先調(diào)用一次sc.nextLine()來(lái)清空緩沖區(qū)。模擬題則更考驗(yàn)細(xì)心程度比如根據(jù)一套復(fù)雜的規(guī)則生成或變換數(shù)據(jù)。我的建議是先完全理解題意用注釋在代碼里把規(guī)則一、二、三寫(xiě)清楚然后分步驟實(shí)現(xiàn)每實(shí)現(xiàn)一步就輸出中間結(jié)果進(jìn)行驗(yàn)證。不要試圖一口氣寫(xiě)出全部邏輯拆解是降低調(diào)試難度的不二法門(mén)。3. 算法思維枚舉、排序與查找的實(shí)戰(zhàn)應(yīng)用省賽的中段題目開(kāi)始考察經(jīng)典的算法思想。雖然不涉及特別高深的數(shù)據(jù)結(jié)構(gòu)但對(duì)時(shí)間復(fù)雜度的估算和優(yōu)化意識(shí)至關(guān)重要。3.1 暴力枚舉與優(yōu)化剪枝“枚舉”是解決許多問(wèn)題的樸素而有效的方法但直接蠻干很可能超時(shí)。例如一道題可能要求找到在1到N中有多少個(gè)數(shù)滿足其各位數(shù)字的某種性質(zhì)如是遞增的。最直接的方法是遍歷1到N對(duì)每個(gè)數(shù)判斷。int count 0; for (int i 1; i N; i) { if (check(i)) { // check函數(shù)判斷數(shù)字i是否滿足條件 count; } }當(dāng)N很大比如10^9時(shí)上述線性枚舉必然超時(shí)。這時(shí)就需要優(yōu)化。優(yōu)化枚舉的核心思路有兩個(gè)減少枚舉范圍和避免重復(fù)計(jì)算。以“遞增數(shù)”為例一個(gè)重要的觀察是滿足條件的數(shù)其實(shí)并不多在十進(jìn)制下各位數(shù)字遞增的組合數(shù)是有限的可以用深度優(yōu)先搜索DFS來(lái)生成所有可能的遞增數(shù)然后統(tǒng)計(jì)在N以內(nèi)的個(gè)數(shù)。這樣我們枚舉的不再是1到N的所有數(shù)而是所有“可能”的遞增數(shù)數(shù)量級(jí)從N10^9降到了C(9len, len)級(jí)別對(duì)于位數(shù)不超過(guò)10的數(shù)這個(gè)組合數(shù)很小。解題框架示例DFS生成遞增數(shù)static long N; static int count 0; static void dfs(long currentNum, int lastDigit) { if (currentNum N) return; if (currentNum 0) count; // 當(dāng)前生成的數(shù)有效且不超過(guò)N for (int d lastDigit; d 9; d) { // 保證下一位數(shù)字不小于前一位 dfs(currentNum * 10 d, d); } } public static void main(String[] args) { Scanner sc new Scanner(System.in); N sc.nextLong(); dfs(0, 1); // 從第一位開(kāi)始不能以0開(kāi)頭除非題目允許0 System.out.println(count); }關(guān)鍵點(diǎn)分析lastDigit參數(shù)確保了生成的數(shù)字序列是非遞減的。currentNum 0的判斷是為了排除初始狀態(tài)0被計(jì)入。這是一個(gè)典型的通過(guò)改變枚舉對(duì)象從所有自然數(shù)變?yōu)椤昂戏ā睌?shù)字來(lái)極大降低復(fù)雜度的案例。3.2 排序與自定義比較器排序是基礎(chǔ)算法但藍(lán)橋杯喜歡考自定義排序規(guī)則。Java中使用Arrays.sort()或Collections.sort()時(shí)傳入自定義的Comparator即可。假設(shè)題目要求對(duì)一組字符串進(jìn)行排序規(guī)則是首先按長(zhǎng)度升序長(zhǎng)度相同的按字典序降序。很多同學(xué)知道要用Comparator但寫(xiě)起來(lái)容易出錯(cuò)。String[] arr ...; Arrays.sort(arr, new ComparatorString() { Override public int compare(String s1, String s2) { // 第一優(yōu)先級(jí)長(zhǎng)度 if (s1.length() ! s2.length()) { return s1.length() - s2.length(); // 長(zhǎng)度升序 } // 第二優(yōu)先級(jí)字典序降序 return s2.compareTo(s1); // 注意這里是s2.compareTo(s1)實(shí)現(xiàn)降序 } });易錯(cuò)點(diǎn)提醒compare方法的返回值負(fù)數(shù)表示s1應(yīng)排在s2前面正數(shù)表示s1應(yīng)排在s2后面0表示相等。所以s1.length() - s2.length()實(shí)現(xiàn)的是長(zhǎng)度升序。字典序降序不能寫(xiě)成-s1.compareTo(s2)。雖然這在大多數(shù)情況下可行但如果s1.compareTo(s2)的結(jié)果是Integer.MIN_VALUE取負(fù)會(huì)導(dǎo)致溢出產(chǎn)生錯(cuò)誤結(jié)果。最安全的寫(xiě)法就是s2.compareTo(s1)。使用Lambda表達(dá)式Java 8可以更簡(jiǎn)潔Arrays.sort(arr, (s1, s2) - s1.length() ! s2.length() ? s1.length() - s2.length() : s2.compareTo(s1));對(duì)于對(duì)象數(shù)組的排序原理相同在Comparator中定義好多級(jí)比較的邏輯即可。4. 動(dòng)態(tài)規(guī)劃與狀態(tài)設(shè)計(jì)從經(jīng)典模型到變種動(dòng)態(tài)規(guī)劃DP是藍(lán)橋杯省賽乃至國(guó)賽的必考題型也是區(qū)分度所在。2022年的題目中很可能包含一道經(jīng)典的DP變種題。4.1 線性DP最長(zhǎng)上升子序列LIS的變體最長(zhǎng)上升子序列LIS是DP的入門(mén)經(jīng)典。其標(biāo)準(zhǔn)O(n^2)解法是定義dp[i]為以第i個(gè)元素結(jié)尾的最長(zhǎng)上升子序列長(zhǎng)度狀態(tài)轉(zhuǎn)移方程為dp[i] max(dp[j]) 1其中j i且arr[j] arr[i]。省賽題目往往不會(huì)直接考標(biāo)準(zhǔn)LIS而是加以變化。例如“最大上升子序列和”求一個(gè)上升子序列使得其元素之和最大。此時(shí)dp[i]的定義就需要從“長(zhǎng)度”變?yōu)椤耙詀rr[i]結(jié)尾的最大上升子序列和”。int[] arr ...; // 輸入數(shù)組 int n arr.length; int[] dp new int[n]; // dp[i]以arr[i]結(jié)尾的最大上升子序列和 int maxSum arr[0]; // 初始化不能是0因?yàn)樾蛄泻涂赡転樨?fù) for (int i 0; i n; i) { dp[i] arr[i]; // 初始化為自身最短子序列就是它自己 for (int j 0; j i; j) { if (arr[j] arr[i]) { dp[i] Math.max(dp[i], dp[j] arr[i]); } } maxSum Math.max(maxSum, dp[i]); } System.out.println(maxSum);狀態(tài)設(shè)計(jì)的心得DP最難也最關(guān)鍵的一步就是定義狀態(tài)。一個(gè)好的狀態(tài)定義應(yīng)該具備兩個(gè)特點(diǎn)1)無(wú)后效性當(dāng)前狀態(tài)的值一旦確定后續(xù)的決策不再受之前如何到達(dá)此狀態(tài)的影響。2)能夠覆蓋所有情況。像上面這道題如果定義dp[i]為前i個(gè)元素中的最大上升子序列和狀態(tài)轉(zhuǎn)移就會(huì)很困難因?yàn)椴恢雷詈笠粋€(gè)元素是誰(shuí)無(wú)法判斷能否接上arr[i]。而以arr[i]結(jié)尾就固定了子序列的終點(diǎn)轉(zhuǎn)移邏輯變得清晰。4.2 背包DP及其應(yīng)用場(chǎng)景01背包和完全背包是另一大類考點(diǎn)。01背包的核心代碼模板必須爛熟于心int[] dp new int[V 1]; // dp[j] 表示容量為j的背包能裝的最大價(jià)值 for (int i 0; i n; i) { // 遍歷物品 int weight weights[i]; int value values[i]; for (int j V; j weight; j--) { // 01背包逆序枚舉容量 dp[j] Math.max(dp[j], dp[j - weight] value); } }省賽題目可能會(huì)將其包裝成一個(gè)實(shí)際問(wèn)題比如“預(yù)算采購(gòu)”、“資源分配”等。關(guān)鍵是將問(wèn)題抽象成背包模型什么是“物品”通常是一個(gè)可選擇的方案或?qū)ο笫裁词恰爸亓俊蓖ǔＪ谴鷥r(jià)如價(jià)格、時(shí)間什么是“價(jià)值”要最大化的目標(biāo)如滿意度、性能。一個(gè)常見(jiàn)的變形是“恰好裝滿”背包。初始化時(shí)只有dp[0]0其他dp[j]初始化為一個(gè)代表“不可能”的值如-INF。這樣最終dp[V]如果大于等于0就表示恰好裝滿容量V的最大價(jià)值如果仍是-INF則表示無(wú)法恰好裝滿。int[] dp new int[V 1]; Arrays.fill(dp, -INF); dp[0] 0; for (int i 0; i n; i) { for (int j V; j weight[i]; j--) { if (dp[j - weight[i]] ! -INF) { // 只有前一個(gè)狀態(tài)是可達(dá)的才能轉(zhuǎn)移 dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]); } } } if (dp[V] 0) { System.out.println(dp[V]); } else { System.out.println(無(wú)法恰好裝滿); }5. 搜索與圖論DFS/BFS的靈活運(yùn)用對(duì)于排列組合、路徑查找、連通塊等問(wèn)題深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS是利器。5.1 深度優(yōu)先搜索DFS與回溯DFS常用于生成所有可能的排列、組合或者遍歷樹(shù)/圖的所有路徑。在藍(lán)橋杯的“填空題”或“代碼填空題”中經(jīng)常需要補(bǔ)全DFS的代碼。一個(gè)典型的全排列DFS框架static int n; static int[] path; // 記錄當(dāng)前路徑 static boolean[] used; // 記錄數(shù)字是否被使用過(guò) static ListListInteger result new ArrayList(); static void dfs(int depth) { if (depth n) { // 到達(dá)葉子節(jié)點(diǎn)得到一個(gè)排列 // 將當(dāng)前path的拷貝加入結(jié)果集注意不能直接加path因?yàn)閜ath會(huì)被修改 ListInteger temp new ArrayList(); for (int num : path) temp.add(num); result.add(temp); return; } for (int i 1; i n; i) { if (!used[i]) { // 數(shù)字i未被使用 used[i] true; path[depth] i; // 選擇數(shù)字i dfs(depth 1); // 遞歸進(jìn)入下一層 used[i] false; // 回溯撤銷(xiāo)選擇 } } }回溯的要點(diǎn)在遞歸調(diào)用返回后必須將狀態(tài)恢復(fù)到調(diào)用前的樣子這里是used[i] false這樣才能保證在生成其他分支時(shí)選擇是公平的。這是DFS算法中極易忘記的一步。5.2 廣度優(yōu)先搜索BFS與最短路徑BFS以其“層層推進(jìn)”的特性天然適合求解“最短步數(shù)”、“最少操作次數(shù)”等問(wèn)題。在二維網(wǎng)格迷宮中尋找最短路徑是經(jīng)典場(chǎng)景。// 假設(shè)網(wǎng)格為 grid[m][n], 0表示可通行1表示障礙 // 起點(diǎn) (startX, startY), 終點(diǎn) (endX, endY) int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四個(gè)方向 boolean[][] visited new boolean[m][n]; Queueint[] queue new LinkedList(); queue.offer(new int[]{startX, startY}); visited[startX][startY] true; int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { // 遍歷當(dāng)前層的所有節(jié)點(diǎn) int[] cur queue.poll(); int x cur[0], y cur[1]; if (x endX y endY) { System.out.println(steps); return; } for (int[] d : dirs) { int nx x d[0], ny y d[1]; // 檢查新坐標(biāo)是否合法、是否可通行、是否已訪問(wèn) if (nx 0 nx m ny 0 ny n grid[nx][ny] 0 !visited[nx][ny]) { visited[nx][ny] true; queue.offer(new int[]{nx, ny}); } } } steps; // 當(dāng)前層所有節(jié)點(diǎn)處理完畢步數(shù)加一 } System.out.println(-1); // 無(wú)法到達(dá)終點(diǎn)BFS實(shí)現(xiàn)細(xì)節(jié)使用隊(duì)列Java中常用LinkedList作為Queue的實(shí)現(xiàn)。記錄訪問(wèn)狀態(tài)visited數(shù)組必不可少防止走回頭路陷入無(wú)限循環(huán)。分層遍歷while循環(huán)內(nèi)的for循環(huán)用于處理同一“步數(shù)”下的所有節(jié)點(diǎn)這樣steps變量才能準(zhǔn)確記錄從起點(diǎn)到當(dāng)前層的距離。這是求最短步數(shù)的關(guān)鍵。提前終止一旦從隊(duì)列中取出的節(jié)點(diǎn)就是終點(diǎn)可以立即返回結(jié)果因?yàn)锽FS首次到達(dá)終點(diǎn)時(shí)的步數(shù)一定是最短的。6. 數(shù)論與數(shù)學(xué)問(wèn)題思維能力的試煉藍(lán)橋杯常會(huì)穿插一些需要數(shù)學(xué)思維或數(shù)論知識(shí)的題目它們往往代碼量不大但想到正確的思路是關(guān)鍵。6.1 最大公約數(shù)與最小公倍數(shù)歐幾里得算法輾轉(zhuǎn)相除法求最大公約數(shù)GCD必須熟練掌握public static int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }最小公倍數(shù)LCM可以通過(guò)GCD求得lcm(a, b) a * b / gcd(a, b)。注意這里潛在的整數(shù)溢出問(wèn)題如果a和b很大a * b可能會(huì)超出int范圍。安全的寫(xiě)法是先除后乘a / gcd(a, b) * b。一道綜合題可能要求求多個(gè)數(shù)的最大公約數(shù)或最小公倍數(shù)。思路是兩兩合并// 求數(shù)組arr中所有數(shù)的最大公約數(shù) int g arr[0]; for (int i 1; i arr.length; i) { g gcd(g, arr[i]); } // 求數(shù)組arr中所有數(shù)的最小公倍數(shù) long l arr[0]; // 使用long防止中間結(jié)果溢出 for (int i 1; i arr.length; i) { l l / gcd((int)l, arr[i]) * arr[i]; // 先除后乘 }6.2 質(zhì)數(shù)判斷與篩法判斷單個(gè)大數(shù)是否為質(zhì)數(shù)可以用試除法遍歷到sqrt(n)即可。public static boolean isPrime(int n) { if (n 2) return false; for (int i 2; i * i n; i) { // i*i n 比 i Math.sqrt(n) 效率稍高 if (n % i 0) return false; } return true; }如果需要找出一定范圍內(nèi)比如1到N的所有質(zhì)數(shù)埃拉托斯特尼篩法埃氏篩是更高效的選擇時(shí)間復(fù)雜度約為O(N log log N)。int N 1000000; boolean[] isPrime new boolean[N 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; for (int i 2; i * i N; i) { if (isPrime[i]) { // 從i*i開(kāi)始標(biāo)記因?yàn)?*i, 3*i, ..., (i-1)*i 已經(jīng)被更小的質(zhì)數(shù)標(biāo)記過(guò)了 for (int j i * i; j N; j i) { isPrime[j] false; } } } // 現(xiàn)在isPrime數(shù)組中為true的下標(biāo)就是質(zhì)數(shù)篩法的優(yōu)化細(xì)節(jié)內(nèi)層循環(huán)的起始點(diǎn)設(shè)為j i * i是一個(gè)重要優(yōu)化避免了重復(fù)標(biāo)記。例如當(dāng)i5時(shí)5*210已經(jīng)在i2時(shí)被標(biāo)記5*315已經(jīng)在i3時(shí)被標(biāo)記所以從5*525開(kāi)始標(biāo)記即可。7. 真題實(shí)戰(zhàn)拆解與編碼陷阱讓我們結(jié)合一道可能出現(xiàn)在2022年省賽中的綜合性題目根據(jù)常見(jiàn)考點(diǎn)推測(cè)來(lái)串聯(lián)上述知識(shí)點(diǎn)并重點(diǎn)分析編碼實(shí)現(xiàn)中的陷阱。假設(shè)題目給定一個(gè)N x M的網(wǎng)格每個(gè)格子有一個(gè)人他們需要參加一場(chǎng)活動(dòng)。活動(dòng)組織者決定每個(gè)人只能與他上下左右四個(gè)方向相鄰的人之一組隊(duì)每人只能屬于一個(gè)隊(duì)伍。問(wèn)在所有可能的組隊(duì)方案中使得所有隊(duì)伍“和諧度”之和最大的方案其和諧度總和是多少隊(duì)伍的“和諧度”定義為兩人編號(hào)的乘積。抽象與建模這本質(zhì)上是一個(gè)“二分圖最大權(quán)匹配”問(wèn)題但N和M較小比如10時(shí)可以用狀態(tài)壓縮DP或者DFS搜索來(lái)解決。這里我們探討DFS搜索方案。思路由于每個(gè)人只能和鄰居配對(duì)我們可以按某種順序例如從左到右、從上到下遍歷網(wǎng)格對(duì)于當(dāng)前格子的人有兩種選擇1) 不與他配對(duì)可能留給后面的鄰居2) 如果他的右側(cè)或下側(cè)鄰居未被配對(duì)則可以選擇與其中一個(gè)配對(duì)。我們需要搜索所有可能的配對(duì)方案計(jì)算總和諧度并取最大值。DFS實(shí)現(xiàn)與陷阱static int N, M; static int[][] grid; static boolean[][] paired; static int maxSum 0; static void dfs(int x, int y, int currentSum) { // 遞歸終止條件所有人都被考慮過(guò) if (x N) { maxSum Math.max(maxSum, currentSum); return; } // 計(jì)算下一個(gè)格子的坐標(biāo) int nextX x; int nextY y 1; if (nextY M) { nextX x 1; nextY 0; } // 情況1當(dāng)前格子的人已經(jīng)在前面的決策中被配對(duì)了作為別人的鄰居 if (paired[x][y]) { dfs(nextX, nextY, currentSum); return; } // 情況2當(dāng)前格子的人不主動(dòng)配對(duì)保持單身或者等待后面被配對(duì) // 注意如果他不主動(dòng)配對(duì)在后續(xù)的搜索中他仍然可能被他的右側(cè)或下側(cè)鄰居“主動(dòng)”配對(duì)。 // 但為了避免重復(fù)計(jì)算和復(fù)雜狀態(tài)更清晰的策略是規(guī)定配對(duì)順序比如只讓每個(gè)人嘗試與右側(cè)和下側(cè)鄰居配對(duì)且“主動(dòng)”方是當(dāng)前遍歷到的人。 // 這樣如果當(dāng)前人不配對(duì)他就永遠(yuǎn)保持未配對(duì)狀態(tài)。 dfs(nextX, nextY, currentSum); // 情況3嘗試與右側(cè)鄰居配對(duì)如果存在且未被配對(duì) if (y 1 M !paired[x][y 1]) { paired[x][y] paired[x][y 1] true; dfs(nextX, nextY, currentSum grid[x][y] * grid[x][y 1]); paired[x][y] paired[x][y 1] false; // 回溯 } // 情況4嘗試與下側(cè)鄰居配對(duì)如果存在且未被配對(duì) if (x 1 N !paired[x 1][y]) { paired[x][y] paired[x 1][y] true; dfs(nextX, nextY, currentSum grid[x][y] * grid[x 1][y]); paired[x][y] paired[x 1][y] false; // 回溯 } }陷阱分析配對(duì)順序與狀態(tài)定義上述代碼采用了“主動(dòng)配對(duì)”策略即只由當(dāng)前遍歷到的人(x, y)去嘗試配對(duì)其右、下鄰居。這保證了每種配對(duì)方案只被生成一次不會(huì)重復(fù)。如果允許“被動(dòng)配對(duì)”即后面的人來(lái)配前面的人狀態(tài)會(huì)非常復(fù)雜容易出錯(cuò)。回溯的完整性在嘗試配對(duì)后必須將paired數(shù)組恢復(fù)原狀paired[x][y] paired[鄰居] false這是DFS回溯法的核心。性能考慮當(dāng)網(wǎng)格較大時(shí)如10x10這種搜索的復(fù)雜度是指數(shù)級(jí)的可能會(huì)超時(shí)。這就需要用到更高級(jí)的算法如狀態(tài)壓縮DP或者剪枝優(yōu)化。但在省賽范圍內(nèi)如果N和M較小比如6DFS是可行的。起始調(diào)用在main函數(shù)中需要初始化paired數(shù)組為false然后從起點(diǎn)(0,0)開(kāi)始調(diào)用dfs(0, 0, 0)。這道題綜合了網(wǎng)格遍歷坐標(biāo)處理、DFS搜索、回溯、狀態(tài)記錄和最優(yōu)值更新是檢驗(yàn)選手綜合編碼能力的典型題目。在考場(chǎng)上先確保暴力搜索寫(xiě)對(duì)拿到基礎(chǔ)分再思考是否有優(yōu)化空間。8. 考場(chǎng)策略與調(diào)試技巧最后分享一些在藍(lán)橋杯賽場(chǎng)上的實(shí)戰(zhàn)經(jīng)驗(yàn)。時(shí)間分配通常省賽有10道左右題目。建議用前1小時(shí)快速瀏覽所有題目按“一眼就有思路”、“需要思考”、“完全沒(méi)思路”進(jìn)行分類。先做“一眼題”建立信心并確?；A(chǔ)分。然后主攻“需要思考”的題。最后如果有時(shí)間再挑戰(zhàn)難題。輸入輸出優(yōu)化對(duì)于大數(shù)據(jù)量的題目使用Scanner可能會(huì)比較慢。雖然藍(lán)橋杯評(píng)測(cè)機(jī)性能尚可但養(yǎng)成好習(xí)慣是有益的?？梢允褂肂ufferedReader和StringTokenizer進(jìn)行快速讀取。import java.io.*; import java.util.*; public class Main { static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static String next() throws IOException { while (st null || !st.hasMoreTokens()) { st new StringTokenizer(br.readLine()); } return st.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt(next()); } public static void main(String[] args) throws IOException { int n nextInt(); // ... 其他邏輯 } }調(diào)試與驗(yàn)證使用樣例題目給的樣例一定要跑通并且要自己構(gòu)造一些邊界情況的樣例如最小輸入、最大輸入、結(jié)果為0的情況。打印中間變量在關(guān)鍵步驟后打印變量值是定位邏輯錯(cuò)誤最直接的方法。提交前記得注釋掉或刪除這些調(diào)試輸出。靜態(tài)檢查寫(xiě)完代碼后花幾分鐘靜態(tài)檢查循環(huán)邊界是否正確是還是數(shù)組下標(biāo)是否可能越界遞歸終止條件是否完備全局變量在多組數(shù)據(jù)輸入時(shí)是否重置。心態(tài)管理遇到卡殼的題目如果思考10-15分鐘仍無(wú)進(jìn)展果斷跳過(guò)去做其他題。很多時(shí)候在做其他題的過(guò)程中可能會(huì)突然對(duì)之前的難題產(chǎn)生靈感。比賽是總分制確保能拿的分都拿到遠(yuǎn)比死磕一道題重要。編程競(jìng)賽尤其是像藍(lán)橋杯這樣偏向基礎(chǔ)和思維的比賽扎實(shí)的基本功、清晰的邏輯和穩(wěn)定的心態(tài)是取勝的關(guān)鍵。通過(guò)大量練習(xí)歷年真題熟悉各種題型和陷阱總結(jié)出自己的解題模板和錯(cuò)題本才能在賽場(chǎng)上游刃有余。希望這份針對(duì)2022年省賽的復(fù)盤(pán)與拓展能幫助你不僅看懂題解更能理解題目背后的思維邏輯和編碼實(shí)踐中那些微妙的細(xì)節(jié)從而在未來(lái)的比賽中寫(xiě)出既正確又優(yōu)雅的代碼。