2021蓝桥杯Java B组省赛真题复盘与算法解析-平芜编程栈

说句实在话，2021年4月18日那场蓝桥杯省赛 Java 大学 B 组第一场的真题，在我刷过的历届卷子里属于"性价比"很高的一套。它一共十道题，五道填空、五道编程，填空题每题10分，编程题分值从15分到25分不等，总分150分。难度分布很有代表性：填空题从几乎白送的"空间"到需要动点脑子的"路径"，编程题从模板级的"时间显示"一路爬升到"双向排序""括号序列"这种真正卡人的硬骨头。我后来带过几个学 Java 的朋友复盘这套题，大家的共同感受是——题不难想，但想在规定时间里全做对，比拼的其实是细节和工程习惯。

这篇就当是我自己的一遍完整复盘，把我当时的思路、踩过的坑、以及对照答案之后才想明白的地方，一条条摊开来说清楚。如果你正在准备蓝桥杯的 Java 组，或者单纯想把 Java 的基础语法、算法模板过一遍练手，这套题都值得你从头到尾手敲一遍。下面我分填空、编程、复盘三个大块讲，中间会把每道题的"为什么这么做"讲透，而不是只丢一个答案给你。

1. 这套题为什么值得反复刷：第一场 B 组的难度底色

1.1 五空五编的结构与分值分布

蓝桥杯 Java 大学 B 组省赛的固定结构是十道题，前五道是填空，后五道是编程。填空只需要提交一个数字或者结果，不要求写代码提交，所以很多人会忽略它们的"性价比"——每题10分，五道就是50分，差不多是整个卷面的三分之一。而这几道填空里，真正需要算法思维的其实只有最后两道，前三道本质上考的是细心。

编程题的分值则是阶梯上升，前面的题分数低、容错高，后面的题分数高、也最容易爆零。2021年这套第一场里，"时间显示"和"最少砝码"属于前段，思路清楚就能拿分；"杨辉三角形""双向排序""括号序列"属于后段，尤其后两道，写不出正解的时候连暴力分都不一定稳。这个分值设计本身就在暗示你：时间应该优先砸在填空和中段编程题上，把能拿的分先攥牢，再去啃硬骨头。

我自己的习惯是拿到卷子先花五分钟通读一遍，把题目按"稳""拼""放弃"三档分好。这套题我当时的分类是：填空前四道稳、第五道拼；时间显示稳、最少砝码稳、杨辉三角形拼；双向排序和括号序列先放着，最后有时间再回来。这个策略后来被证明是对的，因为真正拉开差距的往往是"该稳的地方没稳住"。

1.2 第一场相对后续场次的手感差异

蓝桥杯同一年经常有"第一场""第二场"甚至加赛，不同场次的题目风格会有微妙差异。2021年 Java B组第一场给我的整体手感是：偏向基础算法和数学推导，数据结构层面的要求不算特别刁钻。"杨辉三角形"考的是二项式系数的定位，"最少砝码"考的是平衡三进制，"路径"考的是最短路，"括号序列"考的是动态规划计数。这些都属于"想通了就很快，想不通就卡死"的类型。

相比之下，有些后续场次会更偏爱复杂的模拟和数据结构组合，动辄线段树、树状数组。第一场这套题对刚系统学完 Java 基础语法、刷过几十道入门题的人来说，是很好的"承上启下"练习——既能巩固基本功，又能第一次真正体会到大数、去重、图论、DP 这些概念在竞赛题里怎么落地。所以我一直推荐大家把这套题当成"从入门到进阶"的过渡卷来用。

2. 填空题部分：五道题的完整推导链路

2.1 空间：单位换算里藏着的唯一陷阱

第一道"空间"题非常直白：256MB 的内存能存放多少个 32 位二进制整数。这道题几乎就是送分，但每年都有人栽在单位上。关键在于 MB 到字节的换算用的是 1024 而不是 1000，而且 32 位整数占 4 个字节。

我的计算过程是这样的：256MB 先换算成字节，256 × 1024 × 1024 = 268435456 字节。一个 32 位整数是 4 字节，所以能存 268435456 ÷ 4 = 67108864 个。答案就是 67108864。

