蓝桥杯算法竞赛核心模板：从原理到实战的完整指南

1. 蓝桥杯竞赛与“模板”的实战价值

如果你正在准备蓝桥杯，或者任何类似的算法竞赛，那你一定听过“模板”这个词。它听起来像是一把万能钥匙，似乎掌握了它就能打开所有题目的大门。但在我带过几届学生、自己也从参赛者走到指导者的经历里，我发现很多人对“模板”的理解是片面的，甚至是危险的。它绝不是让你去死记硬背几百行代码，然后在考场上生搬硬套。真正的“常用模板”，是一套经过千锤百炼的、针对特定问题模型的标准化思考框架与代码实现骨架。它的核心价值在于，当你识别出一个问题属于某个经典模型（比如最短路径、动态规划、并查集）时，它能帮你跳过底层实现的纠结，直接聚焦于问题本身的建模与变形。

为什么这如此重要？蓝桥杯的赛制，尤其是省赛和国赛，题目往往在经典算法上包裹一层巧妙的“外衣”，或者将多个知识点融合。比赛时间有限，压力巨大。如果你每遇到一个“图论”问题，都要从头思考邻接表怎么建、优先队列怎么用，时间早就溜走了。而一个可靠的模板，就像你工具箱里那把最称手的螺丝刀，你知道它的长度、握感、扭矩，遇到螺丝你就能立刻上手，省下的是最宝贵的、用于创造性思考的时间。所以，我们今天聊的“常用模板”，不是网上随便下载的一个代码文件，而是融合了问题识别、算法选择、边界处理、调试技巧的一整套方法论。接下来，我会分几个核心板块，拆解那些真正高频、实用，且必须理解其内在原理的模板，并分享我在实战中积累的“私货”心得。

2. 基础数据结构模板：一切算法的基石

在讨论高深的算法之前，我们必须确保基础数据结构的操作像呼吸一样自然。这部分模板的特点是短小精悍，但使用频率极高，几乎每道题都会间接用到。

2.1 快速输入输出模板（C++）

这是影响程序“物理时间”的第一个瓶颈。当数据量达到1e5级别以上时，cin/cout与scanf/printf的速度差异会被放大，更不用说endl导致的频繁缓冲刷新了。

#include <bits/stdc++.h> using namespace std; // 适用于正负整数的快速读入 inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); // 等价于 x = x * 10 + ch - '0' ch = getchar(); } return x * f; } // 适用于正负整数的快速输出 inline void write(int x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } int main() { int n = read(); write(n); return 0; }

核心要点与避坑：

1. 为什么用inline和getchar()？inline建议编译器内联这个小函数，减少调用开销。getchar()是C标准库函数，单字符读取，效率远高于格式化输入。
2. (x << 1) + (x << 3)是x * 10的位运算优化，在竞赛中常用，但现代编译器对*10的优化已经很好，可读性优先时直接用乘法也行。
3. 更通用的做法：对于蓝桥杯，更稳妥且省事的做法是直接关闭cin/cout的同步流，并取消cin与stdio的绑定，这能使其速度接近scanf。

   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 之后可以愉快地使用 cin, cout，但切记不能与 scanf, printf 混用！

4. 最大的坑：一旦使用了ios::sync_with_stdio(false)，C++ 流和 C 标准 IO 流将不再同步，绝对不要再将cin/cout与scanf/printf混合使用，否则会导致输入输出顺序混乱，这是新手最容易栽跟头的地方之一。

2.2 并查集 (Union-Find) 模板

并查集是处理“动态连通性”问题的神器，如判断图中两点是否连通、朋友圈归类、最小生成树Kruskal算法等。其核心在于“查”（Find）与“并”（Union）的高效实现。

