蓝桥杯国赛“123”题解：无限序列求和与二分查找优化

1. 项目概述从“123”这道题看蓝桥杯国赛的思维跃迁最近在整理历年蓝桥杯国赛的真题发现“123”这道题被讨论的频率相当高。乍一看标题你可能会觉得这题简单得离谱不就是输出个“123”吗但真正打开题目描述或者亲自在OJ上提交一次你就会发现事情远没有想象中那么简单。这道题常常作为国赛Java A组或B组的题目出现它考察的绝不仅仅是基础的语法而是对选手算法思维、数学归纳能力以及边界条件处理的一次综合检验。很多朋友在练习时要么是超时要么是答案错误卡上几个小时是常事。今天我就结合自己带学生备赛和刷题的经验把这道题的“里子”和“面子”都拆开来讲透从最朴素的暴力思路到一步步优化至ACAccepted的完整心路历程并附上可运行的Java代码和详细的注释。这道题的核心通常被描述为有一个特殊的无限序列其构造规则如下序列从1开始依次是1, 1,2, 1,2,3, 1,2,3,4, ...。即先写入数字1然后写入1,2然后写入1,2,3以此类推无限延伸。题目会给定T组查询每组查询给出两个整数l和r要求你输出这个无限序列中从第l个数字到第r个数字之间所有数字的和。l和r的范围可能非常大比如达到10^12甚至更大而T也可能不小。这就彻底堵死了暴力模拟生成序列然后累加的道路。它逼着你必须去寻找序列的数学规律设计出O(1)或O(log n)时间复杂度的查询算法。这正体现了蓝桥杯国赛的典型风格题目描述简洁数据范围巨大需要选手具备优秀的数学建模和算法优化能力。2. 核心思路拆解化无限序列为可计算模型面对这样一个无限序列求和问题直接硬算是死路一条。我们的核心思路是分层与分块将问题分解为几个可计算的子问题。2.1 序列的结构化理解首先我们需要重新理解这个序列。它不是杂乱无章的而是有清晰的层次结构第1组[1]包含1个数字。第2组[1, 2]包含2个数字。第3组[1, 2, 3]包含3个数字。...第k组[1, 2, 3, ..., k]包含k个数字。那么整个序列就是这些组的顺序拼接。第k组内部的和是容易计算的即1到k的等差数列求和sum_group(k) k * (k 1) / 2。2.2 问题转化定位与分段求和现在题目要求的是原序列中第l个到第r个元素的和。我们可以将其转化为sum(l, r) prefix_sum(r) - prefix_sum(l - 1)其中prefix_sum(x)表示序列前x个元素的和。因此问题的关键就变成了如何高效计算prefix_sum(x)即给定一个位置x快速求出前x个数的和。计算prefix_sum(x)需要两步定位找到位置x落在第几组记为group_idx以及在该组内的第几个位置记为pos_in_group。分段求和前group_idx - 1个完整组的和 第group_idx组内前pos_in_group个数的和。2.3 定位算法的设计二分查找的引入如何定位已知前m个组一共包含的数字总数是total_cnt(m) 1 2 3 ... m m * (m 1) / 2。 我们需要找到最小的group_idx使得total_cnt(group_idx) x。这显然是一个在单调递增序列上查找目标值的问题二分查找是最佳选择。假设我们通过二分找到了group_idx那么前group_idx - 1个完整组包含的数字个数为cnt_before (group_idx - 1) * group_idx / 2。因此位置x在第group_idx组内的偏移量即pos_in_group为pos_in_group x - cnt_before。2.4 求和公式的推导定位完成后求和就简单了完整组的和前group_idx - 1个完整组的总和。第i组的和是i*(i1)/2前n个完整组的总和公式需要推导一下。 前n组的总和S_total(n) Σ_{i1}^{n} [i*(i1)/2] 1/2 * Σ_{i1}^{n} (i^2 i) 1/2 * [ Σ_{i1}^{n} i^2 Σ_{i1}^{n} i ]。 利用平方和公式Σ i^2 n(n1)(2n1)/6和等差数列求和公式Σ i n(n1)/2可得S_total(n) 1/2 * [ n(n1)(2n1)/6 n(n1)/2 ] n(n1)(n2)/6。 所以前group_idx - 1个完整组的和sum_complete (group_idx - 1) * group_idx * (group_idx 1) / 6。当前组的部分和第group_idx组内前pos_in_group个数的和。这是一个从1开始的等差数列的部分和sum_partial pos_in_group * (pos_in_group 1) / 2。最终前缀和prefix_sum(x) sum_complete sum_partial。至此我们得到了计算单个prefix_sum(x)的O(log x)算法因为二分查找是O(log n)。对于每次查询(l, r)我们计算两次prefix_sum做一次减法总时间复杂度为O(log max(l, r))对于T次查询和巨大的数据范围这是完全可行的。注意在计算sum_complete公式n(n1)(n2)/6时直接计算可能会超出long的范围即使使用long类型因为n可以很大。我们必须注意计算过程中的溢出问题。一个常见的技巧是调整计算顺序或者使用BigInteger。但在蓝桥杯的评测环境下通常数据会保证在long的合理范围内如果使用long需要注意先进行除法运算来减小数值或者使用long的无溢出检查的乘法在Java中如果溢出会默默环绕导致结果错误。更稳妥的做法是在公式中因为n, n1, n2三个连续整数中一定有一个是3的倍数一个是2的倍数我们可以先进行除法来降低中间值。例如计算a n * (n1) / 2再计算a * (n2) / 3。这样能最大程度避免中间溢出。3. 代码实现与逐行解析理论清晰后我们来看Java代码如何实现。我将代码分为几个核心函数并附上详细注释。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int T sc.nextInt(); while (T-- 0) { long l sc.nextLong(); long r sc.nextLong(); // 核心区间和 前缀和(r) - 前缀和(l-1) long result prefixSum(r) - prefixSum(l - 1); System.out.println(result); } sc.close(); } /** * 计算序列前x个元素的和 * param x 位置从1开始计数 * return 前x个元素的和 */ private static long prefixSum(long x) { if (x 0) return 0; // 边界条件处理 // 1. 二分查找找到x所在的组号group long group findGroup(x); // 2. 计算前 group-1 个完整组的总和 long sumComplete sumOfCompleteGroups(group - 1); // 3. 计算x在当前组内的偏移量 long cntBefore (group - 1) * group / 2; // 前group-1组的元素总数 long posInGroup x - cntBefore; // 在当前组内的位置从1开始 // 4. 计算当前组内前posInGroup个元素的和 long sumPartial posInGroup * (posInGroup 1) / 2; // 5. 总和 return sumComplete sumPartial; } /** * 二分查找找到最小的n使得前n组元素总数 x * 即满足n*(n1)/2 x */ private static long findGroup(long x) { long left 1, right (long) Math.sqrt(2 * x) 2; // 一个宽松的上界估计 while (left right) { long mid left (right - left) / 2; if (mid * (mid 1) / 2 x) { right mid; } else { left mid 1; } } return left; } /** * 计算前n个完整组的所有元素之和 * 公式S(n) n*(n1)*(n2)/6 * 为防止溢出采用分步计算 */ private static long sumOfCompleteGroups(long n) { if (n 0) return 0; // 计算策略先算 n*(n1)/2再乘以(n2)/3注意整除关系 long a n; long b n 1; long c n 2; // 调整顺序先除后乘防止溢出 // 因为n, n1, n2中一定有一个是2的倍数一个是3的倍数 if (a % 2 0) a / 2; else if (b % 2 0) b / 2; else c / 2; // 此时c一定是偶数 if (a % 3 0) a / 3; else if (b % 3 0) b / 3; else c / 3; // 现在a, b, c都已经缩小相乘一般不会溢出 return a * b * c; } }3.1 代码关键点解析findGroup函数中的上界估计right (long) Math.sqrt(2 * x) 2。为什么 因为我们要找的n满足n*(n1)/2 x。忽略低阶项近似有n^2 / 2 x所以n sqrt(2x)。我们取sqrt(2x) 2作为一个肯定足够大的上界保证二分查找的正确性。这是一个常用技巧避免将right初始化为一个不必要的大数如x提升二分效率。sumOfCompleteGroups函数中的防溢出处理这是本解法的精髓和易错点。直接计算n*(n1)*(n2)/6当n很大时例如接近10^6n*(n1)就可能超出long的范围约9e18。我们利用连续三个整数中必有一个是2的倍数、一个是3的倍数的性质先进行除法运算将大数拆解然后再相乘。这种方法比使用BigInteger效率高得多是算法竞赛中的经典技巧。主循环的逻辑清晰明了。读取T对于每一组l, r计算prefixSum(r) - prefixSum(l-1)并输出。注意l-1可能为0所以在prefixSum函数开头做了边界判断。4. 测试与边界条件验证理论正确不代表代码正确尤其是涉及大数和整数运算时。我们必须设计测试用例进行验证。4.1 测试用例设计基础功能测试输入1\n1 1 预期输出1序列第一个数输入1\n1 3 预期输出1124输入1\n2 4 预期输出1214跨组求和测试输入1\n3 6 序列片段[2, 3, 1, 2]和8。输入1\n5 10 可以手工计算或写一个暴力程序验证。大数边界测试输入1\n1000000000 1000000000 验证程序是否能快速给出结果且不发生溢出。输入1\n1 1000000000000 测试极大范围的求和。可以先用暴力程序算一个小范围的再用我们的算法算大范围的对比前缀和逻辑是否正确。多组查询测试输入3\n1 1\n1 3\n5 10 验证程序能正确处理多组数据且变量没有残留错误。4.2 常见错误与调试溢出错误最隐蔽的错误。即使使用了longn*(n1)/2在二分判断时也可能溢出。例如当mid很大时mid * (mid 1)可能已经溢出成负数再除以2结果错误导致二分查找逻辑混乱。更安全的写法是if (mid (2L * x mid - 1) / mid)不这太复杂。一个实用的技巧是使用除法来判断if (mid (long) Math.ceil((Math.sqrt(1 8.0 * x) - 1) / 2))但这引入了浮点数可能有精度问题。竞赛中更常见的做法是在findGroup函数中使用BigInteger进行二分判断或者将条件改写为mid * (mid 1) / 2 x并相信评测数据不会让这个乘法溢出。实际上因为我们的上界是sqrt(2x)2当x达到10^12时mid大约为1.5e6mid*(mid1)约为2.25e12远小于Long.MAX_VALUE(~9e18)所以在这个特定问题中二分判断的溢出风险很低。但sumOfCompleteGroups中的溢出风险是真实存在的必须用前述方法处理。二分查找死循环或错误确保循环条件是left right更新边界是right mid和left mid 1。可以手动模拟x1和x2的情况进行验证。l-1为0的情况在main函数中计算prefixSum(l-1)时如果l1则参数为0。必须在prefixSum函数开始处判断if (x 0) return 0;否则在findGroup或后续计算中可能出现错误。5. 算法优化与思维延伸我们的算法已经达到了O(T log max(l, r))的复杂度对于蓝桥杯的评测机来说完全足够。但我们可以从思维层面进行一些延伸这有助于解决更复杂的问题。5.1 能否实现O(1)查询对于单次prefix_sum(x)我们目前需要一次O(log x)的二分查找来定位组号。有没有可能O(1)呢理论上我们可以通过解方程来直接求得组号。 我们需要解不等式n(n1)/2 x。即n^2 n - 2x 0。 由求根公式n (-1 sqrt(1 8x)) / 2。 所以group_idx ceil( (-1 sqrt(1 8x)) / 2 )。 在Java中我们可以这样计算long group (long) Math.ceil((Math.sqrt(1 8.0 * x) - 1) / 2);但是这里有一个巨大的坑浮点数精度问题当x很大时例如10^188.0*x可能超出double的精确表示范围Math.sqrt的结果也会有误差导致ceil取到错误的值。在算法竞赛中除非经过严格验证和调整否则不建议使用浮点数开方直接计算整数解。二分查找虽然多了一个log因子但它是绝对精确和安全的。所以O(log n)的二分法通常是这类问题的首选。5.2 问题变体与举一反三掌握了“123”序列的求解方法我们可以尝试解决一系列类似问题它们都是“分块序列求和”的变体序列变体序列变为1, 2,2, 3,3,3, 4,4,4,4, ...数字i重复i次。求和思路完全一样只是第k组的和变成了k * k前m个完整组的和公式需要重新推导平方和公式。二维查询题目可能不是求区间[l, r]的和而是多次询问序列中第k个数字是多少。这更简单先用二分定位组再计算组内偏移即可得到数字。反向查找给定一个和S问最少需要前多少项的和才能达到或超过S。这需要用到前缀和函数的单调性可以对前缀和进行二分查找。这类问题的通用解题框架是识别序列的分块规律。推导块大小、块内和、前n块总大小的公式。利用二分查找解决定位问题。小心处理求和公式中的溢出问题。5.3 蓝桥杯备赛经验谈从这道“123”题我们可以总结出几条应对蓝桥杯国赛级别算法题的经验切忌盲目暴力看到题目第一眼先看数据范围。如果l, r大到10^12O(n)的算法想都别想必须找O(log n)或O(1)的数学解法。学会观察与归纳题目描述的序列往往有很强的规律性。动手写前几项找规律。分组、分块是处理无限序列的常用手段。数学工具是利器等差数列求和、等比数列求和、平方和公式等基础数学知识要熟练。推导S_total(n) n(n1)(n2)/6的过程就是一次简单的数列求和。细节决定成败溢出这是Java选手在国赛中最容易栽跟头的地方。对于任何涉及long的乘法都要在脑子里过一遍中间结果会不会超过9e18如果可能就要设计防溢出计算。边界二分查找的边界、l-1为0的情况、n0时求和公式是否成立这些边界条件必须测试。精度慎用浮点数开方求整数解除非你完全清楚其误差范围并能处理。调试技巧对于不确定的算法可以写一个暴力Solve(long l, long r)函数通过模拟生成前N项N不要太大比如10000来验证优化算法的正确性。用随机数据对拍是发现隐蔽错误的好方法。最后把完整的、经过测试的代码再贴一遍你可以直接复制到蓝桥杯的练习系统里提交验证。记住理解思路比记住代码更重要。希望这篇长文能帮你彻底吃透“123”这道题并将其背后的思维方法应用到更多题目中去。// 最终复核版代码 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int T sc.nextInt(); while (T-- 0) { long l sc.nextLong(); long r sc.nextLong(); System.out.println(prefixSum(r) - prefixSum(l - 1)); } sc.close(); } private static long prefixSum(long x) { if (x 0) return 0; long group findGroup(x); long sumComplete sumOfCompleteGroups(group - 1); long cntBefore (group - 1) * group / 2; long pos x - cntBefore; long sumPartial pos * (pos 1) / 2; return sumComplete sumPartial; } private static long findGroup(long x) { long l 1, r (long) Math.sqrt(2 * x) 2; while (l r) { long mid l (r - l) / 2; if (mid * (mid 1) / 2 x) { r mid; } else { l mid 1; } } return l; } private static long sumOfCompleteGroups(long n) { if (n 0) return 0; long a n, b n 1, c n 2; // 除以2 if (a % 2 0) a / 2; else if (b % 2 0) b / 2; else c / 2; // 除以3 if (a % 3 0) a / 3; else if (b % 3 0) b / 3; else c / 3; return a * b * c; } }