第13届蓝桥杯省赛Java B 组的题很多备赛群里的同学都有同一个感受前面的A~D属于“抢分题”最后两题属于“听天由命题”真正决定省一还是省二的分水岭恰恰就是中间的Q5~Q7。我当时在考场上把这三题做完出来一核对Q5的二分边界踩了个小坑Q7的取模差点写漏Q6还算顺利。这篇文章就把这三道题的拆解思路、Java实现和考场上的避坑点完整写一遍给后面备赛的同学做个参考。1. 从Q5到Q7的难度梯度决定了考场上这30分钟的做题顺序先说明一下题号对应关系。第13届蓝桥杯省赛Java B 组一共10道题试卷里用“试题A~试题J”编号习惯上大家也把第5题到第7题记作Q5~Q7分别对应试题E、试题F、试题G。当年这三道题分别是求阶乘、最大子段和、数组切分。从题型分布上看Q5和Q7偏算法思维Q6偏基础代码功恰好覆盖了省赛中段最常出现的两类考查方向。很多同学拿到卷子后喜欢从第一题往后按顺序做我的建议是先花30秒把所有题扫一遍然后从自己最有把握的开始。Q6最大子段和属于线性DP状态转移就一行代码量极小确认数据范围后可以在5分钟内拿下Q5求阶乘需要先做数学推导再套二分思路清晰但边界容易踩建议放在第二顺位Q7数组切分是区间DP递推公式和区间判断都需要多验证几组数据放在最后攻坚比较合理。同样都用20分钟先做熟题能保证分数落袋不会因为时间焦虑导致手抖。三道题的知识点、分值和建议用时我用一张表列出来题号题目名称核心考点建议用时参考分值Q5 / 试题E求阶乘数学推导、二分答案、long溢出处理10~15分钟15分Q6 / 试题F最大子段和线性DP、负数边界5~8分钟15分Q7 / 试题G数组切分区间DP、区间连续性判断、取模15~20分钟20分这三道题的分值加在一起有50分对最终省奖等级的影响非常直接。后面两道压轴题很多人只能拿部分分甚至交空白卷所以Q5~Q7的50分几乎是“必须吃下”的分数。越是这样越不能只背模板得把每道题的推导逻辑彻底搞清楚考场上一旦数据范围或输入格式有变化也能随机应变。2. Q5 求阶乘真正考的不是算阶乘而是尾随零计数和二分边界原题的大致意思是输入一个整数K求最小的正整数N使得N!的末尾恰好有K个0。如果不存在这样的N输出-1。很多人第一眼看到“阶乘”条件反射就想用BigInteger把N!算出来再数末尾有几个0。这个思路在小数据下没错但一旦K给到10^18量级N会大到你根本没法算阶乘连BigInteger都会直接被内存和时间卡死。所以第一步必须做数学转换。一个数末尾有多少个0取决于它包含多少个因子10。10 2 × 5而在阶乘的连乘过程中因子2的出现次数远多于因子5比如2、4、6、8里都含2但含5的数间隔更远。所以N!末尾0的个数直接等于N!里因子5的个数。这个结论是整道题的核心f(N) N/5 N/25 N/125 ...为什么要连除25、125因为25本身包含两个因子5125包含三个因子5。比如N 25时N/5 5N/25 1加在一起就是6个因子5所以25!末尾有6个0。这个公式可以写成一个循环函数static long countTailZeros(long n) { long res 0; long d 5; while (d n) { res n / d; if (d Long.MAX_VALUE / 5) { break; } d * 5; } return res; }这里有个很容易忽视的坑d每次乘5当n很大时d可能溢出long变成负数导致循环条件出错。所以我在乘5之前先判断了一下d Long.MAX_VALUE / 5等于给d设了一个安全阀。实际竞赛里K的取值范围一般不会让d真的乘到溢出但养成这个习惯能省去很多麻烦。有了countTailZeros函数问题就变成了找一个最小的N使得f(N) ≥ K并且f(N)恰好等于K。为什么是“≥”而不是“”因为f(N)是单调不减的但f(N)的取值会“跳变”。比如24!末尾有4个025!末尾有6个0中间没有任何N能凑出5个0。如果直接一个数一个数去试N的范围可能到10^18绝对超时用二分查找就能把复杂度压到O(logN)。二分查找有一个特别容易踩的坑右边界不能太随意。有人说那我把右边界设成Long.MAX_VALUE不就行了但如果K特别大(l r) / 2这一步里l r会溢出long变成负数二分直接死循环。稳妥的做法是右边界用一个“足够大但不会溢出”的值。根据前面的公式f(N)的增长大概在N/4附近所以右边界取K * 5 10通常就够用了。如果对K的范围不够确定更保险的写法是从小到大倍增r直到countTailZeros(r)≥Klong l 1; long r 1; while (countTailZeros(r) k) { r * 2; }倍增法虽然多算几次countTailZeros但边界安全不用猜上限。完整的二分代码import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long k sc.nextLong(); long l 1; long r k * 5 10; long ans -1; while (l r) { long mid l (r - l) / 2; long cnt countTailZeros(mid); if (cnt k) { ans mid; r mid - 1; } else { l mid 1; } } if (ans ! -1 countTailZeros(ans) ! k) { ans -1; } System.out.println(ans); } static long countTailZeros(long n) { long res 0; long d 5; while (d n) { res n / d; if (d Long.MAX_VALUE / 5) { break; } d * 5; } return res; } }注意最后一步二分找到的是“第一个f(N)≥K的位置”它不一定是“恰好等于K”。比如K5时二分找到的是N25但f(25)6不等于5所以输出-1。这说明题目里那个“不存在”的情况不是随便糊弄人的而是f(N)的值域天然就有空隙。你可以自己验证几个小数据K1时输出5K2时输出10K3输出15K4输出20K5输出-1K6输出25。这种跳跃是因为25、125这些数一次性引入了多个因子5。我们进一步算一下复杂度countTailZeros内部循环次数是log_5(N)二分复杂度是log(上限)整体非常快即使K取到10^18也完全无压力。这也是二分题的标准套路先写一个单调的判断函数再写二分框架最后单独验证答案是否精确。三步缺一不可。3. Q6 最大子段和状态转移虽短负数边界不能忽略Q6的题目描述很直接给一个长度为N的整数数组要求找出非空连续子数组的元素和的最大值。这就是经典的“最大子段和”问题说它是线性DP的入门题一点也不夸张。但正因为经典考场翻车的人反而多。最常见的错误有两个。第一把“非空子段”忘掉所有数都是负数时错误地输出0第二看到求和就用int没考虑数组里可能出现10^9级别的大数加几次就溢出了。这两个坑在蓝桥杯的数据范围下都会实实在在地触发。正确的DP思路是这样设dp[i]表示“以第i个元素结尾的最大子段和”。那dp[i]只有两种来源要么单独从a[i]开始一段也就是a[i]要么把a[i]接到前面的子段后面也就是dp[i-1] a[i]。所以状态转移方程就是dp[i] max(a[i], dp[i-1] a[i])最终答案是所有dp[i]里的最大值。由于dp[i]只依赖dp[i-1]根本不需要开数组用一个变量cur滚动更新就可以。这个压缩版本很多教材里也叫Kadane算法核心就是“如果前面的累加和是负数那还不如从当前元素重新开始”。用代码写出来非常短import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long cur 0; long ans Long.MIN_VALUE / 2; for (int i 0; i n; i) { long x sc.nextLong(); cur Math.max(x, cur x); ans Math.max(ans, cur); } System.out.println(ans); } }为什么ans的初始值不用0因为如果数组全是负数正确答案是最大的那个负数比如-1、-2、-3里的答案是-1。如果ans初始化为0max(0, cur)会把所有负数都过滤掉最后输出0那就全错了。我习惯把ans初始化为很小的long值比如Long.MIN_VALUE / 2这样不管数组里是什么第一轮都会正确把cur写进ans。除以2是为了防止某些场景下做减法时溢出到正数其实初始化为Long.MIN_VALUE也多半不会出事但写Long.MIN_VALUE / 2更稳。这段代码循环里用的是cur Math.max(x, cur x)而不是网上常见的cur Math.max(cur, 0); cur x;。两种写法本质等价但前者对初值要求更宽松就算cur最初是0也不会出现负数边界问题。我个人推荐背前者因为少一次判断逻辑也更直观。顺手给几个自测样例提交前在本地跑一下基本能确认代码没问题输入 5 -1 -2 -3 -4 -5 输出 -1输入 3 1 -2 3 输出 3输入 5 -10 20 -30 40 -50 输出 40第二个样例里的最大子段是最后的[3]第三个是中间的[40]。第一个样例则是专门用来测evaluate负数边界的。如果这些样例都过了说明核心逻辑没问题。关于输入效率多说一句。N比较小的时候Scanner随便用但蓝桥杯有些测试点数据量能到10^6Scanner的nextLong会按字符流逐个解析速度偏慢有概率拖慢整体运行时间。虽然不是每次都会超时但万一时间卡得紧换BufferedReader会更安心。下面这个封装可以直接套用import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); long cur 0; long ans Long.MIN_VALUE / 2; for (int i 0; i n; i) { if (!st.hasMoreTokens()) { st new StringTokenizer(br.readLine()); } long x Long.parseLong(st.nextToken()); cur Math.max(x, cur x); ans Math.max(ans, cur); } System.out.println(ans); } }有同学问能不能用前缀和加前缀最小值来解当然可以。前缀和数组pre[i]表示前i个元素之和然后对每个位置j用pre[j]减去前面最小的pre[i]就能得到以j结尾的最大子段和。这个做法的时空复杂度都是O(n)遇到一些变形题时会更好用但就这道题本身来说滚动变量的Kadane已经是天花板了不需要额外开数组。4. Q7 数组切分用O(n^2)的区间DP就能稳拿关键在于区间判断条件Q7数组切分是这三道题里最需要动脑的一道。题目的意思大致是给定一个长度为N的数组要求把它切分成若干个连续子段使每一段内部重新排序后都能形成一个连续的自然数区间问一共有多少种切分方案答案对1e97取模。第一次见这道题很多人会想到暴力枚举所有切分组合复杂度直接爆炸。正确姿势是区间DP。但DP前先要解决一个关键问题怎么判断一个子段“内部排序后是连续自然数”这里有一个非常经典的数学判断在一个不包含重复元素的区间里如果最大值减去最小值等于区间长度减1那么这个区间内一定包含从最小值到最大值的所有整数。比如[3,1,2]max3min1len33-12len-1所以它排序后是[1,2,3]连续。再看[2,4]max4min2len24-22≠1所以不连续。这个判断条件时间复杂度O(1)比把每个区间拿出来排序再验证要高效得多。当然它成立的前提是区间内没有重复元素一般来说这种题给的数组都是1到N的排列每个数只出现一次可以直接用。如果题目换成了可能重复的数组就得补用哈希表或布尔数组判断重复了。接下来设计DP。设dp[i]表示“前i个元素的合法切分方案数”dp[0]设为1表示空前缀有一种“什么都不切”的方案。然后枚举每个起点i再向右扩展终点j维护从i到j这段范围内的最小值和最大值。如果区间[i, j]满足连续条件那么它就可以作为一段独立切分和前面i个元素的任意一种合法切法组合。也就是说需要把dp[i]累加到dp[j1]上dp[j1] dp[i]这里有很多人转不过弯为什么是把dp[i]加到dp[j1]而不是加到别的下标因为dp数组的下标表示“已经处理完的元素数量”。前i个元素已经处理完下一段从第i1个元素开始到第j1个元素结束也就是下标从i到j这段。这段作为新的一段切分后前j1个元素就全部处理完了所以累加到dp[j1]。写代码时要注意循环顺序外层i从小到大保证dp[i]在计算前已经被累加过。内层j从i开始向右扫一边扫一边更新min和max。完整实现import java.util.Scanner; public class Main { static final int MOD 1_000_000_007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } long[] dp new long[n 1]; dp[0] 1; for (int i 0; i n; i) { int min a[i]; int max a[i]; for (int j i; j n; j) { min Math.min(min, a[j]); max Math.max(max, a[j]); if (max - min j - i) { dp[j 1] (dp[j 1] dp[i]) % MOD; } } } System.out.println(dp[n]); } }用一个简单例子跑一遍数组[1,2,3]正确答案是4。手动推一下dp[0]1i0时区间[0,0]连续dp[1]1区间[0,1]连续dp[2]1区间[0,2]连续dp[3]1。i1时dp[1]1区间[1,1]连续dp[2]1此时dp[2]2区间[1,2]连续dp[3]1此时dp[3]2。i2时dp[2]2区间[2,2]连续dp[3]2最终dp[3]4。四种切分方式分别是[1,2,3]、[1,2]|[3]、[1]|[2,3]、[1]|[2]|[3]。和预期一致。时间复杂度是O(n^2)空间复杂度O(n)。当年这道题一堆题解都是O(n^2)的dp说明官方数据范围本来就允许这种复杂度。有些同学一看O(n^2)就心虚总想用线段树或单调栈把它优化成O(n log n)但在正式比赛中把简单可靠的解法先写对、拿满分的收益远大于花半个多小时去推一个高级优化。这个取舍本身就是竞赛能力的一部分。还有一点是关于取模的。题目要求答案对1e97取模所以每次dp[j1]增加时我都在赋值语句里顺手取了模。dp[i]和dp[j1]都是小于MOD的数加在一起最多是2×MOD及时取模后就不会溢出long。如果等到最后一次性对结果取模中间数值早就膨胀到天文数字了。5. 实测这三题时Java提交最容易翻车的几个细节把三道题的思路讲完之后再补充一点实战层面的细节。这些细节不是算法层面的但一到OJ提交就会变成真正影响分数的坑。第一类名必须是Main不能带package语句。蓝桥杯Java组的判题环境会直接找Main类里的main方法入口很多同学本地Eclipse里建了个带包名的类复制过去忘了改直接编译错误。这个问题每年都有不少人踩一定提前在模板里写好完整结构。第二IO选型要和数据规模匹配。Scanner的好处是写起来省事但在数据量达到10^6级别的场景下会明显变慢。Q6和Q7虽然N不一定特别夸张但养成用BufferedReader StringTokenizer的习惯没有任何坏处。我在上面已经给出过一段封装实际写代码时可以把输入读取固化成一个nextInt或nextLong方法这样主逻辑里看起来更清爽。第三long溢出问题。Q5里二分右边界如果直接设Long.MAX_VALUE很危险Q6里如果不小心把中间和定义为int结果会错得莫名其妙Q7里每次都取模就是防long溢出。Java的long虽然比C的long long好用但它不是无限大的做题时对每一个涉及乘法的地方都多看一眼。第四二分查找中的死循环。写while (l r)时mid l (r - l) / 2要用这个写法不要用(l r) / 2。左侧额l、r都是long时lr溢出会变成负数mid计算出来也是负数整个二分就会在错误区间里打转。这是我亲眼见过很多选手踩的坑包括我自己也翻过一次车。第五测试时一定要包含边界数据。Q5可以测K1、K5、K6Q6一定要测全负数数组Q7可以测n1、n2、以及[2,1,3]这种打乱顺序的数组。边界样例过了提交的时候心里才有底。6. 复盘后的训练建议同样的算法题怎么从“会做”变成“稳拿分”最后聊聊这三道题对后续备赛的启示。很多人刷蓝桥杯真题只追求“在IDE里跑出正确答案”然后就去刷下一道题。这个习惯在你还是新手时没问题但到了省赛冲刺阶段效率会很低。因为考场上真正难的不是“想不出解法”而是“在有限时间内写出一份没有低级错误的代码”。我的做法是每做完一道题强制自己完成三件事。第一复述一遍完整思路从读题到算法选择到边界处理用两分钟口头说清楚第二把代码里的关键边界条件用注释标出来比如Q5里的验证ans、Q6里的负数初始值、Q7里的取模时机这些就是考场上最容易掉的分数第三故意改乱一个参数看看程序会不会错比如把Q5的右边界改大或者把Q7的mod去掉感受一下错误的症状这样以后遇到类似迹象能快速定位。这三道题放在一起复盘你会发现一个共性它们都不需要太高深的算法理论Q5是二分数学Q6是线性DPQ7是区间DP但每一道都暗藏一两个“细节陷阱”。蓝桥杯的省赛难度本质上比的是谁更稳而不是谁更炫。你可以不会平衡树可以不熟悉最大流但基础的二分查找、DP、前缀和、排序这些“吃饭手艺”必须练到闭着眼睛都能写对。我自己备赛第13届的时候Q5那个无解判断一开始就漏了本地跑K5直接输出25还觉得很合理。直到对照题解才发现f(N)会在5的幂次位置发生跳变中间那些K永远没有对应答案。后来我专门把“凑尾随零”这类按数量倒推的问题整理了一个小专题从阶乘零扩展到组合数末尾零、进制转换末尾零等变形思路一下子就通了很多。竞赛题就是这样做一道题如果只停留在“AC了”这个层面收获其实很小把背后的数学结构吃透下次换一层皮你依然认识它。客观说第13届省赛Java B组的题整体不算偏Q5~Q7的难度属于中等偏基础。如果你准备下一届比赛建议先把这套题完整刷一遍尤其是这三道可以作为检验自己基础是否扎实的试金石。能不看题解写出满分答案说明省二基本稳了如果还能顺手把Q7的O(n^2) DP优化思路讲清楚那省一也在向你招手。关键不是刷了多少道题而是每一道题背后那些“为什么这样写”“这里为什么容易错”有没有真正想明白。
