1. 这一届省赛的难度坐标为什么Java B组值得单独复盘第十二届蓝桥杯2021年省赛真题Java 大学B组 第一场是我带赛这几年里难度曲线最“标准”的一套题。说它标准是因为它没有出现特别冷门的算法但每一道题都在逼你反复做决定暴力能不能过要不要优化如果优化从哪里下手最划算考完当天我让参赛的学生把每道题的代码和思考过程发给我整理完发现一个很有意思的现象拿省一的同学不一定每道题都会做但一定会在会做的题上拿满失手的同学很多不是不懂算法而是输在输入输出、类型越界和做题节奏这些看起来很“低级”的地方。这篇文章不打算把十道题从头到尾念一遍答案而是从Java B组选手的角度把这套题里最有代表性的算法模型、最容易被Java实现坑到的地方以及现场做题的时间分配完整复盘一遍。如果你正在准备蓝桥杯尤其是准备用Java参赛这篇内容会比单纯刷题更有参考价值。1.1 题目结构里藏着的老套路与新信号第十二届省赛第一场Java B组一共10道题5道结果填空5道编程大题。根据我手头整理的赛后回忆版填空部分涉及卡片计数、平面直线去重、约数枚举、图论最短路编程大题里有时间显示、砝码称重、杨辉三角形、双向排序、括号序列。这个结构和往届相比没有大变化但有几个信号值得注意。第一个信号是“卡片”这种题。它表面是数位统计实际考的是枚举范围和边界分析。很多人在考场上一看到数字就循环拼接拼到某个数发现卡片不够了但忘了问自己一个问题消耗最快的到底是哪张卡片这道题里数字1的消耗速度远超其他卡片你需要关注的是“1”的累计消耗量而不是自然数个数。这种稍微绕一下弯的考法比直接让你数数更有区分度。第二个信号是“直线”这类几何题。它考的并不是几何公式而是去重逻辑。平面上21乘21的整数点任意两点确定一条直线问总共有多少条不同直线。难点在于两条直线如果在数学上是同一条不能因为枚举点对顺序不同就重复统计。这个去重过程一旦用浮点数存斜率很容易因精度误差翻车。所以这类题真正考察的是“用整数表示几何对象”的能力这是很多刷题量不够的人完全没想到的。第三个信号更加明确最后两道题把思维难度明显往上拉了一个台阶。整套题的前半段基本是枚举、数论、图论的基础组合到了后半段动态规划、数据结构、组合计数的混合考察开始出现省一和省二的差距基本就在这些题目上拉开。这也提醒后来的备赛者不要只盯着简单的模拟题刷蓝桥杯的难度并没有停留在“暴力能过”的水平线上。1.2 送分题和分水岭题的大致分布如果按分数和难度给这套题画一条线我个人会把前六题归为“必须拿满”的区间后四题归为“拉开差距”的区间。前六题里有几道只需要基本的枚举和数学推导但每个题都有至少一个隐蔽的坑。卡片题要注意卡片消耗的边界直线题要注意去重货物摆放题不能三重循环硬算必须先筛约数路径题要小心lcm的数据范围时间显示题要处理毫秒和long类型砝码称重题则考验最基本的动态规划状态设计。这些坑单独拿出来都很浅但比赛是限时的又是连续做题很多人在前面积累的焦虑感会直接带到后面。我见过有选手在直线题卡了四十分钟导致后面的双向排序几乎没有时间写其实直线题如果一开始就想到用约分后的整数表示直线几分钟就能解决。后四题则是典型的选拔题。杨辉三角形需要组合数知识和二分查找双向排序考察对区间操作本质的理解括号序列则是比较复杂的计数DP。这些题目没有一个能靠背模板直接解决必须现场分析性质。有一点对Java选手特别重要后几题的运行时间压力和代码实现成本都比前几题高选Java本身在常数上不占优势所以前面的题更不应该失分否则后面翻盘的余地很小。2. 从真题里抽出的四个核心算法模型2.1 路径题小范围最短路不一定非要Dijkstra路径题的大意是有2021个节点如果两个节点编号之差的绝对值小于等于21就在它们之间连一条无向边边权是两个节点编号的最小公倍数求1号节点到2021号节点的最短路径。一看到“最短路”很多人第一反应是Dijkstra。这道题用Dijkstra当然能做但在Java里要维护优先队列还要用数组模拟Pair代码量不小现场容易写错。这道题其实有一个很强的条件任意一条边连接的两个节点编号差不超过21。这意味着从1号节点走到任意节点i最后一步一定是从i-21到i-1之间的某个节点走过来的。既然所有能到达i的边都来自编号比i小的节点那我们可以直接用一维数组dist[i]表示从1到i的最短路径然后按照i从1到2021的顺序递推。推导关系是dist[i] min(dist[j] lcm(i, j))其中 i - 21 ≤ j i写出来就是下面这段Java代码import java.util.Arrays; public class Main { static int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } static long lcm(int a, int b) { return (long) a / gcd(a, b) * b; } public static void main(String[] args) { int n 2021; long[] dist new long[n 1]; Arrays.fill(dist, Long.MAX_VALUE / 4); dist[1] 0; for (int i 1; i n; i) { for (int j i 1; j n j - i 21; j) { long w lcm(i, j); if (dist[i] w dist[j]) { dist[j] dist[i] w; } } } System.out.println(dist[n]); } }这里有几个地方必须注意。第一dist数组初始值不能直接设成Long.MAX_VALUE因为后面dist[i] w可能会溢出成负数导致结果错误建议设成Long.MAX_VALUE / 4这种足够大的安全值。第二lcm的计算先除后乘避免中间结果超过long范围。第三虽然图是无向的但这里只从小编号向大编号更新是因为递推顺序已经保证dist[i]在计算所有大于i的节点之前就是最优值这是这道题能不用队列的原因。赛后我核对的答案是10266837。这题的价值在于提醒我们算法模板要会但更重要的是识别题目里的特殊条件。最短路并不一定要跑Dijkstra或SPFA当图的结构有单调方向时动态规划往往是更简洁的解法。2.2 时间显示题一眼题也要检查类型和格式化时间显示这道题题目描述大概是输入一个毫秒数要求输出对应的当天时间忽略年、月、日只输出时、分、秒。看起来简单到不能再简单但Java组在这道题上栽跟头的人并不少。最容易犯的错误就是用int去读输入。题目给的毫秒数可能非常大int根本装不下一旦越界读进来就是负数后续运算全部白费。这道题必须用long接收输入。正确做法是先除以1000把毫秒转成秒再对一天的秒数86400取模然后分别算时、分、秒。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long t sc.nextLong(); t / 1000; t % 86400; long h t / 3600; long m t / 60 % 60; long s t % 60; System.out.printf(%02d:%02d:%02d%n, h, m, s); } }这里有一个容易被忽略的细节如果直接把System.out.printf里的格式串写成%02d:%02d:%02d\n在部分OJ上也能过但用%n更符合跨平台换行习惯。另外有些同学看到时间就想到java.util.Date和SimpleDateFormat这在这道题里反而会踩坑因为Date默认依赖系统时区如果不做时区处理输出结果可能和预期差8个小时。这道题给我们的启发是越简单的题越要检查数据类型和输出格式。竞赛里经常出现题意完全读懂、解法完全正确却因为int越界或者格式化不对而0分的情况。时间显示题就是一个经典教训。2.3 砝码称重用布尔数组维护可达集合砝码称重是这套题里很有代表性的一道动态规划。题目给出一组砝码每个砝码可以放天平左边、右边也可以不放问能称出多少种不同的正整数重量。这题最经典的解法是用布尔数组维护所有可达重量。初始状态是dp[0] true表示重量0可达。每来一个砝码w对于当前已经可达的每一个重量x我们可以得到三个新状态x本身x w以及Math.abs(x - w)。为了不让同一个砝码被重复使用需要通过临时数组ndp来记录下一轮的状态。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] weights new int[n]; int sum 0; for (int i 0; i n; i) { weights[i] sc.nextInt(); sum weights[i]; } boolean[] dp new boolean[sum 1]; dp[0] true; for (int w : weights) { boolean[] ndp dp.clone(); for (int x 0; x sum; x) { if (dp[x]) { if (x w sum) { ndp[x w] true; } ndp[Math.abs(x - w)] true; } } dp ndp; } int ans 0; for (int i 1; i sum; i) { if (dp[i]) { ans; } } System.out.println(ans); } }有些同学会问为什么要用临时数组而不是直接在dp数组上从大到小更新因为砝码称重的转移里有Math.abs(x - w)这种转移不是简单的“只能从更小状态转移到更大状态”如果原地更新同一个砝码可能被使用多次结果就错了。用临时数组虽然多开了一点空间但保证了每轮只考虑一个新砝码。这道题的复杂度是O(n * sum)其中n是砝码数量sum是所有砝码重量之和。n通常不会超过100sum一般不超过100000所以这个算法在Java里跑起来没有任何压力。这个模型其实非常通用以后遇到“给定一些数通过加减操作能得到多少种结果”的题目都可以往这个思路上靠。2.4 杨辉三角形、双向排序、括号序列省一争夺区的关键最后几道题是很多人眼中的“拦路虎”但拆开看它们考的东西并不超纲。杨辉三角形那道题要求找某个数N在杨辉三角形中第一次出现的位置。这题第一反应是建一个二维数组模拟杨辉三角形但N可以很大二维表根本开不下。正确的切入点是观察杨辉三角形的对称性和单调性。每一行从两端向中间递增同时组合数C(n, k)在n增大的时候也会变大。对固定的k可以用二分查找n找到第一个使得C(n, k) N的位置再根据组合数大小和位置关系计算序号。Java实现时比较头疼的是组合数可能溢出需要在累乘过程中及时判断是否超过N超过就直接返回一个很大的值避免long爆掉。双向排序那道题如果直接用Arrays.sort模拟思路完全正确但n和m都到十万级别的时候复杂度是O(m * n log n)必然超时。现场先写暴力版本拿部分分是合理的但想拿高分必须观察操作的性质。连续相同类型的排序操作很多是冗余的可以压缩再进一步序列的最终形态往往是从两端向中间“逐渐固定”的过程可以用双端队列或链表边处理操作边维护边界而不是真的做排序。网上有大佬用TreeSet维护未固定的位置思路更巧妙。老实说这题我在现场没能一次写对但复盘时发现它其实不考高级数据结构考的是对操作序列的抽象能力。括号序列那道题则把动态规划推到了计数层面。最少添加几个括号才能让整个序列合法并且还要输出方案数这个“方案数”三个字让题目难度上了一个台阶。核心思路是把左括号看作1右括号看作-1然后分别处理前缀最小值和后缀最大值。状态设计通常是dp[i][j]表示前i个字符中左括号比右括号多j个时的方案数转移时考虑添加左括号还是右括号。要注意计数不能重复同一个结果只能被统计一次这需要仔细推转移顺序。这类题不是靠背板子能解决的建议多找几道类似的括号DP题练手。3. Java选手在赛场上最容易踩的坑3.1 输入输出Scanner慢不是错觉蓝桥杯Java组的大多数人喜欢用Scanner因为写起来简单一个Scanner就能读所有类型。但Scanner底层在做正则解析遇到大规模输入时开销很大。省赛的输入规模通常没有到极端程度用Scanner多数时候也能过但万一遇到后面几题的输入量比较大Scanner多出来的几百毫秒可能就会让你TLE。更稳妥的做法是记住一个模板用BufferedReader逐行读再用split分割。比如import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(in.readLine()); String[] parts in.readLine().split( ); // 假设后面有n个整数 int[] arr new int[n]; for (int i 0; i n; i) { arr[i] Integer.parseInt(parts[i]); } } }如果输入规模再大可以把split换成StringTokenizer或者自己写一个FastScanner。平时练习时多准备几套输入模板比赛时直接套用省下来的调试时间都是实打实的分数。3.2 类型越界long不是你想用才用Java的int是32位最大值约21亿。蓝桥杯很多题目的数据范围远超这个数尤其是和时间、最短路、组合数相关的题目。时间显示题里的毫秒数可能到十的十八次方级别路径题里的dist累计值也轻松超过int砝码称重的总重量sum加起来同样可能爆int。写代码时有一个简单原则只要题目里出现天数、距离、方案数、最大值累加第一个念头就应该是long。还要小心隐式类型转换。int和int相乘结果仍然是int只有在赋值给long时才可能被自动扩展但乘法本身已经溢出了。所以如果两个int相乘可能超范围要在乘法开头就加上Llong value 1L * a * b;很多同学在本地测试时因为数据小没暴露这个问题一交上去就全错还找不到原因。建议在写题时先看一眼数据范围把每个变量的类型标清楚不要指望最后再统一改。3.3 集合框架和对象创建的隐形成本Java的HashMap、HashSet、PriorityQueue确实好用但凡事都有代价。比如直线去重那道题如果你用double键存HashMap不仅存在精度问题还可能在大量插入时触发扩容和哈希碰撞导致程序跑得很慢。更好的做法是枚举点对后把直线方程约分成一串整数比如Ax By C 0的系数三元组统一符号后拼接成字符串再放到HashSet里。虽然还是用集合但至少避免了浮点精度问题。再比如优先队列里存节点如果你每次都new一个int[]数组来当Pair用会产生大量临时对象触发GC。Java的GC在竞赛环境里虽然不会频繁发生但在最短路径这类循环次数很多的场景下对象创建太多确实会让运行时间明显变差。可以自己写一个简单的Pair类重用对象或者直接用二维数组模拟优先队列。总之能用基本类型和数组解决的问题就不要引入多余的对象。3.4 现场WA与TLE的排查顺序在赛场上遇到错误最忌讳的是东改一下西改一下。我一般建议按固定顺序排查先看样例是否能过再看边界数据然后是类型和输出格式最后才是算法复杂度。很多WA不是因为思路错而是因为输出少了换行、多了空格或者没有用%02d补零。先把这些“物理错误”排除再回头检查代码逻辑。如果是TLE不要立刻怀疑Java本身慢。先估算自己的算法复杂度看是不是在最坏数据下跑不完。比如双向排序如果直接sort最坏情况绝对超时这时候再怎么优化输入输出都没有用。相反砝码称重这种O(n * sum)的题如果TLE大概率是数组越界或者某个循环写了死循环。TLE的排查核心是“先看复杂度再抠常数”顺序不能反。4. 现场做题的节奏管理和部分分策略4.1 前60分钟怎么分配才不亏蓝桥杯省赛的考试时间是4小时看似很长但10道题堆在一起时间非常紧张。我的建议是前60分钟集中处理填空和简单的编程题。填空只填答案不需要交代码所以可以用最暴力的方式在本机跑跑得慢也没关系。比如卡片题、直线题、货物摆放题都可以用多层循环枚举只要剪枝到位几秒内能出结果就行。编程题里时间显示和砝码称重代码量不大想清楚后二十分钟内可以写完。这样前一个小时基本能确定拿到五道题的分数心里就稳了。千万别在第一道填空题上反复纠结如果五分钟没有思路应该直接跳到后面。比赛比的不是单题谁做得久而是总分谁高。4.2 暴力解法的正确打开方式很多选手觉得暴力解法丢人其实在蓝桥杯里暴力是拿分的重要手段。特别是面对后面几道难题时先用最暴力的方法把题目跑通至少能拿到一部分测试点的分数。比如杨辉三角形如果N比较小直接生成前1000行杨辉三角然后查找位置就能过掉一部分数据双向排序也可以直接用Arrays.sort模拟拿到百分之三十左右的分数。暴力解法的第二个价值是验证。写优化算法时可以保留一个暴力版本生成随机小数据来做对拍。一旦发现自己优化版本结果和暴力不同说明优化思路有bug可以及时修正而不是盲目提交。这个习惯在准备阶段就要养成考场才不会慌。4.3 压轴题没有思路时的“抢救”套路如果压轴题完全没有思路先不要放弃试着拆解题目条件。括号序列最少添加数一般都是动态规划双向排序最后的序列变化通常和操作压缩有关杨辉三角形的第一次出现位置大概率借助组合数二分。每个算法标签都能带来一些方向。另外要注意部分分的获取不一定要写完整的算法。比如题目要求输出方案数你可以先写一个只处理小数据的DFS把样例过了至少能拿前面几个测试点的分。不要小看这些零散的分数省赛的分数线有时候就差那十分。考试最后半小时不要再挑战难题把已经写出来的代码重新读一遍检查有没有低级错误这种“守成”策略往往比临场钻研新题更划算。5. 以这套题为参照的备赛清单5.1 Java选手必须能默写的算法骨架从这套2021年省赛真题反推有一些算法和模板是Java选手必须熟练掌握的。不需要背到一字不差但至少要能十分钟内无错写出来。下面是我整理的高频清单算法/模板主要用途本套题对应欧几里得gcd与lcm数论运算、边权计算路径题数组作为布尔集合可行性DP、状态压缩砝码称重前缀和与差分区间操作优化双向排序相关组合数计算与二分查找、计数杨辉三角形括号序列DP合法性判断、方案计数括号序列快速幂取模运算、组合计数可能出现在数论题朴素Dijkstra小规模最短路兜底路径题的备用方案质因数分解/约数枚举枚举优化货物摆放这里想特别强调约数枚举。货物摆放题如果不知道先筛约数基本不可能跑出结果。这个技巧在蓝桥杯里出现频率很高值得单独多练几道。组合数二分也是平时不练考场上一紧张很容易把二分的上下界写错。5.2 真题刷三遍比刷十套更有用很多人刷蓝桥杯真题的方式是“做一遍看题解下一套”这样效果其实很差。更有效的方式是把同一套真题做三遍。第一遍严格限时模拟考场环境做完之后记录哪些题卡了多久哪些题完全没有思路。第二遍对照题解把每一道题的完整思路和代码都吃透尤其是自己不会的题独立重新写一遍。第三遍隔一两周再限时做一次重点看上次卡住的地方这次能不能顺畅突破。以第十二届省赛Java B组第一场为例第一遍你可能发现自己在直线题上浪费太多时间第二遍把直线去重的整数表示法熟练掌握第三遍再遇到类似几何去重题时就应该条件反射地想到约分和HashSet。这种“以题带点”的复盘方式比盲目追求刷题数量有价值得多。5.3 选Java组之前先想清楚这几件事最后聊一个很多同学纠结的问题到底选Java还是C蓝桥杯允许Java组参赛且Java有丰富的集合类库、大数类写起来确实方便。但Java在运行速度上不占优势同样的算法C可能一秒跑完Java可能需要两秒。因此在准备阶段就要养成“常数意识”能用O(n)就不用O(n log n)能剪枝就剪枝。如果你的编程基础是为工作面试准备的未来主要写Java那参加Java组顺理成章。如果只是为了竞赛拿奖而且学校没有强制语言那么C在竞赛场景下的资料更多、运行速度更快确实有一定优势。但语言只是工具真正决定你能拿多少分的是算法理解和现场调试能力。Java选手只要把输入输出模板、类型边界、常见算法骨架都准备到位完全有能力冲击省一。带了几届蓝桥杯之后我越来越觉得2021年这套Java B组第一场真题特别适合用来做“省赛体检”。它不靠偏题怪题打击你但会把你的真实水平暴露得明明白白。如果你时间有限与其贪多刷十套不如把这一套做三遍第一遍摸底第二遍补算法第三遍限时重做重点盯自己上次卡住的地方。等你能在两个半小时内稳定拿到80分以上省一基本就稳了。