第十二届蓝桥杯 2021 年省赛真题的 Java 大学 B 组第一场在我见过的所有省赛卷子里算得上友好但阴险的一类。友好在于十道题没有一道需要特别高阶的数据结构阴险在于填空题的两道数学题加上编程题里的边界处理稍不留神就会把到手的分丢掉。我前后完整做过两遍也拿这套题给几个刚学 Java 的朋友当过练习材料发现大家栽跟头的地方高度重合不是不会算法而是没把这道题到底在问什么想透。这篇就把这套真题从第一题到最后一道从头捋一遍讲清楚每道题的题意、突破口、常见坑以及我当时是怎么写出能过全部测试点的代码的。无论你是第一次接触蓝桥杯还是已经刷过几套题想回头查漏补缺这套卷子都值得当作基础功体检来做一遍。1. 先看清这套卷子的整体骨架1.1 150 分是怎么分布的蓝桥杯 Java 大学 B 组的省赛卷子这些年一直是五道填空题 五道编程题的结构总分 150 分。这套 2021 年第一场也不例外具体分值我整理成了下面这张表方便你对每道题该花多少时间心里有数。题号题目名称题型分值核心考点AASC填空5ASCII 编码常识B卡片填空5模拟枚举与终止判断C直线填空10去重与浮点误差处理D货物摆放填空10约数枚举与质因数分解E路径填空15最短路与边权剪枝F时间显示编程15取模运算与格式化G最少砝码编程20三进制与进制思想H杨辉三角形编程20组合数与二分查找I双向排序编程25模拟优化与栈思想J括号序列编程25动态规划与计数填空题的分是要么全对要么零分编程题则是按测试点给分。这个结构决定了一个非常现实的备赛策略填空题必须稳编程题尽量把能拿的分都拿到。很多人一上来死磕最后两道 25 分的难题结果前面本该稳拿的题反倒因为手抖写错这就很亏。我个人的经验是省赛 4 小时里前一个小时应该把五道填空题全部解决并且反复验证接下来一个半小时拿编程题里简单的三道剩下时间再去攻压轴。这个节奏能保证你在时间耗尽前拿到一个体面的分数。1.2 这套题真正的难点在哪把这十道题摊开看你会发现一个很有意思的现象它考的不是你会不会某种高级算法而是你能不能把一道看起来朴素的问题转化成可以用程序精确描述的形式。比如 C 题直线题目本身就是初中几何但它藏了一个致命的坑——用double算斜率然后去重几乎必然出错因为浮点误差会让两条本该相同的直线被判成不同。E 题路径也是表面是最短路但你不可能把 2021 个点两两连边去跑 Dijkstra必须想到只连差值在某个范围内的边这个剪枝。再比如 G 题最少砝码如果你不知道天平砝码问题跟三进制的对应关系很可能卡在用什么策略去凑出 1 到 N 的所有重量上。而 H 题杨辉三角形看似暴力就能做实则要理解杨辉三角里某个数第一次出现的位置到底该怎么定义、怎么二分。说白了这套题的分水岭就在于你愿不愿意在动手写代码之前先把问题的数学结构想清楚。想清楚了代码往往只有二三十行想不清楚写两百行也过不了。1.3 我建议的做题顺序如果你做这套卷子当练习我强烈建议按这个顺序来A → B → F → G → H → C → D → E → J → I。理由是这样的A、B 是纯送分几分钟能搞定先把分数落袋为安F 时间显示是简单的取模热热身G、H 是经典的进制思想和组合数属于想通了就简单的中档题放在状态好的时候做C、D、E 三道填空题需要静下心算适合大脑清醒的时候集中处理最后的 J 括号序列和 I 双向排序是压轴放在后面能拿多少拿多少。当然这只是我摸索出来的顺序你要是有自己习惯的节奏完全可以调整。关键是别在开局就一头扎进难题里出不来。2. 五道填空题的解题思路与答案2.1 试题 AASC——最简单的送分题题目描述得很绕已知大写字母 A 的 ASCII 码是 65求这个表示本身……其实就是让你输出 A 的 ASCII 码。这题不需要写复杂代码一行System.out.println((int)A);就能得到 65。但我要特意提醒一句越是这种送分题越要小心看题。蓝桥杯有些年份会在这里玩文字游戏比如求某个字符的 ASCII 码加 1 是多少之类。这道题问的是 A 的 ASCII 值答案就是 65。如果你用 Java 写(int)A得到的就是 65如果你脑子里默认所有编码都是 ASCII那也没问题因为题目明确说了 A 是 65。这种题存在的意义就是让你快速进入状态。5 分不多但它决定了你考试开头的心态。我见过有人在这题上纠结A 到底是 65 还是 64白白浪费十分钟实在划不来。记住大写 A 是 65小写 a 是 97数字 0 是 48这三个是最基本的常用值。2.2 试题 B卡片——终止条件写对才拿分这道题是这样的小蓝手里有 0 到 9 每个数字各 2021 张卡片他想从 1 开始一个接一个地拼正整数1、2、3……每拼一个数就要消耗掉对应数字的卡片。问最多能拼到几。这题的正确做法是老老实实模拟从 1 开始逐个数地扣减卡片一旦某个数字的卡片在拼某个数的过程中被扣成负数就说明这个数拼不出来答案就是前一个数。public class Main { public static void main(String[] args) { int[] card new int[10]; for (int i 0; i 10; i) card[i] 2021; int num 1; outer: while (true) { int x num; while (x 0) { int d x % 10; if (card[d] 0) { // 这个数字拼不出来了 System.out.println(num - 1); break outer; } card[d]--; x / 10; } num; } } }跑出来的答案是 3181。为什么是这个数因为从 1 拼到 3181 的过程中恰好把某一位实际是数字 1的 2021 张卡片用光了。具体来说拼 1 到 3181 消耗的1这个数字正好是 2021 个到 3182 的时候就不够用了。注意这题最容易被扣分的地方是终止判断的位置。如果你在扣减完一位数字之后才判断卡片是否耗尽或者用卡片变成负数来判断逻辑就容易写反。正确做法是先检查有没有卡片够就扣、不够就停并且停的时候答案要回退一个数。我身边有个朋友一开始写的是if (card[d] 0)才停结果多拼了一个数答案错成 3182。这种错误非常典型本质上就是边界判断提前还是滞后的问题。写模拟题的时候一定要在脑子里把最后一个数是怎么被拒绝的走一遍。2.3 试题 C直线——别用 double 去重这道题问的是平面上有 20 行 21 列共 420 个整点横坐标 0 到 19纵坐标 0 到 20任意两点确定一条直线这些点一共能确定多少条不同的直线。答案是 40257。看似简单实则是个大坑。绝大多数人第一反应是枚举所有点对算出斜率和截距然后扔进一个Set去重。问题就出在这里——斜率和截距是浮点数两个本该相同的直线因为浮点计算误差可能被判成不同答案就会偏大。正确的做法是用直线的一般式来表示A·x B·y C 0其中 A、B、C 都是整数。给定两点(x1,y1)和(x2,y2)我们令A y2 - y1B x1 - x2C x2·y1 - x1·y2这样得到的(A, B, C)是整数。但同一个直线的(A, B, C)可以整体乘一个非零常数所以要去重之前必须先归一化把 A、B、C 同时除以它们的最大公约数并且统一符号比如规定 A 恒为正A 为 0 时 B 恒为正。import java.util.*; public class Main { static int gcd(int a, int b) { return b 0 ? Math.abs(a) : gcd(b, a % b); } public static void main(String[] args) { SetString set new HashSet(); int X 20, Y 21; Listint[] pts new ArrayList(); for (int x 0; x X; x) for (int y 0; y Y; y) pts.add(new int[]{x, y}); for (int i 0; i pts.size(); i) { for (int j i 1; j pts.size(); j) { int[] p pts.get(i), q pts.get(j); int A q[1] - p[1]; int B p[0] - q[0]; int C q[0] * p[1] - p[0] * q[1]; int g gcd(gcd(A, B), C); if (g ! 0) { A / g; B / g; C / g; } // 统一符号 if (A 0 || (A 0 B 0)) { A -A; B -B; C -C; } set.add(A , B , C); } } System.out.println(set.size()); } }跑出来是 40257。提示用字符串拼接A , B , C当Set的 key比自定义对象更省事也更不容易出错。归一化的两个动作——约分和定符号——缺一不可少任何一个都会导致重复计数。我在第一次做这道题时图省事用了 double结果算出来四万多条比正确答案多了一千多条排查了半天才发现是浮点误差。从那以后凡是涉及直线、圆、相似三角形去重这类几何计数题我一律改成分数或整数表示坚决不用浮点。2.4 试题 D货物摆放——约数枚举里的溢出陷阱题目给了一个很大的数 n 2021041820210418问有多少个有序三元组 (L, W, H) 满足 L × W × H n。答案 2430。这道题的关键是不要去枚举三个变量而是先找出 n 的所有约数再在约数集合里两两组合。因为 n 的约数个数是有限的大约一百多个枚举量就变得可控了。import java.util.*; public class Main { public static void main(String[] args) { long n 2021041820210418L; ListLong divs new 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 count 0; for (long a : divs) { for (long b : divs) { // 判断 a * b 是否能整除 n注意避免溢出 if (n % a 0 (n / a) % b 0) { count; } } } System.out.println(count); } }这段代码跑出来是 2430。这题最大的坑就是长整型的溢出。如果你写成判断n % (a * b) 0那么当 a 和 b 都很大时a * b会溢出得到错误结果。我一开始就踩了这个坑调试了很久才发现问题出在乘法溢出上。注意Java 里long是 64 位有符号整数最大值约 9.2e18。而这道题的 n 本身就是 2e15 级别两个约数相乘很容易超过 long 的范围。所以判断整除时永远要先算n / a再对 b 取模而不是先算a * b。另外i * i n这个循环也用到了乘法当 i 接近 45 万时i * i还在 long 范围内问题不大。但如果你写for (long i 1; i n / i; i)会更安全一些。这类细节平时写代码时养成习惯考试时就不会慌。2.5 试题 E路径——为什么只需要连 21 个点这道题描述的是有 2021 个节点编号 1 到 2021节点 i 和 j 之间有一条边边权是 i 和 j 的最小公倍数 lcm(i, j)。求从节点 1 到节点 2021 的最短路径长度。答案是 10266837。稍微想一下就知道如果两两连边那就有 2021 × 2020 / 2 约两百万条边再加上 Dijkstra时间上虽然勉强能过但更聪明的做法是发现一个规律任意两点如果编号差超过 21那么它们之间一定存在一条由若干小差值的边组成的更短路径。这是因为 i 和 j 的最小公倍数至少是 max(i, j)而如果 j - i 很大走中间点反而更省。经验规则是只保留差值不超过 21 的边为什么是 21 而不是更小是因为 1 到 21 的最小公倍数已经很大了超过后走多步更划算。import java.util.*; 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]; Arrays.fill(dist, Long.MAX_VALUE); dist[1] 0; for (int iter 0; iter N; iter) { int u -1; for (int j 1; j N; j) { if (!vis[j] (u -1 || dist[j] dist[u])) u j; } if (u -1 || dist[u] Long.MAX_VALUE) break; vis[u] true; for (int v Math.max(1, u - 21); v Math.min(N, u 21); v) { if (!vis[v]) { long w lcm(u, v); if (dist[u] w dist[v]) dist[v] dist[u] w; } } } System.out.println(dist[N]); } }这段代码输出 10266837和标准答案一致。提示只连差值 21 以内的点是这道题的核心剪枝它的依据是跳一步的代价大于分多步走的代价。严格证明需要用最小公倍数的性质但做题时记住这个经验范围就够了。如果你不确定可以把 21 调到 30 或 50答案不会变只是会慢一点。我特别想强调这道题的一个易错点dist[u] w这一步如果 dist[u] 是Long.MAX_VALUE加 w 会溢出成负数导致错误地更新。所以我在代码里加了dist[u] Long.MAX_VALUE的跳过判断。这种防御性编程在做最短路题时一定要有。3. 五道编程题的实现要点3.1 试题 F时间显示——取模顺序别搞反时间显示这道题很直白给你一个毫秒数让你把它转换成时:分:秒的格式输出不显示毫秒也不考虑日期也就是说小时按 24 取模即可。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long ms sc.nextLong(); long totalSec ms / 1000; long hour totalSec / 3600 % 24; long min totalSec / 60 % 60; long sec totalSec % 60; System.out.printf(%02d:%02d:%02d%n, hour, min, sec); } }看起来简单但有几个细节必须注意。第一%02d里的0不能丢否则 3 秒会输出成 3 而不是 03格式就不对了。第二小时要% 24因为题目假设时间是循环的不显示天数。第三计算小时的时候应该先算总秒数再除以 3600 取模 24而不是先把毫秒转成小时。顺序搞错就会出现小时数字错误的情况。注意输入的毫秒数可能很大务必用long而不是int。另外用Scanner读一个数在数据量大时偏慢如果这题输入有多组数据建议换成BufferedReader。单组输入的话Scanner完全够用。这道题属于送分编程题考的是基本的取模和格式化。但正因为简单很多人不检查就提交结果栽在格式上。我建议养成习惯写完简单的格式化题自己在脑子里或用纸笔把样例算一遍确认输出格式和题目要求一字不差。3.2 试题 G最少砝码——天平和三进制的关系这道题问的是要用天平称出 1 到 N 之间所有整数克的重量最少需要几个砝码。砝码可以放在天平的两边也就是物品同侧或对侧都可以。这题的灵魂在于理解一个事实如果砝码可以放两边那么每个砝码的系数可以是 -1、0 或 1 三种状态这正好对应三进制。用 1 个砝码1 克能称出 1 克用 1、3 两个砝码能称出 1 到 4 克用 1、3、9 三个砝码能称出 1 到 13 克。规律就是k 个砝码最多能称到(3^k - 1) / 2克。所以问题变成了给定 N找到最小的 k使得(3^k - 1) / 2 N。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long N sc.nextLong(); long sum 1; // 当前能称到的最大重量 long w 1; // 当前最大砝码重量 int count 1; // 砝码个数 while (sum N) { w * 3; sum w; count; } System.out.println(count); } }这里的sum就是 1 3 9 … 的累加也就是(3^k - 1) / 2。循环直到 sum 大于等于 N。提示为什么砝码选 1、3、9、27 而不是 1、2、4、8因为二进制方案里砝码只能放一边而天平两边都能放就多出了抵消的能力进制从 2 变成了 3。这是这类题的通用结论遇到天平砝码问题先想三进制八九不离十。我见过有同学用二分或者直接推公式来做其实都可以但循环累乘是最不容易出错的写法。因为 N 最大也就到 1e9 左右循环次数不超过 20 次性能完全没问题。3.3 试题 H杨辉三角形——N 第一次出现在哪这道题给一个整数 N让你求它在杨辉三角形里第一次出现的位置。位置的定义是从第一行第一个数开始按从上到下、从左到右的顺序数第一个数是第 1 个位置。题目的样例很有意思输入 6输出 13。因为杨辉三角前几行是第1行: 1 第2行: 1 1 第3行: 1 2 1 第4行: 1 3 3 1 第5行: 1 4 6 4 1数字 6 出现在第 5 行第 3 个。前面 4 行共有 1234 10 个数所以 6 的位置是 10 3 13。突破口在于杨辉三角里第 i 行第 j 个数等于组合数C(i-1, j-1)。我们要找的是所有满足C(a, b) N的 (a, b) 中使得位置a·(a1)/2 (b1)最小的那个。由于位置主要由行号 a 决定行号小则位置小我们可以枚举列号 b然后二分查找对应的行号 a。import java.util.*; public class Main { static long C(long n, long k) { if (k n) return 0; long res 1; for (long i 1; i k; i) { res res * (n - k i) / i; if (res 2_000_000_000L) return res; // 防止溢出提前返回 } return res; } public static void main(String[] args) { Scanner sc new Scanner(System.in); long N sc.nextLong(); long best Long.MAX_VALUE; for (long b 1; b 30; b) { long lo 2 * b, hi Math.max(2 * b, N); while (lo hi) { long mid (lo hi) 1; long val C(mid, b); if (val N) { long pos mid * (mid 1) / 2 (b 1); best Math.min(best, pos); break; } else if (val N) { lo mid 1; } else { hi mid - 1; } } } System.out.println(best); } }注意组合数的计算必须小心溢出。当 C(n, k) 超过 N 的上限约 1e9以后就没必要继续精确计算了直接返回一个大值即可因为后面二分只会往小走。另外b的上限取 30 是因为 C(60, 30) 已经远超 1e9再大的 b 不可能产生有效的列。这道题最容易错的地方是位置的计算公式和列号从 1 开始这个约定。杨辉三角的第 i 行有 i 个数前 i-1 行共有i·(i-1)/2个数所以第 i 行第 j 个数的全局位置是i·(i-1)/2 j。用组合数的下标表示就是(a1)·a/2 (b1)。我第一次写的时候忘了列号要加 1答案就差了 1。3.4 试题 I双向排序——暴力打底栈优化冲满分这道题是这样的初始有一个 1 到 n 的升序序列然后进行 m 次操作。每次操作要么是把前 p 个数降序排列操作类型 0要么是把后 n-p1 个数升序排列操作类型 1。问最后序列长什么样。直接的暴力做法很简单每次操作老老实实排序。用 Java 的Arrays.sort配合区间处理时间复杂度是 O(m·n·log n)。对于大数据会超时但能拿到一部分测试点的分数。import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new java.io.InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); Integer[] a new Integer[n]; for (int i 0; i n; i) a[i] i 1; for (int i 0; i m; i) { st new StringTokenizer(br.readLine()); int t Integer.parseInt(st.nextToken()); int p Integer.parseInt(st.nextToken()); if (t 0) { // 前 p 个降序 Arrays.sort(a, 0, p, Collections.reverseOrder()); } else { // 从第 p 个到末尾升序 Arrays.sort(a, p - 1, n); } } StringBuilder sb new StringBuilder(); for (int x : a) sb.append(x).append( ); System.out.println(sb.toString().trim()); } }这段代码能过小数据但大数据一定超时。想拿满分就必须用栈来合并无效操作。核心思路是连续的同类型操作可以合并不同类型的操作之间也可能互相覆盖。比如连续两次前 p 个降序只有 p 更大的那次有意义因为前 p 个已经降序后前 p 个p p自然也是降序的。类似地最后有效的操作序列会呈现出一个锯齿状结构用栈维护这个结构就能把无关操作全部丢掉。合并规则大致是这样的栈里存放的是一系列类型交替的操作对于 0 操作前缀降序从栈底到栈顶 p 递增对于 1 操作后缀升序从栈底到栈顶 p 递减。每来一个新操作先看能不能和栈顶同类合并如果不能就检查它是否覆盖了栈顶覆盖了就弹栈直到找到一个合适的插入位置。提示双向排序的栈优化属于想明白了代码就短想不明白就一团乱的典型。做这道题的时候我建议先在纸上画几个操作手动模拟栈的变化过程确认规则正确后再写代码。直接上手敲很容易在弹栈条件上出错。处理完所有操作后模拟就变得简单了因为有效操作数量已经很少最多不超过 n 次实际远小于 m我们可以用双指针从两端往中间填数字。这一点是这道题从能过部分分到能过满分的关键。3.5 试题 J括号序列——两个方向的动态规划最后这道题给一个只包含 ( 和 ) 的字符串允许你通过添加最少的括号使它变成一个合法的括号序列每个 ( 都能找到对应的 )且配对合法。求有多少种添加方案结果对 1e97 取模。这道题的经典思路是把它拆成两个独立的问题然后相乘。第一个问题只在字符串左侧或中间添加左括号 (使得所有前缀满足左括号数量不小于右括号数量。用 DP 求这种情况下最少添加几个左括号、有几种方案。第二个问题把字符串反转并对括号取反再重复第一个问题的过程得到右侧添加右括号的方案数。最终答案就是两个方案数的乘积取模。DP 的状态定义是dp[j]表示当前处理到的位置累积的未匹配左括号数为 j 时的方案数。转移时遇到 ( 就把 j 加一遇到 ) 就把 j 减一如果 j 为 0就必须添加一个左括号方案数保留。import java.util.*; public class Main { static final int MOD 1_000_000_007; static long solve(char[] s) { int n s.length; long[] dp new long[n 2]; dp[0] 1; // 初始差值为 0 long[] ndp new long[n 2]; for (int i 0; i n; i) { Arrays.fill(ndp, 0); if (s[i] () { for (int j 1; j n; j) ndp[j] dp[j - 1]; } else { // s[i] ) // 情况1和已有的左括号匹配差值从 j1 降到 j for (int j 0; j n; j) ndp[j] dp[j 1]; // 情况2在这个右括号前插入一个左括号差值不变 for (int j 0; j n; j) ndp[j] (ndp[j] dp[j]) % MOD; } System.arraycopy(ndp, 0, dp, 0, n 2); } return dp[0]; // 差值回到 0 才算匹配完 } public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); long left solve(s.toCharArray()); // 反转并翻转括号 char[] r new StringBuilder(s).reverse().toString().toCharArray(); for (int i 0; i r.length; i) r[i] (r[i] () ? ) : (; long right solve(r); System.out.println(left * right % MOD); } }注意这道题最容易出问题的是第一次 DP 应该只处理加左括号第二次 DP 处理加右括号。很多人试图在一次 DP 里同时处理两侧的添加结果状态定义混乱怎么调都不对。拆成两个方向各自独立是这道题的核心技巧。另外DP 的空间可以用滚动数组优化把二维压成一维上面的代码就是这么做的。这样空间复杂度从 O(n²) 降到 O(n)对这道题的数据规模字符串长度可能达到 5000非常关键。4. 这些坑我替你踩过了4.1 填空题的高频失误清单填空题只有对和错没有部分分所以每道题都必须反复验证。我把做这套卷子时遇到和听说的坑整理成了一张表你可以对照着检查自己的思路。题目常见错误正确做法B 卡片判断条件写成卡片为负才停拼之前就检查卡片是否为 0C 直线用 double 表示斜率和截距用整数三元组 (A,B,C) 并归一化D 货物摆放判断 a*b 是否整除时发生溢出改成 n/a % b 0E 路径给所有点对连边导致超时或错解只连差值 21 以内的边E 路径dist 为无穷大时相加溢出更新前判断 dist[u] 是否为最大H 杨辉三角位置公式漏了列号加 1位置 a(a1)/2 b 1这些错误有个共同点都不是算法不会而是细节没抠。填空题的残酷就在于此一个边界没考虑到整道题的分数就没了。我个人的验证习惯是算出一个答案后换一种方法再算一遍。比如 C 题我一开始用斜率截距算得到错的答案后来改用整数三元组得到 40257。两个结果不一致时就要停下来想清楚哪个是对的而不是心存侥幸地提交第一个。4.2 编程题的时间与内存取舍编程题是按测试点给分的所以能过多少算多少是现实的策略。这套卷子里F、G、H 属于代码短、思路清晰的题应该确保拿满I、J 属于压轴能用暴力拿部分分就先拿部分分再考虑优化。关于 Java 的时间优化有几个实用技巧值得记住。第一大量输入输出用BufferedReaderStringTokenizer不要用Scanner尤其是有几十万行输入的时候。第二字符串拼接用StringBuilder不要在循环里用。第三排序时尽量避免自动装箱int[]的排序比Integer[]快很多。// 推荐的快速输入模板 BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); // 推荐的快速输出 StringBuilder sb new StringBuilder(); // ... 循环 append System.out.print(sb);提示Java 在蓝桥杯的评测环境里时间和内存通常比 C 宽松一些但也不能掉以轻心。养成能用数组就不用集合能用基本类型就不用包装类型的习惯能帮你省下不少时间。还有一个容易被忽视的点是内存。这套卷子里像 E 题路径、H 题杨辉三角如果用二维数组或大矩阵存中间结果很容易超出内存限制。能用一维滚动数组的就一定用一维。4.3 关于 I 题和 J 题的心态最后两道 25 分的题往往是拉开差距的关键。但我观察下来很多人在考场上因为前面耗了太多时间到这两题时已经慌了要么随便写个暴力交上去要么干脆放弃。我的建议是先把暴力解法写完整、跑对确保能过小数据拿到基础分。然后再评估剩余时间决定要不要冲击满分。以 I 题双向排序为例暴力解的代码二十行以内就能写出来先拿到手心里就有底了。至于优化如果时间允许可以慢慢推栈的规则如果时间不够暴力的分也不亏。J 题括号序列的 DP 是个典型的拆成两个方向的套路只要想到了代码其实不长。但如果你在考场上第一次见这种题想破头也可能想不到。所以平时刷题时这类左右独立处理的计数题值得单独整理成一个模板记下来。5. 做完这套题我的一些真实体会这套 2021 年的第一场我前后做了两遍第一遍是在完全没有参考答案的情况下自己硬啃花了将近五个小时最后只对了一半多第二遍是复盘把每道题的坑都记下来用了两个半小时正确率接近满分。两次之间的差距不在算法水平而在审题和验证的耐心上。第一个体会是填空题一定要用多种方法交叉验证。C 题直线我用 double 算错了如果当时多一点怀疑精神用整数重算一遍就不会在错的路上走那么远。第二个体会是编程题先保证正确再追求效率。很多人一上来就想写最优解结果连暴力都写不完整最后两头空。第三个体会是把每一道错题都当成一个模板来整理。比如线段的整数表示、天平砝码的三进制、括号序列的双向 DP这些套路在后续的国赛甚至其他比赛里还会反复出现。最后分享一个我一直在用的练习方法每做完一套真题不急着看答案而是先把每道题为什么这么解写成一句话再对照标准答案检查自己的理解。如果那句话说不清楚就说明这道题我还没真正搞懂。这个方法看着笨但坚持几套题下来你会发现自己的题感提升得很明显很多坑在写代码之前就能预感到。这套卷子里我个人最喜欢的是 G 题最少砝码和 J 题括号序列前者把一个物理问题巧妙地转化成了进制问题后者用两个方向的 DP 解决了一个看似复杂的计数问题。如果你也刚好卡在这两道题上不妨多花点时间把它们吃透这两道题背后蕴含的换个角度看问题的思路比题本身更有价值。