藍橋杯備賽學習筆記：高頻考點與真題預測（C++/Java/python版）

2025藍橋杯備賽學習筆記

——高頻考點與真題預測

一、考察趨勢分析

通過對第13-15屆藍橋杯真題的分析，可以發現題目主要圍繞基礎算法、數據結構、數學問題、字符串處理、編程語言基礎展開，且近年逐漸增加動態規劃、圖論、貪心算法等較難題目。

1. 基礎算法（必考）

排序與查找
- 快速排序、歸并排序（手寫實現）
- 二分查找（變種題，如旋轉數組查找）
搜索算法
- DFS（回溯、排列組合）
- BFS（最短路徑、層序遍歷）
貪心算法
- 區間調度、背包問題（部分背包）
動態規劃（重點）
- 背包問題（01背包、完全背包）
- 最長公共子序列（LCS）
- 股票買賣問題（變種DP）

2. 數據結構（必考）

線性表
- 數組（前綴和、差分數組）
- 鏈表（反轉、快慢指針）
樹與二叉樹
- 二叉搜索樹（BST）的插入、刪除
- 平衡二叉樹（AVL、紅黑樹概念）
圖論
- 最短路徑（Dijkstra、Floyd）
- 最小生成樹（Prim、Kruskal）
棧與隊列
- 單調棧（接雨水、柱狀圖最大矩形）
- 隊列（BFS、滑動窗口）

3. 數學問題（常考）

數論
- 素數篩（埃氏篩、歐拉篩）
- 最大公約數（GCD）、最小公倍數（LCM）
組合數學
- 排列組合（卡特蘭數、容斥原理）
位運算
- 異或性質、狀態壓縮（子集枚舉）

4. 字符串處理（常考）

字符串匹配
- KMP算法（模式匹配）
- 字典樹（Trie）
字符串操作
- 反轉、子串查找、回文判斷

5. 編程語言基礎（C++/Java）

語法基礎
- 變量、循環、遞歸
文件操作
- 讀寫文件（藍橋杯常考）
輸入輸出優化
- C++ scanf/printf vs cin/cout（關閉同步流）

二、預測題目與解題思路

1. 算法類

題目1：最大子數組和（動態規劃）

描述：給定一個整數數組 nums，找到和最大的連續子數組。
解題思路：

C++：

#include <vector>
#include <algorithm>
using namespace std;int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n);dp[0] = nums[0];int res = dp[0];for (int i = 1; i < n; i++) {dp[i] = max(nums[i], dp[i-1] + nums[i]);res = max(res, dp[i]);}return res;
}

Java：

public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];int res = dp[0];for (int i = 1; i < n; i++) {dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);res = Math.max(res, dp[i]);}return res;
}

Python：

def maxSubArray(nums):dp = [0] * len(nums)dp[0] = nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i-1] + nums[i])return max(dp)

變種：如果數組是環形的（首尾相連），如何計算？

題目2：最短路徑（Dijkstra算法）

描述：給定帶權圖，求從 start 到 end 的最短路徑。
解題思路：

C++：

#include <vector>
#include <queue>
#include <climits>
using namespace std;vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {int n = graph.size();vector<int> dist(n, INT_MAX);dist[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;pq.push({0, start});while (!pq.empty()) {auto [current_dist, u] = pq.top();pq.pop();if (current_dist > dist[u]) continue;for (auto [v, w] : graph[u]) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.push({dist[v], v});}}}return dist;
}

Java：

import java.util.*;public int[] dijkstra(List<List<int[]>> graph, int start) {int n = graph.size();int[] dist = new int[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[start] = 0;PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);pq.offer(new int[]{0, start});while (!pq.isEmpty()) {int[] curr = pq.poll();int u = curr[1], currentDist = curr[0];if (currentDist > dist[u]) continue;for (int[] edge : graph.get(u)) {int v = edge[0], w = edge[1];if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.offer(new int[]{dist[v], v});}}}return dist;
}

Python：

import heapq
def dijkstra(graph, start):heap = [(0, start)]dist = {node: float('inf') for node in graph}dist[start] = 0while heap:current_dist, u = heapq.heappop(heap)if current_dist > dist[u]:continuefor v, w in graph[u].items():if dist[v] > dist[u] + w:dist[v] = dist[u] + wheapq.heappush(heap, (dist[v], v))return dist

2. 數據結構類

題目3：二叉搜索樹的插入與刪除

描述：實現BST的插入和刪除操作。
解題思路：