public class Main { public static void main(String[] args) { long bytes = 256L * 1024 * 1024; System.out.println(bytes / 4); // 67108864 } }

这里的"坑"不在算法，而在两个细节：一是有人会用 1000 来做换算，得到 64000000 这种错答案；二是有人直接写256 * 1024 * 1024而不加L，虽然这道题的数值没溢出 int（268435456 还在 int 范围内），但养成加L的习惯能避免后面的大数题翻车。我在实际敲的时候会先写清楚"字节数"和"每个元素占几个字节"两个中间变量，而不是一行到底，这样复查的时候一眼就能看出逻辑对不对。

2.2 卡片：为什么答案停在3181

第二道"卡片"题是这套填空里我比较喜欢的一道：小蓝有 0 到 9 每个数字各 2021 张卡片，从 1 开始依次拼出 1、2、3……问最多能拼到多少。这道题的直觉是——数字"1"最费，因为从 1 开始数，1 出现的频率最高，所以一定会先耗尽 1。

实现思路是维护一个长度为 10 的数组，记录每个数字还剩多少张。然后从 1 开始枚举，把每个数的每一位拆出来，对应数字的库存减一，一旦某个数字不够用了，说明这个数拼不出来，答案就是前一个数。

import java.util.Arrays; public class Main { public static void main(String[] args) { int[] cnt = new int[10]; Arrays.fill(cnt, 2021); for (int i = 1; ; i++) { int x = i; while (x > 0) { int d = x % 10; if (--cnt[d] < 0) { System.out.println(i - 1); return; } x /= 10; } } } }

运行结果是 3181。这里有个容易踩的坑：判断"不够用"的时机。如果你在拆完一个数的所有位之后才统一判断，那就会把已经部分消耗的库存算错。正确做法是每减一张就立刻检查是否变负，一旦变负就说明当前这个数已经无法完整拼出，答案就是i - 1。这个"边减边判"的细节，我第一遍写的时候就写错过，减完才发现超了，结果答案偏了几十，非常隐蔽。

2.3 直线：暴力枚举为什么必须去重

第三道"直线"题：平面上 x 在 0 到 19、y 在 0 到 20 的所有整数点，共 20 × 21 = 420 个点，问这些点一共能确定多少条不同的直线。答案我记得是 40257。

这道题的"暴力"思路很直接：枚举所有点对，每对点确定一条直线，然后把重复的直线去掉。但难点在于"如何表示一条直线才能正确去重"。斜率加截距的做法会遇到精度问题，而且斜率为无穷（竖直线）要单独处理。稳妥的做法是用直线的通用式 Ax + By + C = 0，把 A、B、C 三个系数约分到最简整数比之后拼成字符串塞进 HashSet。

import java.util.HashSet; import java.util.Set; public class Main { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public static void main(String[] args) { Set<String> lines = new HashSet<>(); int n = 20, m = 21; for (int x1 = 0; x1 < n; x1++) for (int y1 = 0; y1 < m; y1++) for (int x2 = 0; x2 < n; x2++) for (int y2 = 0; y2 < m; y2++) { if (x1 == x2 && y1 == y2) continue; int A = y2 - y1; int B = x1 - x2; int C = x2 * y1 - x1 * y2; int g = gcd(gcd(Math.abs(A), Math.abs(B)), Math.abs(C)); if (g != 0) { A /= g; B /= g; C /= g; } // 统一符号，避免 (A,B,C) 和 (-A,-B,-C) 被当成两条线 if (A < 0 || (A == 0 && B < 0)) { A = -A; B = -B; C = -C; } lines.add(A + "," + B + "," + C); } System.out.println(lines.size()); // 40257 } }

这里最容易被忽略的是"符号统一"。如果不处理，(1,2,3)和(-1,-2,-3)会被当成两条不同的直线存进去，结果就偏大。我在实际写的时候，除了约分，还会顺手把 A 的符号统一为正，A 为零时把 B 统一为正，这样同一族直线就只会留下一个代表。这道题也再次印证了一个经验：能用整数表示就绝不用浮点数去重，double 的精度误差在这种大规模枚举里是灾难。

2.4 货物摆放：大数因式分解之后的组合计数

第四道"货物摆放"给了你一个大数 n = 2021041820210418，问有多少组正整数 (L, W, H) 满足 L × W × H = n。答案是 2430。

这道题的坑在于 n 很大，大约在 2 × 10^15 这个量级，直接双重循环枚举肯定超时。正解是先对 n 做因数分解，拿到它的质因数之后，把指数分配给三个变量。也就是说，如果 n = p1^a1 × p2^a2 × … × pk^ak，那么我们要把每个质因数的"次数"分摊到 L、W、H 三个位置上，然后统计满足乘积等于 n 的分配方案数。

思路可以分两步走：先求出 n 的所有因数（数量不多，因为 n 的因数个数是有限的），然后三重枚举因数 a、b，如果 a × b 能整除 n，就说明 c = n / (a × b) 也是因数，方案数加一。

public class Main { public static void main(String[] args) { long n = 2021041820210418L; java.util.List<Long> divs = new java.util.ArrayList<>(); for (long i = 1; i * i <= n; i++) { if (n % i == 0) { divs.add(i); if (i != n / i) divs.add(n / i); } } int ans = 0; for (long a : divs) for (long b : divs) if (n % (a * b) == 0) ans++; System.out.println(ans); // 2430 } }

注意这里的a * b已经是 n 量级的有理数，虽然理论上可能溢出 long（n 本身接近 2 × 10^15，两个因数相乘理论上可能超过 9 × 10^18 的 long 上限），但实际因为 a、b 都是 n 的因数，乘积只要不超过 n 的量级就没问题；更稳妥的写法是先把 a 除以它与 n 的最大公约数之类的技巧，不过这道题实测直接算不会溢出。这个"因数个数其实不多"的观察很关键——n 的因数个数通常只有几百到几千，三重枚举完全跑得动。

2.5 路径：把最小公倍数当作边权的最短路

第五道"路径"是填空题里最像编程题的一道：有 2021 个点，编号 1 到 2021，任意两点 i 和 j 之间的边权是它们的最小公倍数 lcm(i, j)，问从点 1 到点 2021 的最短路径长度。答案我记得是 10266837。

这本质上是一道最短路问题，只是边权需要现算。因为点数 2021 并不大，而且每个点只和相邻若干个点有"便宜"的边（lcm 越小，边权越小），所以建图的时候可以做一点剪枝：不是所有点对都要连边，只连那些 lcm 相对小的边就够了。实际做法通常是在 Dijkstra 里，对每个当前点，只向后枚举一定范围内的点计算 lcm 作为边权。

import java.util.PriorityQueue; public class Main { static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } static long lcm(long a, long b) { return a / gcd(a, b) * b; } public static void main(String[] args) { int N = 2021; long[] dist = new long[N + 1]; boolean[] vis = new boolean[N + 1]; java.util.Arrays.fill(dist, Long.MAX_VALUE); dist[1] = 0; PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[1], y[1])); pq.add(new long[]{1, 0}); while (!pq.isEmpty()) { long[] cur = pq.poll(); int u = (int) cur[0]; if (vis[u]) continue; vis[u] = true; for (int v = 1; v <= N; v++) { if (v == u) continue; long w = lcm(u, v); if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.add(new long[]{v, dist[v]}); } } } System.out.println(dist[N]); // 10266837 } }

这里要提醒的是，边权不是 1，而是 lcm，数值可能很大，所以 dist 数组要用 long。这道题如果用 Floyd 那种 O(n³) 的算法，2021³ 大约是 8 × 10^9，肯定跑不动，必须用 Dijkstra 或者 SPFA。我个人更推荐 Dijkstra 加优先队列，因为边权都是正数，稳妥又快。

3. 编程题部分：从时间显示到括号序列的实现细节

3.1 时间显示：10^18级毫秒数的取模套路

"时间显示"题面大概是：给定一个整数，表示从某个基准时刻开始的毫秒数，要求输出它对应的时:分:秒，24 小时制，只显示时分秒不显示日期。输入范围很大，能到 10^18 级别，这决定了你必须用 long，而且要用取模把"天"的部分去掉。

核心就一句话：先把毫秒除以 1000 得到秒，再对一天的秒数 86400 取模，剩下的就是一天之内的时间，然后分别算时、分、秒。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long ms = sc.nextLong(); long s = ms / 1000; s %= 86400; long h = s / 3600; long m = s % 3600 / 60; long sec = s % 60; System.out.printf("%02d:%02d:%02d%n", h, m, sec); } }

样例里，输入 46800999 应该输出 13:00:00，输入 1618708103123 应该输出 01:08:23。我特意验算了第二个：1618708103123 毫秒等于 1618708103.123 秒，对 86400 取模后是 4103 秒，4103 秒正好是 1 小时 8 分 23 秒，对上了。

这道题有两个细节值得注意：一是整除和取模的顺序，先除以 1000 再取模，避免直接用毫秒取模把毫秒的余数混进来；二是输出格式，%02d保证补零，否则会出现1:8:23这种错误格式。这类"格式化输出"题在蓝桥杯里很常见，我踩过的坑是忘了补零导致样例对不上。

3.2 最少砝码：平衡三进制的一次直觉训练

"最少砝码"是一道很容易想偏的题。题面大意是：用一架天平称出 1 到 N 之间所有整数重量，砝码可以放在天平的任意一边，问最少需要多少个砝码。很多人第一反应是二进制拆分的思路——砝码只能放一边，那确实是用 1、2、4、8 这样的二进制。但砝码能放两边，问题就变成了平衡三进制。

为什么是 3 的幂？想象你有一组砝码重量是 1、3、9、27……，因为每个砝码可以放在"物体同侧""物体异侧""不放"三种状态，所以 k 个砝码能表示的范围是 3^k 种组合，能称出的重量范围是 1 到 (3^k - 1) / 2。要称出 1 到 N，就要找最小的 k 使得 (3^k - 1) / 2 ≥ N。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); long sum = 0, w = 1; int ans = 0; while (sum < n) { sum += w; w *= 3; ans++; } System.out.println(ans); } }