class DSU { private: vector<int> parent; vector<int> rank; // 或 size，用于优化 public: DSU(int n) : parent(n), rank(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; // 初始化，每个节点自成一派 } // 查找根节点，带路径压缩 int find(int x) { // 普通递归写法 // return parent[x] == x ? x : find(parent[x]); // 路径压缩优化写法 if (parent[x] != x) { parent[x] = find(parent[x]); // 递归找到根，并直接挂到根下 } return parent[x]; // 迭代写法（避免递归深度问题） // while (parent[x] != x) { // parent[x] = parent[parent[x]]; // 路径压缩 // x = parent[x]; // } // return x; } // 合并两个集合，按秩合并 void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 已在同一集合 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; // 秩相等时，被挂接的根秩增加 } // 如果使用size优化，则总是将小的集合合并到大的集合 } bool connected(int x, int y) { return find(x) == find(y); } };

核心要点与避坑：

1. “路径压缩”与“按秩合并”：这是保证并查集操作均摊时间复杂度接近 O(α(n))（阿克曼函数的反函数，近乎常数）的关键。两者同时使用效果最佳。rank表示树的高度上界，不是精确高度。用size（集合元素个数）优化也是常见策略。
2. 初始化数量：构造函数中的n是节点的总数量，通常节点编号从0或1开始。务必确保n的大小足够，否则会越界。
3. 典型应用场景：
   • 判断图中是否有环：在逐边合并时，如果发现边的两个端点已经连通，则说明加入这条边会形成环。
   • Kruskal算法：对所有边按权重排序后，依次尝试合并边两端的节点，成功合并则加入生成树。
   • 动态连通性问题：如“网络连接”、“亲戚关系”。
4. 易错点：在unite函数中，务必使用find(x)和find(y)的结果（即根节点）来进行合并判断和操作，而不是直接使用x和y。

3. 图论算法模板：化繁为简的导航图

图论是蓝桥杯的重中之重，从简单的遍历到复杂的最短路、最小生成树，模板的清晰与否直接决定解题速度。

3.1 图的存储模板

“工欲善其事，必先利其器”。根据图的特点（稠密/稀疏、有无权值）选择正确的存储方式，是写好后续算法的第一步。

邻接矩阵：适合稠密图或需要快速判断两点间是否有边的场景。

const int MAXN = 1005; int graph[MAXN][MAXN]; // graph[i][j] 表示边(i, j)的权值，INF表示无边 void init() { memset(graph, 0x3f, sizeof(graph)); // 初始化为“无穷大” for (int i = 0; i < MAXN; ++i) graph[i][i] = 0; }

邻接表（vector实现）：最常用，适合稀疏图，节省空间。

const int MAXN = 100005; struct Edge { int to; // 边的终点 int weight; // 边权 // 可以添加其他属性，如next（用于链式前向星） }; vector<Edge> adj[MAXN]; // adj[u] 存储从u出发的所有边 void addEdge(int u, int v, int w) { adj[u].push_back({v, w}); // 如果是无向图，需要添加反向边 // adj[v].push_back({u, w}); }

链式前向星：另一种高效的邻接表，尤其适合需要边编号（如网络流）的场景，但写法稍复杂。

const int MAXN = 100005, MAXM = 200005; // 注意无向图边数要*2 struct Edge { int to, next, weight; } edges[MAXM]; int head[MAXN], edgeCnt = 0; void addEdge(int u, int v, int w) { edges[++edgeCnt] = {v, head[u], w}; head[u] = edgeCnt; } // 遍历u的所有出边 for (int i = head[u]; i; i = edges[i].next) { int v = edges[i].to, w = edges[i].weight; // 处理边(u, v) }

选择建议：对于蓝桥杯，优先掌握vector实现的邻接表，它直观、易写，在绝大多数情况下性能足够。链式前向星可以作为进阶了解。

3.2 单源最短路径：Dijkstra 算法模板

解决边权非负的图中，单源点到所有其他点的最短路径问题。这是你必须刻在脑子里的模板。

const long long INF = 0x3f3f3f3f3f3f3f3fLL; // 足够大的数，防止溢出 vector<long long> dijkstra(int start, int n, const vector<vector<pair<int, int>>>& adj) { // adj[u] = vector of {v, weight} vector<long long> dist(n, INF); dist[start] = 0; // 使用优先队列（小顶堆），存储 {当前距离, 节点编号} priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq; pq.emplace(0, start); while (!pq.empty()) { auto [curDist, u] = pq.top(); pq.pop(); // 关键优化：如果当前取出的距离大于记录的距离，说明是旧数据，直接跳过 if (curDist > dist[u]) continue; for (auto& [v, w] : adj[u]) { long long newDist = curDist + w; if (newDist < dist[v]) { dist[v] = newDist; pq.emplace(newDist, v); } } } return dist; // dist[i] 为 start 到 i 的最短距离，若为 INF 则不可达 }

核心要点与避坑：

1. 为什么用priority_queue和greater<>？Dijkstra 的核心是每次从未确定的节点中选取距离源点最近的那个。优先队列（最小堆）能高效地提供这个“最近”节点。greater<>使得队首元素是最小的。
2. if (curDist > dist[u]) continue;这行代码至关重要！由于同一个节点可能被多次加入优先队列（因为发现了更短的路径），这行代码能过滤掉所有“过时”的、无效的队列项，避免冗余计算。这是保证效率的关键，也是容易忘记的一步。
3. 数据类型：距离dist和newDist建议使用long long，因为边权累加可能导致int溢出。INF也要相应定义为long long型的极大值。
4. 适用条件：边权必须非负。如果存在负权边，请使用 SPFA 或 Bellman-Ford 算法。
5. 邻接表结构：这里使用了vector<vector<pair<int, int>>>，pair的第一个元素是终点v，第二个是边权w。这种结构在遍历时非常方便。

3.3 最小生成树：Prim 算法模板

用于在加权无向连通图中找到一棵边权之和最小的生成树。其思想与 Dijkstra 类似。

long long prim(int n, const vector<vector<pair<int, int>>>& adj) { vector<bool> visited(n, false); vector<long long> minEdge(n, INF); // minEdge[i] 表示当前连通块到i的最小边权 minEdge[0] = 0; // 从节点0开始，任意节点均可 long long totalWeight = 0; // 优先队列存储 {边权, 节点} priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq; pq.emplace(0, 0); while (!pq.empty()) { auto [weight, u] = pq.top(); pq.pop(); if (visited[u]) continue; // 已加入生成树，跳过 visited[u] = true; totalWeight += weight; for (auto& [v, w] : adj[u]) { if (!visited[v] && w < minEdge[v]) { minEdge[v] = w; pq.emplace(w, v); } } } // 检查是否所有节点都连通，如果 visited 不全为 true，则图不连通，无最小生成树 for (bool v : visited) if (!v) return -1; // 表示无解 return totalWeight; }

核心要点与避坑：

1. 与 Dijkstra 的区别：Dijkstra 更新的是“从源点到某点的总距离”，而 Prim 更新的是“当前生成树连通块到某点的单条最小边权”。注意pq.emplace(w, v)中的w是边权，不是累积距离。
2. if (visited[u]) continue;：同样是为了过滤优先队列中的过时项。
3. 起始点：可以从任意节点开始，因为最小生成树的总权重是唯一的。
4. 图连通性判断：循环结束后，务必检查visited数组是否全为true。如果不是，说明原图不是连通图，不存在最小生成树。这是一个常见的陷阱，题目可能给出不连通的图。

4. 动态规划（DP）模板框架与经典模型

动态规划是算法竞赛的“明珠”，也是区分度最高的部分之一。它没有一成不变的代码模板，但有非常清晰的思维模板和框架。

4.1 DP 解题通用思维框架

在动笔写代码前，按照以下步骤思考，能极大提高解题成功率：

1. 定义状态 (dp数组的含义)：这是最关键的一步。明确dp[i]或dp[i][j]代表什么。通常与问题的子问题、所求目标直接相关。例如，“以第 i 个元素结尾的某种最优值”、“前 i 个物品在某种限制下的最优值”。
2. 确定状态转移方程：找出dp[i]与之前状态（如dp[i-1],dp[i-2],dp[...][...]）的关系。这是DP的核心逻辑，需要分析问题的最优子结构。
3. 初始化：给状态转移的起点赋值。通常是dp[0],dp[1]或边界情况。
4. 确定遍历顺序：确保在计算dp[i][j]时，它所依赖的状态都已经被计算出来。
5. 输出结果：最终答案通常存储在dp[n]或dp数组的某个特定位置。

4.2 经典模型：0-1背包问题模板

这是理解DP的绝佳入门模型。问题描述：有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使总价值最大，且总体积不超过背包容量。

二维DP模板（最直观）：

vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0)); // dp[i][j] 表示考虑前 i 件物品，在背包容量为 j 的情况下能获得的最大价值 for (int i = 1; i <= N; ++i) { // 枚举物品 for (int j = 0; j <= V; ++j) { // 枚举容量 // 不选第 i 件物品 dp[i][j] = dp[i-1][j]; // 选第 i 件物品 (前提是容量足够) if (j >= v[i]) { dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]); } } } int ans = dp[N][V];

一维滚动数组优化（必须掌握）： 观察二维转移方程：dp[i][j]只依赖于dp[i-1][...]。因此可以压缩掉第一维，但需要逆序枚举容量j。

vector<int> dp(V + 1, 0); for (int i = 1; i <= N; ++i) { // 关键：从大到小遍历容量 for (int j = V; j >= v[i]; --j) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } int ans = dp[V];

核心要点与避坑：

1. 为什么一维优化要逆序？因为dp[j]更新需要用到上一轮（i-1时）的dp[j - v[i]]。如果正序枚举j，那么dp[j - v[i]]可能在本轮 (i) 中已经被更新过了，这就变成了“完全背包”问题的逻辑（物品无限取），而不是0-1背包。“逆序”是为了保证每个物品只被考虑一次。这是背包问题最经典的考点。
2. 初始化细节：
   • 如果要求“恰好装满背包”，则dp[0] = 0，其他dp[...] = -INF（表示不可达）。
   • 如果只要求“价值最大”，不要求恰好装满，则全部初始化为0即可。
3. 变形与应用：背包模型可以衍生出很多问题，比如“方案数”（将max改为+）、“可行性判断”等。关键在于准确识别出题目中的“物品”（决策单元）、“体积”（限制条件）和“价值”（优化目标）。

4.3 经典模型：最长公共子序列（LCS）模板

两个字符串的动态规划经典问题。给定两个字符串text1和text2，返回它们的最长公共子序列的长度。

int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i-1] == text2[j-1]) { // 字符相等，LCS长度加1 dp[i][j] = dp[i-1][j-1] + 1; } else { // 字符不等，取两个方向的最大值 dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }

核心要点与避坑：

1. 状态定义：dp[i][j]定义为前缀子串的LCS长度，而不是以某个字符结尾。这使得状态转移更清晰。
2. 转移方程的理解：
   • text1[i-1] == text2[j-1]：当前字符可以加入LCS，所以长度等于dp[i-1][j-1] + 1。
   • 不相等：当前字符不能同时加入LCS，那么LCS要么来自text1[0..i-2]和text2[0..j-1]，要么来自text1[0..i-1]和text2[0..j-2]，取最大值。
3. 空间优化：同样可以优化为一维DP，因为dp[i][j]只依赖于上一行和当前行的左边。但二维写法更直观，在竞赛中通常够用。优化时需要注意状态的覆盖顺序。
4. 输出序列本身：如果需要输出具体的LCS字符串，不能只靠dp数组，需要额外记录转移路径（来自哪个状态），然后反向构造。

5. 搜索与回溯算法模板

当问题没有明显的数学公式或贪心策略时，搜索（DFS/BFS）是解决问题的“万能钥匙”，尤其是对于蓝桥杯常见的填空题和部分编程题。

5.1 深度优先搜索（DFS）与回溯模板

用于枚举所有可能的情况，常见于排列、组合、子集、棋盘类问题。

// 以经典的“全排列”问题为例：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。 vector<vector<int>> result; vector<int> path; vector<bool> used; // 标记元素是否被使用过 void backtrack(vector<int>& nums) { // 终止条件：路径长度等于原数组长度 if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); ++i) { // 剪枝：如果这个数字已经用过了，跳过 if (used[i]) continue; // 做选择 used[i] = true; path.push_back(nums[i]); // 进入下一层决策树 backtrack(nums); // 撤销选择（回溯） path.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { used.resize(nums.size(), false); backtrack(nums); return result; }

核心要点与避坑：

1. 回溯三部曲：
   • 选择 (Choose)：将当前选项加入路径，并更新状态（如used[i]=true）。
   • 递归 (Explore)：进入下一层决策。
   • 撤销选择 (Unchoose)：从路径中移除当前选项，恢复状态。这是“回溯”的精髓，保证了状态空间被完整且不重复地探索。
2. 状态记录：使用used数组来避免重复使用同一个元素。对于排列问题，这是必须的。对于组合或子集问题，通常通过传递一个startIndex参数来避免重复。
3. 剪枝：在递归前判断某些分支是否不可能产生有效解，从而提前返回，大幅提升效率。例如，在“N皇后”问题中，放置皇后前检查是否与已有皇后冲突。
4. 递归深度：蓝桥杯的栈空间通常足够深，但对于极端情况（如n>30的排列），递归DFS可能导致栈溢出，此时需要考虑迭代或BFS。

5.2 广度优先搜索（BFS）模板

用于寻找最短路径、最少步数等问题，特别是在图或网格中。

// 以网格中的最短路径为例：从起点 (sr, sc) 到终点 (tr, tc)，'.'表示可通行，'#'表示障碍。 int shortestPath(vector<vector<char>>& grid, int sr, int sc, int tr, int tc) { int rows = grid.size(), cols = grid[0].size(); // 方向数组：上、右、下、左 vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; vector<vector<bool>> visited(rows, vector<bool>(cols, false)); queue<pair<int, int>> q; q.emplace(sr, sc); visited[sr][sc] = true; int steps = 0; while (!q.empty()) { int size = q.size(); // 关键：记录当前层的节点数 for (int i = 0; i < size; ++i) { auto [r, c] = q.front(); q.pop(); // 判断是否到达终点 if (r == tr && c == tc) { return steps; } // 遍历四个方向 for (auto& [dr, dc] : directions) { int nr = r + dr, nc = c + dc; // 检查边界、是否可通行、是否访问过 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '.' && !visited[nr][nc]) { visited[nr][nc] = true; q.emplace(nr, nc); } } } steps++; // 一层遍历完，步数加1 } return -1; // 无法到达终点 }

核心要点与避坑：

1. 队列与层次遍历：BFS使用队列（queue）来保证“先进先出”，从而按距离起点的层次顺序遍历节点。int size = q.size()这行代码是按层计数的关键，它保证了steps的增加时机是正确的。
2. 访问标记：必须在节点入队时立刻标记为已访问 (visited[nr][nc] = true)，而不是在出队时。如果在出队时标记，同一个节点可能会被多次加入队列，导致超时甚至死循环。这是BFS最经典的错误之一。
3. 方向数组：使用directions数组来简化四个或八个方向的遍历代码，使逻辑更清晰。
4. 最短路径：BFS第一次到达终点时的步数，就是最短路径长度（在边权为1的图中）。这是由BFS的性质保证的。

6. 数学与数论常用模板

蓝桥杯填空题和部分编程题非常喜欢考察数学思维和数论知识。掌握以下几个模板，能帮你解决一大类问题。

6.1 质数判断与筛法

试除法判断单个质数：时间复杂度 O(√n)。

bool isPrime(int n) { if (n <= 1) return false; // 优化：只需检查到 sqrt(n) for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; }

埃拉托斯特尼筛法（埃氏筛）：快速筛选出[2, n]范围内的所有质数。时间复杂度 O(n log log n)。

vector<int> sieveOfEratosthenes(int n) { vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; vector<int> primes; for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); // 从 i*i 开始标记，因为 2*i, 3*i, ... (i-1)*i 已经被更小的质数标记过了 if ((long long)i * i <= n) { // 防止 i*i 溢出 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } } return primes; }

线性筛（欧拉筛）：在 O(n) 时间内得到所有质数，并能同时得到每个数的最小质因子。

vector<int> linearSieve(int n) { vector<int> primes; vector<bool> isComp(n + 1, false); // 是否是合数 vector<int> minPrimeFactor(n + 1, 0); // 最小质因子，可选 for (int i = 2; i <= n; ++i) { if (!isComp[i]) { primes.push_back(i); minPrimeFactor[i] = i; } // 用当前已得到的质数 primes[j] 去筛 for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) { isComp[i * primes[j]] = true; minPrimeFactor[i * primes[j]] = primes[j]; // 关键：保证每个合数只被其最小质因子筛掉一次 if (i % primes[j] == 0) { break; } } } return primes; }

选择建议：如果只需要判断少量大数，用试除法。如果需要得到n以内的所有质数，n <= 10^7用埃氏筛（代码简单），n更大或需要最小质因子时用线性筛。

6.2 最大公约数与最小公倍数

欧几里得算法（辗转相除法）：计算最大公约数（GCD）的经典方法。

// 递归版本 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // 迭代版本 int gcd_iter(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; }

最小公倍数（LCM）：利用公式lcm(a, b) = a * b / gcd(a, b)。注意先除后乘，防止溢出。

int lcm(int a, int b) { return a / gcd(a, b) * b; // 先除，防止 a*b 溢出 }

6.3 快速幂与模运算

快速计算a^b % mod，时间复杂度 O(log b)。这是处理大指数运算的必备工具。

long long fastPow(long long a, long long b, long long mod) { long long res = 1; a %= mod; // 先取模，防止后续乘法溢出 while (b > 0) { if (b & 1) { // 如果b的二进制最低位是1 res = (res * a) % mod; } a = (a * a) % mod; // a自乘 b >>= 1; // b右移一位 } return res; }

核心原理：将指数b用二进制表示。例如a^13 = a^(1101)_2 = a^(8) * a^(4) * a^(1)。通过不断将底数平方 (a = a * a)，并根据b的二进制位决定是否乘入结果，将计算复杂度从 O(b) 降为 O(log b)。

7. 字符串处理与STL技巧模板

蓝桥杯题目中字符串处理和标准模板库（STL）的使用无处不在，熟练运用能事半功倍。

7.1 字符串分割（Split）模板

C++标准库没有直接的split函数，自己实现一个非常实用。

vector<string> split(const string& s, char delimiter) { vector<string> tokens; string token; istringstream tokenStream(s); while (getline(tokenStream, token, delimiter)) { if (!token.empty()) { // 避免空字符串 tokens.push_back(token); } } return tokens; } // 使用示例：split("hello,world,c++", ',') -> {"hello", "world", "c++"}

更通用的版本（支持字符串分隔符）：

vector<string> split(const string& s, const string& delimiter) { vector<string> tokens; size_t start = 0, end = 0; while ((end = s.find(delimiter, start)) != string::npos) { tokens.push_back(s.substr(start, end - start)); start = end + delimiter.length(); } tokens.push_back(s.substr(start)); // 添加最后一个部分 return tokens; }

7.2 使用unordered_map进行计数与映射

统计元素出现次数、建立映射关系时，unordered_map（基于哈希表）通常比map（基于红黑树）更快。

// 统计字符串中字符频率 string s = "abracadabra"; unordered_map<char, int> freq; for (char c : s) { freq[c]++; } // 遍历 for (auto& [key, value] : freq) { cout << key << ": " << value << endl; }

注意：如果键的类型是自定义结构体，需要为其提供哈希函数和相等比较函数，或者使用map。

7.3 使用set进行去重与有序维护

set（有序集合）和unordered_set（无序集合）用于存储不重复的元素。

// 去重并排序 vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6}; set<int> unique_sorted(nums.begin(), nums.end()); // {1, 2, 3, 4, 5, 6, 9} // 判断元素是否存在 O(log n) if (unique_sorted.find(5) != unique_sorted.end()) { // 存在 } // 获取最小/最大元素（因为set有序） int smallest = *unique_sorted.begin(); int largest = *unique_sorted.rbegin();

multiset的妙用：可以存储重复元素，并保持有序。常用于动态求中位数、维护滑动窗口的最值等（虽然效率不是最高，但编码简单）。

multiset<int> ms; ms.insert(3); ms.insert(1); ms.insert(3); // {1, 3, 3} auto it = ms.find(3); // 找到第一个3 ms.erase(it); // 只删除一个3 // ms.erase(3); // 这会删除所有值为3的元素！小心！

8. 调试、测试与赛场策略

模板背得再熟，临场写不出来也是白搭。最后这部分，分享一些实战中的“软技能”模板。

8.1 常用调试代码片段

在代码中预埋一些调试输出，关键时刻能救命。

// 1. 打印容器内容（适用于vector, set等） template<typename T> void debugPrint(const T& container) { #ifdef LOCAL // 定义 LOCAL 宏，只在本地调试时生效 for (const auto& x : container) { cout << x << " "; } cout << endl; #endif } // 2. 快速查看变量（使用宏，比赛后记得注释或删除） #define dbg(x) cerr << #x << " = " << (x) << endl // 使用：dbg(a); dbg(b); // 3. 测量代码段运行时间（用于优化时参考） #include <chrono> auto start = chrono::high_resolution_clock::now(); // ... 你的代码 ... auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - start); cerr << "Time elapsed: " << duration.count() << " ms" << endl;

8.2 针对不同题型的策略模板

• 结果填空题：通常只要求提交一个数字或字符串。策略是“先暴力，再优化”。先写一个思路清晰的暴力程序（DFS、枚举）在小规模数据上跑出结果，然后通过数学推导、找规律、优化算法来得到最终答案。务必用程序验证最终答案，哪怕是用计算器手算复核。
• 程序设计题：
  1. 读题：划出数据范围、输入输出格式、特殊条件。数据范围直接决定了你能用什么算法（n<=20可能用搜索，n<=10^5通常需要 O(n log n) 或 O(n)）。
  2. 构思：在草稿纸上画图、列样例、推演。先想清楚再编码，避免边写边改。
  3. 编码：使用清晰的变量名，复杂逻辑加注释。先写核心算法框架，输入输出和简单逻辑可以稍后补全。
  4. 测试：
     • 用题目给的样例。
     • 设计边界用例（如 n=0, n=1，最大值，最小值）。
     • 设计一些随机小数据，用暴力程序（如果写得出来）对拍。
  5. 检查：检查数组大小是否足够（通常开n+10），初始化是否正确，int是否会溢出（考虑用long long），递归深度是否过大。

8.3 代码书写模板（文件头）

养成好的代码习惯，避免低級错误。

#include <bits/stdc++.h> // 竞赛常用，包含大多数标准库 using namespace std; typedef long long ll; typedef pair<int, int> pii; // 其他常用类型别名 const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const int MOD = 1e9 + 7; // 常用模数 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 你的代码逻辑 return 0; }

把这些模板内化成自己的肌肉记忆，在赛场上你才能把精力集中在问题建模和算法设计上，而不是纠结于Dijkstra的优先队列怎么写，或者背包为什么总是多算一次。真正的“模板”，是你思考的脚手架，而不是思维的枷锁。多练，多总结，把每一个模板背后的原理吃透，你就能在蓝桥杯的赛场上，从容地拆解题目，快速组合出正确的解决方案。