2016 藍橋杯省賽題解回顧：DFS、貪心與二分綜合應用

比賽概況

2016 年藍橋杯省賽，題目以 DFS、貪心、動態規劃為主，難度中等。以下為關鍵題目解法回顧。

題目 1：撕郵票（枚舉子集 + 連通性判斷）

在 5×5 格子中選 5 個相連格子。利用二進制枚舉 25 格子的所有子集（2^25 約 3300 萬，可行），預處理鄰接關係，判斷子集內格子是否連通（BFS/DFS）。

題目 2：3×4 缺角方格填數（DFS + 去重）

典型回溯搜索，按順序填入數字，剪枝條件：行/列/宮無重複。對稱解去重可用哈希集合存儲標準化字符串。

題目 3：代碼補全（快排 + DFS）

閱讀不完整代碼，補全關鍵行。可先複製代碼本地運行樣例，對照輸出推斷邏輯。

大題 1：四數平方和（兩數和預處理 + 二分）

預處理所有兩數之和及其平方和存入結構體數組，按平方和、第一數、第二數排序。枚舉前兩數，二分查找匹配的後兩數。複雜度 O(n^2 log n)。

大題 2：貪心經典（紫書第八章習題原題）

具體模型為區間調度或資源分配，按結束時間/單位價值排序貪心選擇。

大題 3：相鄰比值迭代（O(n²) 模擬）

每輪計算相鄰元素比值形成新序列，長度減 1，重複至剩一個數。直接模擬即可，數據範圍允許 O(n²)。

心得

• 基礎算法（DFS、BFS、貪心、二分、DP）靈活組合是關鍵。
• 代碼補全題考察對標準算法模板的熟悉度。
• 比賽中優先攻克有把握的題目，大題可通過部分分策略得分。