举个直观的例子：要称 1 到 4，用 1 和 3 两个砝码就够了（1、(3-1)、3、(3+1) 对应 1、2、3、4）。要称到 5 就不够了，得再加一个 9，三个砝码能覆盖到 13。这个"1、3、9、27"的序列最好记，考试的时候甚至可以不写程序，直接手算找第一个大于等于 N 的覆盖点。

这道题的坑在于容易把它当成背包或者贪心去做，绕一大圈。其实抓住"每个砝码三态"这个本质，问题就退化成一个简单的累加。我后来总结，遇到"天平称重""最少砝码"这种关键词，第一时间就该想到三进制。

3.3 杨辉三角形：第一次出现的定位策略

"杨辉三角形"题面是：输入一个正整数 N，输出 N 第一次出现在杨辉三角中的位置。位置的编号规则是，按行从上到下、行内从左到右依次编号，从 1 开始。

这道题的暴力做法是逐行生成杨辉三角，遇到 N 就输出位置，但对大 N 会爆。正解要利用杨辉三角的对称性和二项式系数。观察一个结论：N 第一次出现的位置，要么在比较靠左的列上（列号很小），要么就是它作为某一行的第二个数出现（因为 C(N,1) = N，第二列就是自然数序列）。

所以策略是：从列号 k = 2 开始往上枚举（列号越小，位置越靠前），对每个 k 用二分查找找到满足 C(n, k) = N 的行号 n，算出位置，取所有候选中位置最小的那个。同时别忘了 N 作为第二列元素出现的位置 C(N, 1) 对应第 N 行。

