★ FEATURED ARTICLE 备赛蓝桥杯这件事很多同学一上来就是刷真题、刷题解恨不得把洛谷、力扣上的热门题全过一遍。但刷到一定量你会发现真正让你卡在国奖之外的不是思路而是把思路转成代码时的速度和准确度。这时候一份可靠的算法竞赛模板就成了最实际的东西。这篇博文就把我在备赛过程中反复打磨过的蓝桥杯算法竞赛必备模板整理出来从高频考点反推模板需求把并查集、树状数组、线段树、二分、搜索、图论、DP 这些常用板子逐个拆开再结合一道真题演示整个“套模板”的流程最后聊聊背诵、调试和三语言提交时踩过的坑。适合正在准备蓝桥杯省赛和国赛、或者打算系统梳理竞赛模板的同学参考。1. 先从命题规律反推蓝桥杯为什么需要“模板”1.1 蓝桥杯的题面特征与模板需求蓝桥杯的比赛形式和 ACM/ICPC 不太一样它按组别分 C/C、Java、Python省赛国赛都有填空类和程序设计类题目。填充题可以手算但真正拉开差距的是后面几道编程大题。编程大题的特点是单题分值高、数据范围阶梯式分布、部分数据点允许暴力过而 AC 全部测试点往往需要你写出标准做法的实现。从历年真题看编程大题的考点相对“收敛”前缀和与差分、二分、排序、贪心、搜索DFS/BFS、动态规划、图论最短路、拓扑排序、并查集、数论快速幂、素数筛、GCD/LCM以及数据结构里的树状数组、线段树、单调栈/队列。这些考点非常集中在竞赛模板的覆盖范围内所以“背模板”这件事在蓝桥杯场景下不是投机取巧而是确确实实能缩短编码时间、降低失误率的策略。我见过不少同学平时题解看得懂比赛时却因为一个lower_bound写成了upper_bound、或者 DFS 忘记标记访问节点而整道题挂掉。模板的意义恰恰在于把这些高频逻辑固化成稳定、熟练的代码块让你在比赛时不需要从零设计只需要根据题面调整边界和状态参数。1.2 模板的本质是压缩“实现成本”模板不是把代码背下来就完事而是“接口固定、改动点清晰”。我习惯把每份模板想象成做菜的备料食材切好、调料配好下锅时只会根据菜谱微调火候。比如并查集核心就是find、unite两个接口树状数组核心就是lowbit、add、sum二分答案则是“单调性判断 上下界更新”的骨架。真正需要你在考场上思考的是这道题“为什么匹配这个模板”以及“模板里的哪一行需要改动”。我给自己定过三条模板储备原则模板必须自己重写过不直接抄别人代码理解每一行是干什么的模板代码必须能在空白编辑器里默写出来限时 5 到 8 分钟一份每套模板附一个最小用例用来快速验证模板的正确性。这三条原则看起来简单但真到比赛现场它们能帮你把写代码的时间从 30 分钟压到 15 分钟以内省下来的时间足够你去检查边界条件。2. 核心模板拆解与实现细节2.1 通用框架头文件、快速IO与基础函数C/C 组别里最常用的头文件就是bits/stdc.h它把标准库全拉进来省去记头文件名的功夫。蓝桥杯评测环境基本都支持这一头文件可以放心用。配合下面的输入输出优化能让cin/cout在高数据量输入下不至于超时#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 业务代码 return 0; }ios::sync_with_stdio(false)的意思是关闭 C 标准流与 C 标准流的同步cin.tie(nullptr)则是取消cin与cout的绑定避免每次输出时都强制刷新缓冲区。这两行是所有 C 竞赛程序的标配实测在 1e5 以上数据量时提升非常明显。Java 组别要注意主类名必须是Main并且使用 BufferedReader 加 StringTokenizer 做快读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(); } }Python 组别则建议用sys.stdin.buffer.read()一次性读入全部数据再切分避免逐行input()的损耗import sys data sys.stdin.buffer.read().split() it iter(data) n int(next(it))如果你遇到“蓝桥杯 Python 入门基础”这类问题第一件事就是把快读模板练熟因为 Python 的 OJ 性能瓶颈往往不在算法而在 IO 和递归深度。2.2 二分与排序模板二分是蓝桥杯的高频考点主要分成两类一类是直接调用lower_bound / upper_bound在有序序列里找位置另一类是“二分答案”用于求最大值最小或最小值最大。手写二分答案的核心模板如下int l 0, r 1e9, ans -1; while (l r) { long long mid l (r - l) / 2; if (check(mid)) { ans mid; l mid 1; // 求最大值 } else { r mid - 1; } }注意两个细节第一mid用l (r - l) / 2而不是(l r) / 2防止两个大整数相加溢出第二check函数的单调性要想清楚求最小值时更新逻辑反过来。很多同学死循环就死在l mid而不是l mid 1上这是一定要避开的坑。排序方面C 直接用sort和stable_sort。如果题目用到结构体多关键字排序我习惯重载operator或者在sort里传 Lambdastruct Node { int val, idx; bool operator(const Node other) const { if (val ! other.val) return val other.val; return idx other.idx; } }; sort(arr, arr n);2.3 数论模板快速幂、线性筛、GCD/LCM数论题在蓝桥杯里以快速幂和素数相关为主。快速幂用来算大指数取模代码短且固定long long qpow(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这里使用“二进制拆解指数”的思路每次把b的二进制位看一遍。注意初始res写成1 % mod而不是直接1避免mod 1时的边界问题。这个细节平时看不出来但极端数据下会直接导致输出错误。线性筛模板用于在 O(n) 时间内筛出所有质数并记录最小质因子const int MAXN 1000000; int primes[MAXN], cnt; bool isComp[MAXN]; void sieve(int n) { for (int i 2; i n; i) { if (!isComp[i]) primes[cnt] i; for (int j 0; j cnt 1LL * i * primes[j] n; j) { isComp[i * primes[j]] true; if (i % primes[j] 0) break; } } }线性筛的关键是if (i % primes[j] 0) break这保证每个合数只被它的最小质因子筛掉一次。蓝桥杯里求区间素数、质因数分解的题目都能用上。GCD 和 LCM 我一般直接用__gcdC17 支持蓝桥杯环境通常可用或自己写一行long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }lcm先除后乘避免中间结果溢出。2.4 数据结构模板并查集、树状数组、线段树并查集是图论题的“万金油”判断连通性、合并集合、统计集合个数都用它int fa[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; }初始化时for (int i 1; i n; i) fa[i] i;不能省。路径压缩之后find的均摊复杂度接近常数级。比赛时我一般不会加按秩合并因为路径压缩已经够快再多一行代码反而增加默写负担。树状数组模板适合“单点修改 区间查询”的场景代码比线段树短一个量级int bit[MAXN], n; int lowbit(int x) { return x -x; } void add(int idx, int val) { while (idx n) { bit[idx] val; idx lowbit(idx); } } long long sum(int idx) { long long res 0; while (idx 0) { res bit[idx]; idx - lowbit(idx); } return res; }求区间[l, r]的和就是sum(r) - sum(l - 1)。树状数组在统计逆序对、动态前缀和等题目里非常实用对应很多人搜的“树状数组模板”。线段树则用于“区间修改 区间查询”尤其是带懒标记的版本。核心结构长这样long long tree[MAXN 2], lazy[MAXN 2]; void pushUp(int id) { tree[id] tree[id 1] tree[id 1 | 1]; } void pushDown(int id, int l, int r) { if (!lazy[id]) return; int mid (l r) 1; lazy[id 1] lazy[id]; lazy[id 1 | 1] lazy[id]; tree[id 1] lazy[id] * (mid - l 1); tree[id 1 | 1] lazy[id] * (r - mid); lazy[id] 0; } void update(int id, int l, int r, int L, int R, long long val) { if (L l r R) { tree[id] val * (r - l 1); lazy[id] val; return; } pushDown(id, l, r); int mid (l r) 1; if (L mid) update(id 1, l, mid, L, R, val); if (R mid) update(id 1 | 1, mid 1, r, L, R, val); pushUp(id); } long long query(int id, int l, int r, int L, int R) { if (L l r R) return tree[id]; pushDown(id, l, r); int mid (l r) 1; long long res 0; if (L mid) res query(id 1, l, mid, L, R); if (R mid) res query(id 1 | 1, mid 1, r, L, R); return res; }这个模板默认处理区间加和区间求和如果题目需要区间异或、区间覆盖只需要把pushDown里的合并逻辑改成对应操作。线段树容易写错的地方是pushDown里tree[child]增加的值要乘以子区间长度很多人漏了这一步。2.5 图论与搜索模板DFS、BFS、Dijkstra、拓扑排序搜索是蓝桥杯的绝对主力。DFS 模板主要用来处理连通块、回溯枚举和部分剪枝int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; bool vis[MAXN][MAXN]; void dfs(int x, int y) { if (x 0 || x n || y 0 || y m) return; if (vis[x][y] || g[x][y] #) return; vis[x][y] true; for (int i 0; i 4; i) { dfs(x dx[i], y dy[i]); } }标记访问的vis[x][y] true要放在进入递归前而不是递归返回后。如果放在递归返回后标记会造成大量重复访问。BFS 模板用于求最短步数、分层扩散类问题int bfs(int sx, int sy) { queuepairint, int q; q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); if (x tx y ty) return dist[x][y]; for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (vis[nx][ny] || g[nx][ny] #) continue; vis[nx][ny] true; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return -1; }BFS 的一个常见坑是“出队时才标记访问”这会让同一个节点反复入队最坏情况下复杂度退化。正确做法是“入队时标记”。带权图的最短路模板是堆优化的 Dijkstravectorpairint, int g[MAXN]; long long dist[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairlong long, int, vectorpairlong long, int , greaterpairlong long, int pq; pq.push({0, s}); while (!pq.empty()) { long long d pq.top().first; int u pq.top().second; pq.pop(); if (d ! dist[u]) continue; for (auto edge : g[u]) { int v edge.first; int w edge.second; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }拓扑排序用 Kahn 算法配合队列和入度数组vectorint topo(int n) { queueint q; vectorint res, indeg(n 1, 0); for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : g[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } return res; }如果res.size() ! n说明图中存在环。这道模板在判断有向图是否有环、安排任务顺序时非常好用。2.6 动态规划模板背包、LIS、树形DPDP 类题目很吃状态设计但模板仍然能帮上忙。01 背包是一行代码级别的骨架for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }j从大到小遍历保证每个物品只选一次。如果改成从小到大就是完全背包。蓝桥杯还经常考分组背包、多重背包多重背包可以用二进制拆分优化成多个 01 背包。LIS最长上升子序列可以用贪心加二分的 O(n log n) 模板vectorint d; for (int x : a) { auto it lower_bound(d.begin(), d.end(), x); if (it d.end()) d.push_back(x); else *it x; } // d.size() 就是答案这个模板的原理是维护一个“当前最小末尾值”数组lower_bound找到第一个不小于x的位置并替换。很多人搜的“c语言二分模板”在这里刚好能直接复用。树形 DP 模板最典型的是树上最大独立集也就是“每个节点选或不选”vectorint tree[MAXN]; int dp[MAXN][2]; // dp[u][0] 不选 udp[u][1] 选 u void dfs(int u, int fa) { dp[u][1] val[u]; for (int v : tree[u]) { if (v fa) continue; dfs(v, u); dp[u][0] max(dp[v][0], dp[v][1]); dp[u][1] dp[v][0]; } }这里的状态转移非常清晰当前节点不选时子节点可选可不选当前节点选时子节点只能不选。换根、树上背包都可以在这个骨架上扩展。3. 用真题检验模板以“全球变暖”为例3.1 题目到底在考什么蓝桥杯省赛有一道经典真题叫“全球变暖”。题意很好懂给你一个 N×N 的海图#表示陆地.表示海洋上下左右相邻的陆地属于同一个岛屿。海平面上升后所有与海洋相邻的陆地都会被淹没斜对角不算相邻。题目问有多少个岛屿会被完全淹没。这道题被很多人拿来练手因为它看起来简单实际做起来却在“完全淹没”这个概念上卡人。你需要先识别出所有岛屿然后对每个岛屿判断是否存在某块陆地四面都是陆地如果存在这个岛屿就不会被完全淹没如果不存在就会被完全淹没。对应到模板这是典型的“DFS 求连通块 额外状态统计”问题。DFS 模板负责找岛屿额外状态负责统计“是否有高地”。3.2 套模板的完整过程拿到题目后我的思路顺序是这样的看到“上下左右相邻”确定用四方向 DFS看到“岛屿”确定要遍历全图寻找未访问的#每找到一个未访问#启动一次 DFS同时把当前岛屿的“是否存在四面皆陆地的点”记录下来统计岛屿总数和有高地岛屿数两者相减就是被完全淹没的岛屿数。完整代码实现如下#include bits/stdc.h using namespace std; const int MAXN 1010; char g[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int n; bool highLand; void dfs(int x, int y) { if (x 0 || x n || y 0 || y n) return; if (vis[x][y] || g[x][y] .) return; vis[x][y] true; bool ok true; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny n) ok false; else if (g[nx][ny] .) ok false; } if (ok) highLand true; for (int i 0; i 4; i) { dfs(x dx[i], y dy[i]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 0; i n; i) cin g[i]; int islands 0, survive 0; for (int i 0; i n; i) { for (int j 0; j n; j) { if (!vis[i][j] g[i][j] #) { highLand false; dfs(i, j); islands; if (highLand) survive; } } } cout islands - survive \n; return 0; }这份代码就是把“DFS 连通块模板”和“额外状态统计”两个东西粘在一起。DFS 里判断高地时我把越界的情况也当成会被淹没因为地图边缘外就是海这个细节很容易漏。如果你不想用全局变量highLand也可以让 DFS 返回一个 boolean 或 int 来标记当前岛屿是否有高地。全局变量写法在比赛中最直观适合快速写完但要注意每次新岛屿开始前必须重置。这道题用 BFS 也能做思路完全一致只是把栈换成了队列。3.3 边界条件与常见坑这道题最典型的坑有三个。第一个是“统计数量对象搞错”。题目问的是“多少岛屿会被完全淹没”而不是“多少陆地会被淹没”。我见过不少新手最后输出被淹没的陆地个数样例能过交上去全错。所以套模板前一定把题读清楚确定最终答案是哪个汇总值。第二个是标记访问的时机。如果 DFS 里把vis[x][y] true写在递归返回之后整个 DFS 会退化成指数级重复搜索N 稍大直接超时。这个错误在“全球变暖”这类全连通区域题里尤其致命因为岛屿往往很大。第三个是递归爆栈。当 N 达到 1000 且整张图全是#时递归深度可能到几十万层部分环境下会栈溢出。解决办法有两个一是把 DFS 改成显式栈二是直接用 BFS 写法。BFS 版本不用递归稳定性和 DFS 版本相当就是代码稍长一点。4. 常见问题与排查技巧实录4.1 背板默写最容易翻车的5个点我整理了一份自己踩过的高频默写错误表每次模拟赛前都会扫一遍错误类型出错表现正确做法数组大小不够越界访问或 segfault根据数据范围开 MAXN 5多组数据未清空后一组答案受前一组影响每组输入前 memset / clear二分边界死循环程序卡住或输出错误mid l (r - l) / 2配合l mid 1递归爆栈运行时崩溃换 BFS 或显式栈Java 主类名错误提交编译失败类名必须是Main不能带包名这些错误里数组大小是最隐蔽的。比如题目 N 最大 1e5你开了 100005但有些算法要用MAXN 2四倍空间没开够就会在边界数据上挂掉。我的习惯是一律开const int MAXN 100005线段树和树状数组再用MAXN 2宁可多开几十 KB。4.2 五分钟定位模板 bug打印、缩样例、对拍现场调试时我有一套固定的“三板斧”。第一板斧是打印中间变量。在二分答案的check函数里打印每个 mid 和对应的check(mid)结果能瞬间看出来单调性判断是否写反。在 BFS 里打印当前出队节点和dist能定位入队顺序错没错。第二板斧是构造最小样例。不要上来就造大数据先构造一个规模在 3 到 5 的样例手动算出答案再跑程序。比如“全球变暖”这种题构造一个 3×3 全#的地图你会发现这个岛屿中心有高地不会被完全淹没再构造一个单格#的地图它会完全被淹没。两个极端样例一套逻辑对不对就清楚了。第三板斧是对拍。准备一个暴力解程序和一个模板程序用随机数据批量比较输出。我常用 Python 写一个小对拍脚本import random import subprocess for t in range(1000): n random.randint(1, 8) with open(input.txt, w) as f: f.write(str(n) \n) for _ in range(n): f.write(.join(random.choice(.#) for _ in range(n)) \n) for name in [brute, solve]: subprocess.run([./ name], stdinopen(input.txt), stdoutopen(name .out, w)) a open(brute.out).read().strip() b open(solve.out).read().strip() if a ! b: print(found diff at, t) break对拍的好处是能在本地小数据范围内找出所有边界 bug缺点是需要先写一个暴力版。但暴力版往往很简单写起来不亏比赛前这个习惯能救回很多分。4.3 三语言提交的差异与注意事项蓝桥杯支持 C/C、Java、Python我三种都提交过总结出一些很实际的差异。C 输出浮点数用printf(%.3f\n, x)或cout fixed setprecision(3) x。注意long long输出用%lld别和%d混用。Java 的陷阱主要在输入输出和类名。输入用BufferedReader输出尽量拼成StringBuilder一次性提交而不是频繁System.out.println。蓝桥杯“数字题目”经常要求格式化输出比如保留两位小数、按固定宽度输出Java 可以用String.format(%.2f, x)对应 Python 的 f-string 语法更直接f{x:.2f}。这两套格式化模板是处理输出类题目的刚需。Python 还有两个特有的坑。第一深递归要手动调sys.setrecursionlimit(1 25)否则 DFS 在 1000 层时就会报错第二稠密图算法如 Floyd-Warshall 在 Python 里可能超时能转 C 思路就用 C如果只能用 Python优先选 BFS 和动态规划这类不容易被常数拖垮的写法。蓝桥杯 Python 组的数据规模一般不会特别夸张但 IO 优化必须做足。5. 备赛规划模板之外的隐藏分5.1 从“背模板”到“验模板”的练习节奏模板真正发挥作用的时间点不是比赛当天而是赛前两周。我建议把备赛分三个阶段第一阶段整理期。把本文列出的所有模板全部打开自己重写一遍。不要复制粘贴手敲到编辑器里然后把不理解的语句注释标注出来。这个阶段的目标是让每份模板都变成“自己能解释每一行”的代码。第二阶段默写期。每天抽 20 分钟随机选 3 份模板默写在文本文件里限时 8 分钟一份。默写完对照原版看差异重点看缩进、变量名、边界条件有没有写错。别小看这个笨办法它能把模板从“看过”变成“长在手上”。第三阶段真题检验期。每周拿一套蓝桥杯省赛真题要求自己只能用模板库里的代码和手写模板解题。做完之后复盘这份模板有没有地方写起来别扭别扭的位置就是需要优化的位置。我自己的模板库就是这么一点点从“抄来的”变成“自己的”。5.2 用“最小用例”验证模板正确性每份模板都配一个最小用例这是我能给出的最实用建议。最小用例不需要复杂只要覆盖边界情况即可。比如并查集的最小用例是n 1时find(1)返回 1树状数组的最小用例是数组长度为 1 时add(1, 5)后sum(1) 5线段树的最小用例是区间更新[1, n]后query(1, n)的值正确。为什么最小用例这么重要因为模板是高频使用的如果在最小规模下出错说明模板本身的实现有问题而不是题目数据刁钻。我见过同学在比赛时用一份“从来没验证过”的树状数组结果在 20 行以内的小样例就输出错误白白浪费整道题。赛前把所有模板的最小用例跑一遍是对模板库的体检。5.3 别忽视暴力模板和“部分分”策略蓝桥杯的编程大题通常按测试点给分很多题目具有明显的“分档数据”小数据可以暴力大数据才需要标准做法。因此你的模板库里除了标准模板还应该准备几份“保底暴力模板”。暴力枚举模板要覆盖全排列生成next_permutation、子集枚举状态压缩for (int mask 0; mask (1 n); mask)、朴素 BFS 和朴素 DP。比赛时如果一时想不出正解先用暴力把能拿的测试点全部拿满再尝试用剪枝优化其中一档数据。这个策略在蓝桥杯里非常实用因为省赛分数线常常就压在“一题满分 其余题部分分”的组合上。不过要注意暴力模板不能让你拿到所有分它的作用是“兜底”。真正想稳拿国奖还是要靠标准模板的熟练度。5.4 关于“背模板”这件事我最后想说的话我从第一次参加蓝桥杯到现在最大的体会是模板不是用来“抄”的而是用来“压榨”的。每当我 AC 一道题我都会回头看看能不能从这道题里提炼出一个更通用的模板片段每当我发现现有模板写起来别扭就说明它还没打磨到位。比赛前一周我每天会花十分钟快速默写十个核心模板不求一字不差但求手熟。省赛和国赛用下来只要题型在模板覆盖范围内基本能省出十到二十分钟编码时间这些时间足够多调试两个边界用例。希望这份整理能帮你在备赛路上少走一段弯路。祝顺利。
阅读完成 · 觉得有帮助？