C++：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};TreeNode* insert(TreeNode* root, int val) {if (!root) return new TreeNode(val);if (val < root->val) root->left = insert(root->left, val);else root->right = insert(root->right, val);return root;
}

Java：

class TreeNode {int val;TreeNode left, right;TreeNode(int x) { val = x; }
}public TreeNode insert(TreeNode root, int val) {if (root == null) return new TreeNode(val);if (val < root.val) root.left = insert(root.left, val);else root.right = insert(root.right, val);return root;
}

`Python：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef insert(root, val):if not root:return TreeNode(val)if val < root.val:root.left = insert(root.left, val)else:root.right = insert(root.right, val)return root

題目4：最長回文子串（動態規劃/中心擴展）

描述：給定字符串 s，返回最長回文子串。
解題思路：

C++：

string longestPalindrome(string s) {int n = s.size();int start = 0, maxLen = 1;auto expand = [&](int l, int r) {while (l >= 0 && r < n && s[l] == s[r]) {if (r - l + 1 > maxLen) {maxLen = r - l + 1;start = l;}l--; r++;}};for (int i = 0; i < n; i++) {expand(i, i);     // 奇數長度expand(i, i+1);   // 偶數長度}return s.substr(start, maxLen);
}

Java：

public String longestPalindrome(String s) {int n = s.length();int start = 0, maxLen = 1;for (int i = 0; i < n; i++) {expand(s, i, i);     // 奇數長度expand(s, i, i+1);   // 偶數長度}return s.substring(start, start + maxLen);
}private void expand(String s, int l, int r) {while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {if (r - l + 1 > maxLen) {maxLen = r - l + 1;start = l;}l--; r++;}
}

Python：

def longestPalindrome(s):n = len(s)dp = [[False] * n for _ in range(n)]res = ""for i in range(n-1, -1, -1):for j in range(i, n):if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):dp[i][j] = Trueif j - i + 1 > len(res):res = s[i:j+1]return res

3. 數學問題類

題目5：數字1的個數（數位DP）

描述：計算 1~n 中數字 1 出現的次數。
解題思路：

C++：

int countDigitOne(int n) {int count = 0;for (long i = 1; i <= n; i *= 10) {long divider = i * 10;count += (n / divider) * i + min(max(n % divider - i + 1, 0L), i);}return count;
}

Java：

public int countDigitOne(int n) {int count = 0;for (long i = 1; i <= n; i *= 10) {long divider = i * 10;count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);}return count;
}

Python：

def countDigitOne(n):count = 0i = 1while i <= n:divider = i * 10count += (n // divider) * i + min(max(n % divider - i + 1, 0), i)i *= 10return count

題目6：階乘計算（大數處理）

描述：計算 n!（n 可能很大，如 1000!）。
解題思路：
```
def factorial(n):res = 1for i in range(1, n+1):res *= ireturn res
```
- 優化：如果 n 很大，使用 math.factorial 或高精度計算（如Python默認支持大整數）。

4. 字符串處理類

題目7：判斷回文串（雙指針）

描述：判斷字符串 s 是否是回文。
解題思路：

C++：

bool isPalindrome(string s) {int left = 0, right = s.size() - 1;while (left < right) {if (s[left++] != s[right--]) return false;}return true;
}

Java：

public boolean isPalindrome(String s) {int left = 0, right = s.length() - 1;while (left < right) {if (s.charAt(left++) != s.charAt(right--)) return false;}return true;
}

Python：

def isPalindrome(s):left, right = 0, len(s)-1while left < right:if s[left] != s[right]:return Falseleft += 1right -= 1return True

題目8：子序列判斷（雙指針）

描述：判斷 s 是否是 t 的子序列。

解題思路：

def isSubsequence(s, t):i, j = 0, 0while i < len(s) and j < len(t):if s[i] == t[j]:i += 1j += 1return i == len(s)

三、備考策略

刷題優先級
- 必刷：動態規劃（背包、LCS）、DFS/BFS、Dijkstra、二分查找。
- 次重點：數論（素數篩、GCD）、字符串（KMP、回文）。
- 保底題：文件操作、遞歸、基礎語法。
時間分配建議
- 填空題（5題）：10分鐘/題（數學、模擬題為主）。
- 編程題（5題）：前2題暴力解法（30分鐘），后3題優化（60分鐘）。
調試技巧
- 對拍：用暴力算法驗證優化算法的正確性。
- 邊界測試：n=0、n=1e5 等極端情況。