准备蓝桥杯Java组的比赛绕不开一件事算法模板。我参加了三届蓝桥杯从省二到国二最大的转折点就是把零散的刷题笔记整理成了一套自己的算法模板库并且用历年真题反复打磨过。这套东西帮我省了至少一半的备赛时间今天把它公开出来结合2022年国赛B组真题“出差”完整讲一遍模板怎么搭、怎么背、怎么在考场上用。这篇文章不打算写成那种“从入门到放弃”的大杂烩而是聚焦一件事给你一套可以直接背、直接套、直接提交的Java核心算法模板再用真题带着你走一遍完整的实战流程。内容面向今年准备蓝桥杯省赛和国赛的Java选手也适合准备机试、面试手撕算法的朋友。看完之后你可以把这些模板整理成自己的笔记考前反复过比临时翻书高效得多。1. 赛题特点与模板库的整体设计思路1.1 蓝桥杯Java组到底在考什么先说结论蓝桥杯省赛的题目难度分布大概是“基础题占一半中等题占三成难题两成”的样子。基础题基本就是枚举、排序、模拟、字符串处理中等题开始出现BFS/DFS、简单DP、二分、并查集难题才轮到状态压缩DP、最短路径变体、线段树这类进阶内容。换句话说省赛拿省一不需要你会什么很高深的东西把常见模板写熟就够了。国赛想要拿奖除了模板熟练度还需要一点数学思维和建模能力但模板依然是地基。很多同学有一个误解觉得蓝桥杯是“思维竞赛”考的是灵感。实际上蓝桥杯更像是“算法模板竞赛”绝大多数题目都能归类到某个经典模板里。你看到一道题能快速识别出“哦这是背包”“哦这是最短路”就已经赢了一半。1.2 为什么不建议拿着别人的模板直接背我见过太多人从网上扒一份“算法模板大全”存进手机就再也不看了。模板这东西你光看不写等于零。它和吉他谱、菜谱一样必须亲手练过、亲手改过才是你的。所以我的建议是不要直接背我的模板而是拿着我的思路去改写成自己习惯的风格。比如有人喜欢用Scanner有人喜欢用StreamTokenizer有人习惯for循环二分有人习惯while。这些个人偏好都要在平时敲代码的时候定型考场上才能形成条件反射。我的这套模板库从设计之初就是按“可背诵、可实战”的标准来的。每个模板都保持最短的代码量去掉所有花里胡哨的写法尽量不做无谓的封装。因为蓝桥杯是OI赛制代码越短、越好写、越好记考场上就越不容易出错。1.3 模板库的分层结构我给自己的模板库分了四层划分依据是“考场上出现频率”和“代码复杂度”层数分类包含模板关键词第一层IO与基础StreamTokenizer快读、PrintWriter快写、常用数学工具输入输出、模运算第二层搜索枚举DFS、BFS、全排列、子集枚举、网格遍历枚举、搜索、剪枝第三层经典算法二分、双指针、背包DP、线性DP、LIS/LCS最优解、状态转移第四层图论进阶Dijkstra、Floyd、并查集、最小生成树、拓扑排序图、连通性、最短路每一层都是下一层的基础。第二层的DFS写法熟了第四层的图遍历自然就会了第三层的DP状态设计学会了图论里的状态压缩就不怕了。平时刷题的时候凡是遇到新题先想这四层模板里有没有能直接套的没有才去学新东西。2. 第一层地基输入输出与基础数学模板2.1 快读模板别让Scanner拖垮你的程序Java选手最容易忽略的一个问题就是输入输出性能。蓝桥杯的测试数据量省赛大部分题目在10^5级别Scanner勉强能跑但到了国赛数据量到10^6Scanner的nextInt()就开始卡了。我在初赛的时候吃过这亏一道排序题代码全对结果超时查了半天发现是Scanner在拖后腿。这个坑的根源是Scanner内部用了正则表达式做分词天生就慢。我常用的替代方案有两个StreamTokenizer或BufferedReader手动解析。对于绝大多数蓝桥杯题目StreamTokenizer的代码量最少最推荐。import java.io.*; import java.util.*; public class Main { static StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); static int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } public static void main(String[] args) throws IOException { int n nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] nextInt(); } out.println(Arrays.toString(arr)); out.flush(); } }这个模板有几个细节值得注意。第一main方法必须声明throws IOException因为st.nextToken()会抛异常。第二PrintWriter最好用out.flush()手动刷新不然可能输出不全。第三如果题目涉及long类型的输入st.nval是double直接强转(long)就行。如果题目输入里既有整数又有字符串比如图论题里nextInt()和next()混合用StreamTokenizer有个大坑st.nextToken()之后字符串用st.sval获取但普通字符会被当成空白符跳过。这时候我建议改用BufferedReader手写快读虽然代码长一点但不容易出错。2.2 判素数、快速幂与组合数预处理数论题在蓝桥杯里出现频率极高尤其是“质因数分解”“最大公约数”“快速幂”这三个点。省赛喜欢考简单的国赛喜欢把它们包在复杂题里当步骤之一所以这套基础数学模板必须滚瓜烂熟。// 埃氏筛求出1~n内所有素数isPrime[i]为true表示i是素数 static boolean[] primeSieve(int n) { 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]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } return isPrime; } // 快速幂计算 a^b % mod static long quickPow(long a, long b, long mod) { long res 1; while (b 0) { if ((b 1) 1) res res * a % mod; a a * a % mod; b 1; } return res; }这里我想特意强调一下b 1的写法它相当于b b / 2但位运算速度更快在循环次数很多的时候有微弱优势。快速幂的原理其实一句话就能讲清把指数转成二进制用“平方代替乘方”的方式减少乘法次数。这就像你去超市买东西一次买一箱比一次买一瓶跑的次数少。组合数模板也经常用到尤其是求C(n, k)的值当n到2000的时候直接用二维数组预处理n到10^6的时候用阶乘和逆元。蓝桥杯的题一般不会卡到需要费马小定理求逆元的程度但省赛出现过所以把公式背下来没坏处。3. 第二层搜索DFS、BFS与枚举万能骨架3.1 全排列与组合枚举回溯模板必须默写全排列是蓝桥杯出镜率最高的模板之一。不管是“八皇后”“排列数字”还是“凑算式”底层都是这套回溯框架。为什么它重要因为很多中等题一眼看不出数学模型但数据范围很小直接枚举所有排列暴力验证反而最简单。static int n; static int[] path new int[20]; static boolean[] used new boolean[20]; static void dfs(int step) { if (step n) { // 此时path[0]~path[n-1]就是一个全排列处理输出或判断 for (int i 0; i n; i) out.print(path[i] ); out.println(); return; } for (int i 1; i n; i) { if (!used[i]) { used[i] true; path[step] i; dfs(step 1); used[i] false; // 回溯恢复现场 } } }回溯的核心就是“递归前标记递归后还原”这八个字。只标记不还原叫剪枝方向写错只还原不标记叫重复枚举。很多同学写排列题第一次都会漏掉used[i] false这一步导致结果翻倍这个坑我见过不下十次。组合枚举略有不同它需要一个startIndex参数来控制不往回选。比如从1到5选3个数的组合选了2之后只能从3往后选不能再选1。这个“不往回选”的限制是组合去重的灵魂。// 从1~N中选m个数cnt表示当前已选几个start表示从哪个数开始往后选 static void comb(int cnt, int start) { if (cnt m) { // 输出path return; } for (int i start; i n; i) { path[cnt] i; comb(cnt 1, i 1); } }3.2 网格型BFS最短步数题的万能模板蓝桥杯的图论题很多都是“走迷宫”的变体二维网格、有障碍物、问从起点到终点的最少步数。这种题BFS是标准解法。BFS的特点是“一层一层往外扩”就像在水面丢石头波纹一圈一圈扩散先碰到的终点就是最短路径。static int n, m; static char[][] grid new char[1005][1005]; static int[][] dist new int[1005][1005]; static int[] dx {1, -1, 0, 0}; static int[] dy {0, 0, 1, -1}; static int bfs(int sx, int sy, int ex, int ey) { for (int i 0; i n; i) Arrays.fill(dist[i], -1); Queueint[] q new LinkedList(); q.offer(new int[]{sx, sy}); dist[sx][sy] 0; while (!q.isEmpty()) { int[] cur q.poll(); if (cur[0] ex cur[1] ey) return dist[cur[0]][cur[1]]; for (int k 0; k 4; k) { int nx cur[0] dx[k], ny cur[1] dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[cur[0]][cur[1]] 1; q.offer(new int[]{nx, ny}); } } return -1; }这个模板有几个优化点得说清楚。dist数组同时充当“是否访问过”和“距离”两个角色省掉一个visited数组代码更短。用LinkedList做队列是因为它实现了Queue接口注意不要搞混offer/add、poll/remove的区别offer和poll失败时返回特殊值而不是抛异常写搜索题更稳。3.3 DFS解决连通块问题从洪水填充到统计岛屿与BFS类似的还有DFS连通块问题比如“数一数图里有几个独立岛屿”“矩阵中被包围的区域”。这类题可以用DFS递归实现模板更短但不适合求最短步数因为DFS是“一条道走到黑”。我在考场上喜欢这样分工求最短路径用BFS求连通性用DFS。原因很实际BFS代码长但不容易爆栈DFS代码短但有栈溢出风险。蓝桥杯的数据量一般不会让DFS爆栈所以简单连通块题用DFS反而更快。4. 第三层核心DP与经典算法模板4.1 背包问题模板01背包是其他所有背包的基础背包问题在蓝桥杯里是“神级考点”每年至少出现一道。把01背包吃透完全背包、多重背包、分组背包都能顺着推出来。我自己的话总结成一句话“外层循环物品内层倒序容量。”// n个物品背包容量m每个物品体积v、价值w求最大价值 static int knapsack01(int n, int m, int[] v, int[] w) { int[] dp new int[m 1]; for (int i 0; i n; i) { for (int j m; j v[i]; j--) { dp[j] Math.max(dp[j], dp[j - v[i]] w[i]); } } return dp[m]; }为什么要“倒序”因为01背包要求每个物品只能选一次如果正序遍历dp[j - v[i]]可能已经是本轮更新过的值等于一个物品被用了多次就成了完全背包。这是一个很经典的坑我建议你在草稿纸上手动模拟一遍比背十遍都管用。完全背包模板只需要把内层循环从倒序改成正序for (int j v[i]; j m; j) { dp[j] Math.max(dp[j], dp[j - v[i]] w[i]); }4.2 线性DP与LIS状态定义是最关键的一步线性DP的经典模型是“最长上升子序列LIS”和“最长公共子序列LCS”。蓝桥杯喜欢把它们包装成“最长快乐线路”“最长共有子串”这类情景题。这种题难的不是代码而是你能不能看出来它在考DP、能不能定义出正确的状态。LIS的朴素做法的状态定义是dp[i]表示以第i个数结尾的最长上升子序列长度。转移时枚举前面的数看看能不能接上去。它的时间复杂度是O(n²)n在1000以内没问题n到10^5就需要二分优化那个模板也建议背下来但不是今天讲的重点。// 朴素LIS求最长上升子序列长度 static int lis(int[] arr) { int n arr.length; int[] dp new int[n]; int ans 0; for (int i 0; i n; i) { dp[i] 1; for (int j 0; j i; j) { if (arr[j] arr[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } ans Math.max(ans, dp[i]); } return ans; }状态定义这块我的经验是“从答案往回推”。题目问什么dp状态里就存什么。题目问“最多能走几天”“最多”就是最优值“走几天”就是状态的维度。这样推出来的状态定义一般不会错。4.3 并查集模板连通性问题的万能答案并查集在省赛里几乎每年都有而且经常藏得很深。比如“判断两个点之间是否有路径”“合并朋友圈”“判断图是否成环”底层都是并查集。它是一个非常“接地气”的数据结构把每个集合看成一棵树find找根union合并树。static int[] parent new int[100005]; static int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路径压缩 return parent[x]; } static void union(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) parent[ra] rb; } // 初始化每个元素自成一组 for (int i 1; i n; i) parent[i] i;路径压缩就是“递归时顺手把路径上的所有节点直接挂到根下面”这样下次找的时候一步到位。很多教材还讲按秩合并但在蓝桥杯的规模下路径压缩已经足够快我一般不写按秩合并代码短一点不容易写错。5. 真题实战拆解蓝桥杯2022国赛B组“出差”5.1 题目模型还原与考点识别下面用这套模板库的实际应用来做一次真题实战。以蓝桥杯2022年国赛B组“出差”为例。这道题的背景大概是某工作人员从1号城市出发去n号城市城市之间有道路相连道路有通行时间疫情下每个城市有隔离天数进入该城市必须隔离满相应天数才能继续出门问最早什么时候能到n号城市。我记得这道题刚出的时候讨论区很多人说“看不懂题”或者“以为是搜索”。实际上它的考点非常清晰带点权的最短路。每条边有权重通行时间每个点有权重隔离天数。这类题目在平时训练里出现过很多次套路就是“把点权转成边权”然后再跑最短路。识别考点的方法很简单看到“最早时间”“最短路径”“点之间有权重关系”脑子里第一步先想到最短路如果发现每个点还有额外消耗隔离、等待、带伞出门就把它建模成点权最短路。这不是什么高深的技巧就是刷题量堆出来的“题感”。5.2 状态设计与代码实现Dijkstra堆优化版确定用最短路之后下一步是设计状态。这道题有一个很关键的细节起点的隔离天数不用算终点到达即完成所以终点的隔离天数也不用算。处理方式有两种一种是把起点和终点的隔离天数记为0另一种是在转移时特判。我的代码里用更干净的方案直接在读入后把a[1]和a[n]置零。转移方程是dist[v] dist[u] 边权 a[v]意思是“到达u并隔离完毕、可以出发”的时间加上走这条路的时间再加目的地v的隔离天数得到“到达v并隔离完毕”的时间。由于边权可能是任意正整数BFS排不上用场必须用优先级队列优化的Dijkstra。import java.io.*; import java.util.*; public class Main { static StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); static int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } static class Edge { int to, w; Edge(int to, int w) { this.to to; this.w w; } } public static void main(String[] args) throws IOException { int n nextInt(), m nextInt(); int[] a new int[n 1]; for (int i 1; i n; i) a[i] nextInt(); a[1] 0; a[n] 0; ListEdge[] graph new ArrayList[n 1]; for (int i 1; i n; i) graph[i] new ArrayList(); for (int i 0; i m; i) { int u nextInt(), v nextInt(), w nextInt(); graph[u].add(new Edge(v, w)); graph[v].add(new Edge(u, w)); } long[] dist new long[n 1]; Arrays.fill(dist, Long.MAX_VALUE); dist[1] 0; PriorityQueuelong[] pq new PriorityQueue(Comparator.comparingLong(x - x[1])); pq.offer(new long[]{1, 0}); while (!pq.isEmpty()) { long[] cur pq.poll(); int u (int) cur[0]; long d cur[1]; if (d ! dist[u]) continue; // 跳过过时节点 for (Edge e : graph[u]) { long nd d e.w a[e.to]; if (nd dist[e.to]) { dist[e.to] nd; pq.offer(new long[]{e.to, nd}); } } } out.println(dist[n]); out.flush(); } }这段代码有几点值得专门讲。第一邻接表用ArrayListEdge[]数组的方式比MapInteger, ListEdge快不少也更简洁。第二优先队列里存long[]{节点编号, 距离}用Comparator.comparingLong(x - x[1])按距离排序这是Java 8之后推荐的写法。第三if (d ! dist[u]) continue;是Dijkstra堆优化的标准剪枝防止同一节点被多次更新导致重复计算。5.3 为什么用Dijkstra而不是BFS或SPFA很多同学看到“最短”两个字就想BFS这是个常见误区。BFS能求最短路径的前提是“所有边权相等”比如走迷宫每走一步长度是1。但“出差”里道路通行时间每个城市都不一样隔离天数也不同这时候每条边的实际代价是变化的BFS的“层级递增”特性就不成立了。那为什么不用SPFASPFA在平均情况下跑得快但它最坏时间复杂度很高蓝桥杯的出题人非常清楚SPFA的弱点数据里经常埋了链式图结构专门卡SPFA。Dijkstra堆优化版的最坏时间复杂度是O((V E) log V)稳定不会卡。所以见了最短路我毫不犹豫写Dijkstra。这个经验也可以用一句话概括数据范围在10^5级别、图的规模较大的最短路题直接无脑写堆优化Dijkstra别去省那几行代码。5.4 真题变体考试时如何套模板应对把所有模板都写熟之后考试遇到新题怎么套其实是一个流程问题。我的做题顺序是这样的先读题暴力方法先记在草稿纸上再看数据范围数据量决定算法复杂度然后去模板库里匹配数据结构最后才是写代码。比如“出差”这道题数据范围我记得大概是n和m都在10^5左右直接排除了O(n²)的Floyd也排除了纯BFS剩下的就是Dijkstra堆优化。这就是“数据范围决定算法”的经典应用。如果考场上遇到“最短路隔离天数”的变体比如隔离天数只针对某些城市或者道路有时间窗口其实不用慌。这些都是在点权、边权上做文章核心还是最短路模板只需要在转移方程里加一两个判断条件就行。模板是骨架变题是在骨架上加肉骨架稳了加多少肉都不怕。6. 备赛中的常见问题与避坑笔记6.1 模板看着都会一写就废怎么办很多人都有这个阶段视频看懂了代码复现了一到独立写题就卡住。这是典型的“假懂”状态。解决方法是把模板“默写”出来合上笔记在白纸上调试环境里凭记忆写出快读、DFS、BFS、Dijkstra这四个核心模板。第一遍写不出来很正常第二遍第三遍就熟了。我在备赛时把Dijkstra默写了不下二十遍写到后来闭着眼都能打出来。这个阶段不能急。模板熟练度就像肌肉记忆需要靠重复来形成。我见过有同学一天背五个模板结果考试时全混在一起这个更糟。宁可一天只背一个但保证这个模板能完全独立写出来。第二个有效做法是“改模板”。把求最短路的Dijkstra改成求最长路径的“最长路Dijkstra”把01背包改成完全背包把DFS全排列改成DFS子集枚举。这样一通操作下来你对模板的理解会从“背下来的代码”变成“理解原理的工具”。6.2 数组越界、折半死循环与取模溢出写过Java竞赛代码的同学都知道运行报错有时候比WA答案错误更让人崩溃。数组越界是最常见的尤其是BFS里访问邻接格子的时候nx、ny必须越界判断而且要放在访问grid[nx][ny]之前。顺序反了就是运行时异常。二分死循环是另一个高频坑。写二分的时候while (l r)和while (l r)对边界收缩的要求完全不一样。我建议固定只写一种比如固定用while (l r)然后配套l mid 1、r mid的写法不要混用。混用最容易出现死循环或者mid无法推进的问题。取模溢出在算组合数和DP的时候很容易发生。Java里两个int相乘结果可能超过int范围变成负数。处理方式很简单要么乘之前强转long要么所有涉及乘法的变量直接定义成long。我写蓝桥杯代码的习惯是涉及求和、乘积、计数的一律用long反正Java的long在64位机上是8字节内存开销可以接受。6.3 蓝桥杯考场时间分配与心态调整最后说点考场上实战的东西。蓝桥杯比赛时间一般是4个小时这个时间看起来多但如果前面的题卡壳后面的大题基本没机会做。我的策略是开考先花10分钟把所有题都扫一遍按难度排个序。先把最稳的、一眼能看出模板的题做掉拿到保底分再啃中等题最后一小时留给难题能做多少做多少。还有一个小习惯每做完一道题先别急着提交用题目自带的样例测一遍再自己编一两个边界用例。蓝桥杯是OI赛制许多题目是“按测试点给分”一个样例不过可能让你丢掉不少分。这个细节能让你少丢很多冤枉分。心态方面我特别想说的是遇到陌生题不要慌。蓝桥杯几乎没有“完全没有思路”的题只要你模板库覆盖够广总能从四层模板里找到切入点。实在找不到就退一步想“这题的数据范围能不能暴力”很多看似复杂的题数据范围其实允许暴力枚举暴力拿到的分也比空着强得多。6.4 几个值得长期保留的学习习惯备考结束后我保留了三个习惯现在做工程也受益。第一个是“刷题笔记”每道错题都记录为什么错、哪个知识点不足、下次遇到怎么想。第二个是“模板库版本管理”模板不是一次定稿的我会在每次比赛后把新学到的技巧加进去。第三个是“限时模拟”平时练习也给自己计时模拟考场节奏免得考试时因为时间压力发挥失常。这三个习惯里最推荐大家马上开始的是第一个。你不需要记录得很精致哪怕是手机上随手记两句话也比什么都不记强。因为记录的过程本身就是把“做过的题”转化成“自己的知识”的过程。如果用一句话总结这套方法论那就是把模板练成肌肉记忆把真题当成检验工具。蓝桥杯的结果最终还是由你在赛场上写出的每一行代码决定的而那一行行的代码都来自你现在每一次不偷懒的练习。愿你从这个模板库出发写出属于自己的省一和国奖。