校内选拔赛一结束学委群里就有人追着问“有没有题解啊”说实话我特别理解这种心情。选拔赛不是省赛题量不大但梯度拉得开考完很多人对完答案还是说不清自己挂在哪一步。这几天我把四道题重新过了一遍整理出这篇完整解析。今年的四道题分别落在前缀和、二分答案、完全背包和并查集最小生成树这几个经典考点上几乎就是蓝桥杯省赛前四题的高频考法。题目本身不难难的是你能不能稳定地把该拿的分全拿到。这篇题解不只是给答案我会把每道题的思考链、易错点和代码一起放出来方便备赛的同学对着自查。1. 赛题设置的整体逻辑与题目难度梯度1.1 为什么选这四类题参加过蓝桥杯的同学应该都有体会省赛的题目分布是有规律可循的前两三道题是“送分题”考察基本语法和简单算法中间一至两道题开始加入数据结构或经典算法模型最后一道题则往往需要组合多个知识点。这次选拔赛基本复刻了这样的结构。A题考察前缀和属于必须秒杀的签到题B题是二分答案考察“最大值最小化”这类经典问题的敏感度C题是完全背包考察动态规划的状态设计和循环优化D题是并查集加最小生成树思想属于需要一定功底的综合题。这样设计的目的很明确。选拔赛不是以“难倒人”为目标而是要在有限时间内筛出两类人一类是基础扎实、该拿的分不丢的稳型选手另一类是有算法直觉、能快速将陌生问题归约到经典模型的成长型选手。很多人在校赛阶段容易踩同一个误区——觉得题越难越能证明实力。实际上蓝桥杯的判分规则决定了一件事一道签到题的分数和一道压轴题的分数是一样的性价比却有天壤之别。赛场上最重要的能力不是“解出最难的题”而是“在最短时间内拿到最多的分”。1.2 题号、知识点与蓝桥杯考点对应关系先放一张表方便大家对号入座。题号题目考点对应蓝桥杯常见题型预期难度A前缀和、区间查询省赛B组前两题常见签到B二分答案、贪心判定省赛中间层次高频考题中等C完全背包、DP优化省赛DP类必考题型中等偏上D并查集、最小生成树省赛综合大题常客拉开差距下面按题号逐一拆解建议大家不要只盯代码重点是理解每一步推导的逻辑。因为代码是背不完的思路才是你自己的。2. A题“数列区间查询”前缀和是一道不需要思考的题2.1 题意回顾给定一个长度为n的整数数组a接下来有q次询问每次给定两个整数l和r1 ≤ l ≤ r ≤ n要求输出第l个数到第r个数的和。很多同学第一反应是这有什么难的用循环累加不就行了。但题目里有一句要紧的话——n和q的范围都在10^5级别。这意味着如果你每次询问都重新for一遍区间最坏情况下的总时间复杂度是O(nq)也就是10^10次运算放在蓝桥杯的判题环境里铁定超时。这道题想考察的东西其实就一句话你知不知道“预处理换查询时间”的思想。2.2 暴力解法的性能瓶颈在哪我们先看一下暴力代码的思路for (int i 0; i q; i) { int l sc.nextInt(); int r sc.nextInt(); long sum 0; for (int j l; j r; j) { sum a[j]; } System.out.println(sum); }这段代码的逻辑是对的但它把每一次询问都当成独立任务完全没有利用题目给出的静态数组这个特性。注意数组在输入之后就没有任何变化那么任意区间[l, r]的和其实都可以通过前后两个前缀值的差来得到。2.3 前缀和的推导过程定义前缀和数组prepre[i]表示原数组前i个元素的和。递推关系是pre[0] 0 pre[i] pre[i - 1] a[i]有了pre数组之后区间[l, r]的和就等于pre[r] - pre[l - 1]。这个式子可以这样理解前r个数的总和减去前l-1个数的总和自然就是第l到第r这一段的和。整个预处理只需要O(n)的时间之后每一次查询都是O(1)总复杂度降到O(nq)性能差距是碾压级的。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long[] a new long[n 1]; long[] pre new long[n 1]; for (int i 1; i n; i) { a[i] sc.nextLong(); pre[i] pre[i - 1] a[i]; } int q sc.nextInt(); while (q-- 0) { int l sc.nextInt(); int r sc.nextInt(); System.out.println(pre[r] - pre[l - 1]); } } }2.4 这题真正容易栽的地方别看题目简单实际阅卷时我见过不少人在这题上丢分丢的不是思路的分而是数据类型的分。题目没有保证数组元素为正元素可能是负数而且区间和完全可能超过int的表示范围。Java的int最大才21亿多一旦累加结果超过这个值就会溢出变成负数导致答案错误。这也是蓝桥杯的一个经典陷阱——所有求和类题目开long几乎是一个不需要犹豫的默认选择。再提醒一个细节数组下标问题。强烈建议用1-based索引也就是让数组下标从1开始而不是从0开始。这样pre[l - 1]在l1时正好是pre[0]边界处理非常干净。如果用0-based虽然也能调整但每次写边界都要格外小心容易在细节上出错。这道题的延展方向是二维前缀和蓝桥杯省赛偶尔会出现“求子矩阵和”的题目思路完全一样只是pre变成二维数组递推和查询用容斥原理处理。建议学有余力的同学顺手练一下。3. B题“数列分段问题”一眼识别“最大值最小化”的二分答案模型3.1 题意回顾给定一个长度为n的正整数数组要求把这个数组按原有顺序分割成m段每段至少包含一个元素问所有分段方案中每段元素之和的最大值最小可能是多少。简单举个例子数组为[1, 2, 3, 4, 5]如果分成两段方案可以是[1, 2, 3]和[4, 5]前后两段和分别为6和9最大值是9也可以是[1, 2, 3, 4]和[5]最大值是10。所以最优答案是9。3.2 为什么这题不能用贪心直接做看到“分成m段”很多人会本能地想那我从左往右加加到上限再切一刀不就行了。问题是——加到哪个上限你没有标准。贪心局部贪不出来因为你不知道每一段的“合适大小”应该控制在什么范围。这类“最大值最小化”或“最小值最大化”的题目有一个非常成熟的套路化解法就是二分答案。3.3 二分答案的核心思想我们不直接求“最大值最小是多少”而是先猜一个答案x然后验证“是否存在一种分段方案使得每一段的和都不超过x”。如果能做到说明x可行如果做不到说明x太小了。这个验证函数是有单调性的如果x可行那么任何比x大的y一定也可行如果x不可行任何比x小的y也一定不可行。整体可行域是一段连续的区间二分就是在这个区间上快速寻找临界点。3.4 check函数的实现细节验证函数怎么写是关键。遍历整个数组用一个临时变量cur记录当前段已经累加的和。如果cur加上当前元素仍然不超过x就继续累加一旦超过x说明必须在这里切一刀新开一段段数加一并把cur重置为当前元素的值。这里有一个最容易漏掉的判断如果某个单个元素本身已经大于x那么无论怎么分段这一段的和都会超过x直接返回false。完整代码如下import java.util.*; public class Main { static int n, m; static long[] a; public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); m sc.nextInt(); a new long[n]; long sum 0; for (int i 0; i n; i) { a[i] sc.nextLong(); sum a[i]; } long left 0, right sum; // 答案一定在[0, sum]之间 while (left right) { long mid (left right) 1; if (check(mid)) { right mid - 1; } else { left mid 1; } } System.out.println(left); } static boolean check(long x) { int cnt 1; long cur 0; for (long v : a) { if (v x) return false; // 单个元素超过限制直接不可行 if (cur v x) { cur v; } else { cnt; cur v; } } return cnt m; } }3.5 二分边界和初始化值的坑二分的边界通常是最容易出bug的地方。我这里用的写法是while (left right)意思是区间里还有元素要处理。退出循环时left是第一个可行的答案right是最后一个不可行的答案因此直接输出left即可。二分的初始右边界设为整个数组的和因为最极端的方案是“把所有元素分到一段”此时段和就是总和这一定是可行的初始左边界设为0因为段和不可能为负数。有些同学喜欢把左边界设为数组中最大值这样能省下一点二分次数但前提是确保这个值不会超过最优答案。对于这道题设0最简单不会出错。这类题在蓝桥杯历年题目中的出场率非常高尤其是“将n个数分成m组”“最小化最大工作量”等包装主题本质上都是二分答案。大家看到题目里有“最大值最小”“最小值最大”这类字眼时第一反应就应该是二分。4. C题“纪念品兑换”完全背包的状态设计与循环顺序4.1 题意回顾学校办活动有n种纪念品第i种单价为cost[i]吸引力指数为value[i]。每种纪念品可以无限次兑换现在给你预算M元问在不超预算的前提下最多能获得多少吸引力指数。这道题的特点是“每种物品不限数量”这和经典的0-1背包问题不一样。0-1背包每件物品最多取一次这里可以取无数次所以要用完全背包模型。4.2 DP状态的定义和转移设dp[j]表示预算为j元时能获得的最大吸引力指数。对于每一种纪念品i我们做一次决策在当前预算j下要不要兑换一个这种纪念品如果兑换状态就从dp[j - cost[i]]转移过来加上value[i]。关键区别来了。0-1背包的容量循环是倒序的从M往cost[i]方向循环目的是保证每个物品只被使用一次完全背包则是正序循环从cost[i]往M方向循环因为正序时dp[j - cost[i]]可能已经在当前物品的转移中被更新过相当于允许同一物品被重复使用多次。4.3 朴素代码与滚动数组的写法import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int M sc.nextInt(); int[] cost new int[n]; int[] value new int[n]; for (int i 0; i n; i) { cost[i] sc.nextInt(); value[i] sc.nextInt(); } long[] dp new long[M 1]; for (int i 0; i n; i) { // 正序循环允许重复选择 for (int j cost[i]; j M; j) { dp[j] Math.max(dp[j], dp[j - cost[i]] value[i]); } } System.out.println(dp[M]); } }4.4 为什么dp开long而不是int这个和A题是一样的道理。吸引力指数叠加之后可能很大如果用int在极限数据下可能溢出。Java的Math.max可以处理long类型所以dp数组类型直接设成long是稳妥的。另外初值的问题也要注意。如果纪念品的吸引力指数都是正整数dp数组初始化为0即可如果存在负值的情况需要初始化成极小值并且要把dp[0]设为0。不过蓝桥杯这类题通常默认所有数值为正可以直接初始化0。4.5 完全背包、多重背包、0-1背包的区分策略考场上有不少人死记硬背“倒序是0-1正序是完全”不知道为什么换个包装就乱了。我给大家一个更本质的理解方式倒序循环时dp[j - cost[i]]还没被当前物品更新过它代表的是“只用前i-1种物品”的最优值所以每件物品只能选一次正序循环时dp[j - cost[i]]可能已经包含当前物品所以可以重复选。从这个原理出发多重背包拆成0-1背包也就好理解了——每种物品有数量限制拆成多个单件再套0-1背包的倒序循环。理解了底层逻辑考场上才不会慌。5. D题“校园网连通计划”并查集与最小生成树思想的综合运用5.1 题意回顾校园里有n个建筑彼此之间已经规划了m条可铺设网线的线路第i条线路连接建筑u和v需要花费w元。另外其中有若干条线路已经提前铺设完成不需要再花钱。现在要让所有建筑都处于连通状态问最少还需要投入多少元。这道题比前三道多了几个弯但剥开外壳核心就是“最小生成树”这四个字。已经铺好的线路成本为0普通线路成本为w本质上就是让你找一棵连接所有点的最小生成树只是部分边权重为0。5.2 并查集基础回顾并查集是用来维护元素分组关系的数据结构支持两个操作查询某个元素所在集合的根节点以及合并两个元素所在的集合。核心优化有两个路径压缩和按秩合并。路径压缩的意思是在find查询过程中把沿途所有节点直接指向根节点这样下次查询就能一步到位摊还时间复杂度接近常数级别。按秩合并则是在合并时把深度较小的树挂到深度较大的树上避免树退化成链。5.3 克鲁斯卡尔算法的思路最小生成树的经典算法之一是克鲁斯卡尔算法思想特别简单把所有边按权重从小到大排序然后依次遍历如果边的两个端点不在同一个集合里就合并它们并累加这条边的费用如果已经在同一个集合里说明加上这条边会形成环跳过。这个算法正确性的直观解释是用贪心思想权重越小的边越优先使用在不形成环的前提下尽可能多连通节点最终一定得到全局最优的最小生成树。证明方法涉及“切割定理”和“贪心选择性质”这里不展开但大家要记住这个结论考场上直接使用。回到题目已经铺好的线就当成权重为0的边照样参与排序只不过因为权重最小排序后一定会被优先选取。5.4 完整代码import java.util.*; class Edge { int u, v; long w; Edge(int u, int v, long w) { this.u u; this.v v; this.w w; } } public class Main { static int[] parent; static int[] rank; static int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } static boolean union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return false; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } return true; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); parent new int[n 1]; rank new int[n 1]; for (int i 1; i n; i) { parent[i] i; } ListEdge edges new ArrayList(); for (int i 0; i m; i) { int u sc.nextInt(); int v sc.nextInt(); long w sc.nextLong(); edges.add(new Edge(u, v, w)); } edges.sort((a, b) - Long.compare(a.w, b.w)); long ans 0; int components n; for (Edge e : edges) { if (union(e.u, e.v)) { ans e.w; components--; if (components 1) break; // 所有点已连通提前结束 } } if (components 1) { System.out.println(-1); // 图本身不连通 } else { System.out.println(ans); } } }5.5 这题最大的坑图本身不连通这道题最容易被忽略的设计是题目并没有保证给出的m条线路能让所有建筑连成一片。如果输入的图本身就是多个连通块那么无论如何铺设都没法让所有建筑互通。这时候正确答案是-1而不是某个最小生成树的值。这个坑在蓝桥杯原题中反复出现。很多同学写完克鲁斯卡尔就直接输出ans丢掉了最后这个判断导致样例全过但分数全丢。我建议把“components 1”的判断当作这类题的标配写法不管题目有没有说都先写上去顶多多费两行代码但能避免一次致命失误。5.6 关于“已铺线路”权重为0的处理有些同学在实现时喜欢先把所有已铺线路union掉再把剩余边排序这当然没问题。但更简洁的做法是直接把它们当作权重为0的边参与排序。因为克鲁斯卡尔会优先取权重最小的边权重为0的边一定排在所有正权边之前在无环的情况下必然优先连通。这样不仅代码统一也减少了写着写着把某条已铺线路漏掉的风险。6. 赛后复盘从这次选拔赛暴露出的高频问题与备赛建议6.1 从代码层面看最普遍的三个失分点第一数据类型没有随大流开long。A题、C题、D题都有求和理论上都可能溢出int。我在复查代码时发现不少同学A题用了long但C题的dp数组还是intD题的ans也是int这很不稳定。第二二分边界没有统一模板。有人while(left right)有人while(left right)还有人把mid (left right) 1和right mid这类写法混在一起导致边界条件一改就崩。第三并查集的find函数没有路径压缩或者压缩写错了。这个问题平时刷题很少暴露一旦数据量大递归深度一上来直接栈溢出崩溃。6.2 考场时间分配的策略建议蓝桥杯的时长是两个小时一共题目数量通常在十道上下省赛但校内选拔赛时间更紧张。我个人的建议是先花两到三分钟把全部题目扫一遍给每道题贴一个“会/疑似会/不会”的标签然后按标签顺序做题而不是按题号顺序做。A题这种签到题不用想五分钟内必须写完跑通样例。B题如果十分钟内没有思路先跳过做C题回头再冷静分析。D题如果写到一半发现情况比想象中复杂先保存好现有版本再决定是否继续投入时间。我们这次选拔赛有个比较可惜的情况至少三位同学在D题卡了四十分钟导致C题没时间写。其实他们C题完全有能力做出来。填一个空就能稳稳拿到C题的分比死磕D题的未知结果划算得多。6.3 下一阶段的备赛路径如果你想用这次选拔赛暴露的问题指导接下来的备赛我建议做三件事。第一把高频考点做成自己的模板库。前缀和、差分、二分答案、背包DP、并查集、最短路、最小生成树这些是蓝桥杯省赛的常客每个知识点各准备一份经过自己验证、边界处理完好的代码模板比赛时直接套而不是现场推。第二每周固定时间做模拟赛。不是刷一道题就休息而是卡时间、卡环境完整做一套卷子。模拟赛的价值不只是练知识点更在于练心态和节奏。第三养成赛后复盘的硬习惯。每场比赛结束后不管考得好不好都要把每道题重新做一遍特别是那些你“觉得会但没做出来”的题这类题的提升空间最大。6.4 一个值得长期坚持的小习惯最后说个我自己带队时反复强调的小习惯每次提交前花三秒钟问自己三个问题——下标开对了没有数组越界有没有数据类型开了long没有这三个问题的成本几乎为零但每次比赛都能帮人拦住两三处致命失误。选拔赛只是起点不是终点。这次没发挥好的人离省赛还有一段可以弯道超车的距离这次发挥正常的人也别急着松因为省赛题量和难度都会比校内赛高一个级别。希望这篇题解能帮你在下一阶段走得更稳。