位置的计算公式是：第 n 行（0 开始计数）前面有 n(n+1)/2 个元素，行内第 k 个元素（0 开始）对应的总编号是 n(n+1)/2 + k + 1。枚举时把每个 k 对应的位置算出来，取最小。

public class Main { static long N; static long C(long n, long k) { long res = 1; for (long i = 1; i <= k; i++) { res = res * (n - i + 1) / i; if (res > N) return res; // 提前剪枝防溢出 } return res; } public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); N = sc.nextLong(); long ans = Long.MAX_VALUE; // N 出现在第二列：第 N 行，第 1 个（0 开始） ans = Math.min(ans, N * (N + 1) / 2 + 2); for (long k = 2; k <= 30; k++) { long lo = 2 * k, hi = N, pos = -1; while (lo <= hi) { long mid = (lo + hi) / 2; long val = C(mid, k); if (val == N) { pos = mid; break; } else if (val < N) lo = mid + 1; else hi = mid - 1; } if (pos != -1) ans = Math.min(ans, pos * (pos + 1) / 2 + k + 1); } System.out.println(ans); } }

这道题有两个必须注意的点。第一是组合数计算要提前剪枝，否则中间结果会溢出 long，得到错误的比较结果。第二是k的枚举上界，一般枚举到 30 左右就够了，因为 C(n, k) 随 k 增长得极快，列号稍大就迅速超过 N 的量级。我第一遍写的时候忘了剪枝，res * (n - i + 1)直接溢出了，二分完全跑飞。