蓝桥杯国赛123题解：二分查找与数学建模在无限序列求和中的应用

1. 从“123”到二分查找一道国赛题的解题心路看到“第十二届蓝桥杯国赛123”这个标题再结合“AC二分”这个后缀很多参加过算法竞赛的朋友大概会心一笑。这指的正是第十二届蓝桥杯全国总决赛软件类C/C组的一道编程题题目编号或简称是“123”。而“AC二分”则清晰地指出了这道题的核心解法——二分查找。这道题当年给不少选手留下了深刻印象它不像某些纯数学推导题那样烧脑也不像某些复杂模拟题那样繁琐但它巧妙地考察了选手对数据规模的理解、对算法工具的选择以及对边界条件的把控能力。今天我们就来彻底拆解这道题不仅复现AC的二分解法更要深入探讨其背后的设计逻辑、常见的思维误区以及如何将这种解题思路迁移到其他场景。简单来说这道题描述了一个由自然数序列构成的特殊字符串将正整数1234...依次拼接起来形成一个无限长的字符串“123456789101112131415...”。题目会给出若干次查询每次查询给出两个整数l和r要求你输出这个无限字符串中从第l个字符到第r个字符之间所有数字字符对应的数值之和。例如字符串前10位是“1234567891”那么l3, r7对应的子串是“34567”数字之和就是3456725。问题的核心挑战在于l和r的范围可以非常大通常上限在10^12甚至10^18量级你不可能真的去生成这个庞大的字符串。这就需要我们透过现象看本质用数学和算法来高效解决。2. 问题本质分析与数学模型建立要高效解决这个问题第一步是跳出“字符串”的直观表象建立清晰的数学模型。我们不能被“拼接”这个词迷惑去思考如何生成字符串而应该直接思考在这个由自然数拼接而成的序列中第k个位置上的数字到底是什么以及从第l个到第r个位置上的数字之和又该如何快速计算2.1 数字的位数与区间划分这是整个解题思路的基石。自然数在拼接时其数字位数是变化的1位数1-9共有9个数字每个数字占1个字符位置总共贡献9 * 1 9个字符。2位数10-99共有90个数字每个数字占2个字符位置总共贡献90 * 2 180个字符。3位数100-999共有900个数字每个数字占3个字符位置总共贡献900 * 3 2700个字符。...d位数共有9 * 10^(d-1)个数字每个数字占d个字符总共贡献9 * 10^(d-1) * d个字符。我们可以预先计算出当位数d增加时累计的字符总数。设total_len(d)表示所有位数不超过d的数字拼接起来的总字符长度。那么total_len(d) Σ_{i1}^{d} (9 * 10^(i-1) * i)这个计算量很小因为d不会很大例如10^12以内的数其位数d最多也就十几位。我们可以用一个数组len_prefix来存储total_len(d)其中len_prefix[i]表示所有i位数及更小的数字拼接后的总长度。例如len_prefix[1] 9(1-9)len_prefix[2] 9 180 189(1-99)len_prefix[3] 189 2700 2889(1-999)...2.2 定位给定位置k找出对应的数字现在假设我们想知道第k个字符是什么。我们可以利用len_prefix数组进行快速定位确定位数d在len_prefix数组中二分查找找到最小的d使得len_prefix[d] k。这意味着第k个字符位于某个d位数之中。确定是第几个d位数在d位数区间内排在第k个字符之前的、所有位数小于d的数字的总长度为prev_len len_prefix[d-1]如果d1则prev_len0。那么在d位数区间内第k个字符距离该区间起点的偏移量为offset k - prev_len - 1减1是为了从0开始计数。确定具体数字d位数的起始数字是start_num 10^(d-1)。由于每个d位数占d个字符所以offset / d的商就代表了这是第几个d位数从0开始。因此第k个字符所在的完整数字是num start_num (offset / d)。确定数字中的具体字符offset % d的结果指明了目标字符在这个数字num的十进制表示中的位置从左到右从0开始。例如如果num1234offset % d 1那么目标字符就是num的第2位数字即‘2’。可以通过将数字转为字符串或使用数学方法(num / (10^(d-1 - (offset%d)))) % 10来获取。这个“定位”函数get_digit(k)是后续所有计算的基础。它能在 O(log d) 的时间内完成效率极高。2.3 求和从l到r的数字之和最朴素的想法是循环从l到r调用get_digit(k)获取每个位置上的数字值然后累加。这在l和r很大且区间长度(r-l1)也很大时是不可行的。我们需要更高效的方法。这里的关键洞察是数字是以“完整的自然数”为单位被拼接进来的。虽然查询区间[l, r]可能切分在某个数字的中间但我们可以将其分解为三部分左边界不完整的数字从l开始到它所在数字的末尾。中间完整的数字在左边界数字和右边界数字之间的所有完整数字。右边界不完整的数字从右边界数字的开头到r结束。如果能快速计算出一个完整数字的字符和以及一个数字的一部分的字符和那么问题就转化为如何快速找到这些边界并利用前缀和思想进行快速区间求和。定义前缀和函数S(x)表示从第1个字符到第x个字符的所有数字之和。那么区间[l, r]的和就是S(r) - S(l-1)。因此问题转化为如何高效计算S(x)。计算S(x)的思路与定位类似但更进一层利用len_prefix和二分找到x所在的数字位数d以及在该位数区间内的偏移量。所有位数小于d的完整数字它们的总和是可以公式化快速计算的。例如所有1位数之和是12...945所有2位数之和是(1011...99)的和这是一个等差数列求和可以公式计算。我们可以像预处理len_prefix一样预处理一个sum_prefix[d]表示所有位数不超过d的完整数字的字符总和注意这里“总和”指的是将这些数字的每一位数字的值加起来而不是数字本身的值。例如数字12贡献的和是123。但更常见的做法是在定位过程中动态计算。对于位数等于d的数字它们可能被x截断。我们需要计算从该位数区间的起始数字到x所在数字可能不完整的所有数字的字符和。这可以通过计算等差数列和与处理不完整数字部分来实现。具体到“123”这道题一个更巧妙的思路被广泛采用二次二分。首先我们实现一个函数calc_sum(n)用于计算字符串中前n个完整数字注意是数字不是字符所构成的前缀的数字之和。例如前3个完整数字是1,2,3它们的数字之和是1236。这个函数同样可以用数学公式等差数列求和及其变体在O(log n)时间内完成因为我们需要知道第n个完整数字是几这又涉及到数字位数和二分查找。有了calc_sum(n)结合get_digit(k)的定位能力我们就可以计算S(x)首先定位第x个字符位于哪个数字假设是第N个数字的第几位。那么前N-1个完整数字的数字之和就是calc_sum(N-1)。第N个数字本身我们只取前(x字符在该数字中的位置1)位计算这几位数字的和。S(x) calc_sum(N-1) 第N个数字的部分和。这样计算一次S(x)的复杂度是 O(log N) ~ O(log x)。对于每次查询[l, r]我们只需要计算两次S(x)再做减法总复杂度就是 O(log max(l, r))完全可以处理极大的查询。3. 二分查找的核心应用与实现细节“AC二分”中的“二分”在本题中至少应用于两个关键环节这也是解题的精髓所在。3.1 第一次二分根据字符位置k定位数字N我们需要一个函数find_num_by_pos(k)返回第k个字符所在的完整数字是第几个数字即数字N。如前所述我们不能遍历。注意到如果我们知道了数字N我们可以计算出前N个数字拼接起来的总字符长度total_chars(N)。这个total_chars(N)是一个关于N的单调递增函数。因此我们可以对N进行二分查找寻找最小的N使得total_chars(N) k。那么第k个字符就位于第N个数字中。这里的关键是如何高效计算total_chars(N)。这需要根据N的位数进行分段计算假设N是一个d位数。那么所有位数小于d的数字1位数到d-1位数的总字符数我们已经预计算好了就是len_prefix[d-1]。位数等于d的数字从start 10^(d-1)开始到N结束共有cnt N - start 1个。每个数字贡献d个字符所以这部分贡献cnt * d个字符。因此total_chars(N) len_prefix[d-1] (N - start 1) * d。在二分查找N时我们需要反复计算total_chars(mid)这就要求我们能根据mid快速判断它的位数d。这可以通过另一个预处理的“数字个数前缀和”数组或者直接用数学方法while (base mid) base * 10来得到位数后者在二分查找的log次调用中是可以接受的。3.2 第二次二分在计算calc_sum(n)时定位数字边界函数calc_sum(n)要计算前n个完整数字的数字之和。同样我们需要分段计算按数字位数所有位数小于d的完整数字之和记为sum_smaller可以用公式提前算好或预处理。例如所有1位数的和是45所有2位数的和是(1099)*90/2 4905但注意这里要求和的是每个数字的每一位数字值之和对于两位数ab其数字和是ab。所有两位数的数字值之和并不是4905而是需要另外计算。更简单的方法是对于所有i位数其数字和有一个规律但直接预处理一个sum_prefix[d]数组更稳妥其中sum_prefix[d]表示所有位数不超过d的数字的数字值之和。这个数组可以通过遍历位数利用位数、数字个数和平均数字和来递推计算。对于位数等于d的数字从start 10^(d-1)到第n个数字记为end_num我们需要计算这段区间内所有数字的数字值之和。如果n就是end_num那么这就是一个从start到end_num的连续整数序列我们可以用等差数列求和公式先求出这些数字本身的和但我们需要的是每个数字的各位数之和这没有简单的闭式解。因此通常我们在这里不直接计算数字值之和而是换一种思路。更常见的“二次二分”策略如下第一次二分如上所述找到最小的数字N使得total_chars(N) k。我们得到了第k个字符所在的数字num以及它在该数字中的位置pos_in_num。此时我们知道前N-1个数字是完整的。我们需要计算前N-1个数字的数字值之和。这就是calc_sum(N-1)。如何计算calc_sum(m)前m个数字的数字值之和我们可以再对m进行二分查找的“思想”但更准确地说是按位数分段累加。我们预先计算出所有1位数、2位数、...的数字值总和。假设我们要计算calc_sum(m)确定m的位数d_m即第m个数字是几位数。这可以通过与len_prefix类似的“数字个数前缀”数组二分得到。累加所有位数小于d_m的数字值总和直接从预处理的sum_prefix[d_m-1]获取。对于位数等于d_m的数字从start_d 10^(d_m-1)到m共有cnt m - start_d 1个。我们需要计算这cnt个d_m位数的数字值之和。这里没有一个简单的公式但我们可以利用一个关键性质对于一个d位数其数字值之和可以分解计算。然而在竞赛中由于d_m不会很大比如小于15且cnt可能很大直接循环累加这cnt个数字的各位和仍然可能超时如果cnt是10^9量级。因此需要找到一个能快速计算一段连续d位数数字值之和的方法。一个可行的方法是考虑每个数位上的数字之和。对于从A到B的连续d位数个位上的数字会从0到9循环十位、百位等高位变化较慢。我们可以用数位DP的思想或者公式来计算但实现较复杂。正是由于直接计算calc_sum(m)的复杂性在“123”这道题的标准解法中通常采用另一种等价的、但更易于实现的二分策略直接二分答案的“数字个数”N并与字符位置k进行换算。标准二分解法流程实现函数get_sum_of_chars_by_num_count(n)计算前n个完整数字所贡献的总字符长度。这个函数容易实现就是上面提到的total_chars(n)。实现函数get_digit_sum_by_num_count(n)计算前n个完整数字的数字值之和。这个函数需要按位数分段计算是本题的难点但我们可以用循环遍历位数来实现因为n最大可能为10^9量级但位数只有10多种所以这个循环是常数复杂度。遍历位数d从1开始递增。当前d位数的起始数字为start 10^(d-1)结束数字为end 10^d - 1共有count end - start 1 9 * 10^(d-1)个。如果n大于等于count那么这整个d位数区间的数字都可以完整计入。计算这整个区间所有数字的数字值之和并累加到结果中然后n - count。如果n小于count那么只有前n个d位数需要计入。计算从start到start n - 1这n个连续数字的数字值之和累加到结果中然后n 0跳出循环。计算一段连续数字的数字值之和可以用公式。例如对于连续数字[L, R]其数字值之和等于(L到R的每个数字的各位和之和)。虽然没有单个闭式解但我们可以快速计算每个数字x的各位和S(x)可以用一个简单循环或预处理的函数得到。由于这里n已经不大进入这个分支时n count而count对于大位数来说可能很大但对于我们处理的最后一段n是剩余量我们可以用循环累加这n个数字的S(x)。在题目合理的约束下查询次数不多且最后一段的n不会巨大到超时这是可以接受的。更严谨的做法是推导S(x)的前缀和公式但竞赛中为了简化有时会利用数据约束允许这种“小范围循环”。对于每次查询(l, r)目标是求S(r) - S(l-1)。要计算S(x)我们需要知道前x个字符对应到了前多少个完整数字设为cnt_full以及最后一个不完整数字的部分。如何由x得到cnt_full这就是第一次二分。我们对数字个数cnt进行二分利用get_sum_of_chars_by_num_count(cnt)函数即总字符长度与x比较找到最小的cnt使得get_sum_of_chars_by_num_count(cnt) x。这个cnt就是cnt_full如果恰好等于x则第x个字符是第cnt个数字的最后一位如果大于x则第x个字符在第cnt个数字中间。那么前cnt_full - 1个数字的数字值之和就是get_digit_sum_by_num_count(cnt_full - 1)。第cnt_full个数字记为num的部分和需要根据x在该数字中的位置来计算。我们可以通过x - get_sum_of_chars_by_num_count(cnt_full - 1)得到x在第cnt_full个数字中的字符偏移量从1开始从而确定要取这个数字的前几位并计算这几位数字的和。由此得到S(x)。这个流程中对每次查询我们进行了两次二分查找为了求cnt_full以及若干次常数复杂度的前缀和计算。总时间复杂度为 O(Q * log N)其中Q是查询次数N是可能的数字个数上限与l, r的大小相关完全可以满足要求。4. 代码实现、调试与常见“坑点”理解了原理实现起来仍有不少细节需要注意。下面给出一个清晰的C实现框架并逐一分析关键点。4.1 核心函数设计与预处理首先我们需要预计算两个关键数组或者实现对应的计算函数。#include iostream #include algorithm using namespace std; using ll long long; // 必须使用长整型 // 预计算到足够大的位数例如18位可覆盖10^18以内的字符位置 const int MAX_D 18; ll len_prefix[MAX_D 1]; // len_prefix[i]: 所有位数 i 的数字的总字符长度 ll cnt_prefix[MAX_D 1]; // cnt_prefix[i]: 所有位数 i 的数字的总个数 ll sum_prefix[MAX_D 1]; // sum_prefix[i]: 所有位数 i 的数字的数字值之和 void init() { ll base 1; for (int d 1; d MAX_D; d) { ll count 9 * base; // d位数的个数 ll total_len count * d; // d位数贡献的总字符长度 len_prefix[d] len_prefix[d-1] total_len; cnt_prefix[d] cnt_prefix[d-1] count; // 计算所有d位数的数字值之和对于每个d位数其数字和平均约为4.5*d但需要精确计算 // 更精确的方法d位数从 start base 到 end base*10 - 1 // 数字值之和 Σ_{numstart}^{end} S(num)其中S(num)是num的各位和。 // 我们可以利用数位贡献来快速计算每个数位上数字0-9出现的次数是相等的。 // 对于d位数共有count个数字每个数字有d位。每个数位上0-9每个数字出现的次数都是 count / 10 9*base/10。 // 注意最高位不能为0所以最高位第d位上数字1-9各出现 base 次。 ll sum_digit 0; if (d 1) { // 1位数1-9 sum_digit 45; // 12...9 } else { // 非最高位共d-1位每位上0-9出现次数相同 ll non_top_count count / 10; // 9 * base / 10 ll sum_per_non_top_pos non_top_count * 45; // 01...945 sum_digit sum_per_non_top_pos * (d - 1); // 最高位数字为1到9各出现 base 次 ll sum_top (1 9) * 9 / 2 * base; // 1*base 2*base ... 9*base base*(12...9) sum_digit sum_top; } sum_prefix[d] sum_prefix[d-1] sum_digit; base * 10; } }4.2 关键函数实现// 函数1给定数字个数n返回前n个数字拼接的总长度 ll total_chars_by_cnt(ll n) { if (n 0) return 0; // 找到n是几位数 int d 1; ll base 1; while (cnt_prefix[d] n) { d; base * 10; } // 此时d是n所在的位数区间 ll prev_cnt cnt_prefix[d-1]; // 位数小于d的数字总个数 ll start_num base; // d位数的起始数字 ll cnt_in_d n - prev_cnt; // 在d位数中是第几个从1开始 ll total_len len_prefix[d-1] cnt_in_d * d; return total_len; } // 函数2给定数字个数n返回前n个数字的数字值之和 ll total_digit_sum_by_cnt(ll n) { if (n 0) return 0; ll res 0; ll remaining n; int d 1; ll base 1; while (remaining 0) { ll max_cnt_in_d 9 * base; // d位数的总个数 ll cnt min(remaining, max_cnt_in_d); // 计算从 start 开始的连续cnt个d位数的数字值之和 ll start base; ll end start cnt - 1; // 快速计算区间[start, end]内所有数字的数字值之和 // 方法数位贡献法或如果cnt不大直接循环这里演示循环实际比赛若cnt可能很大需优化 // 注意这里为了逻辑清晰使用循环在cnt很大时如1e9会超时。实际需要数位DP或公式优化。 // 下面给出一个针对本题数据范围通常n1e9左右可行的简化思路 // 由于d不会很大我们可以用等差数列思想近似但更稳妥的是用预处理的sum_prefix。 // 实际上我们可以利用之前预处理的思想但这里我们换一种方式 // 我们知道前 cnt_prefix[d] 个数字的总和是 sum_prefix[d]。 // 如果我们需要的是前n个且n跨越了完整的d位数区间我们可以直接用 sum_prefix[d]。 // 如果不完整我们需要计算从 start 到 end 的d位数之和。 // 计算从L到R的d位数数字和可以写一个函数 calc_range_sum(L, R, d)。 // 由于dMAX_D且区间长度cnt可能很大我们需要O(d)的算法而不是O(cnt)。 // 这里省略 calc_range_sum 的详细实现它需要分解每个数位进行计算。 // 假设我们已经实现了 calc_range_sum(L, R, d) res calc_range_sum(start, end, d); remaining - cnt; d; base * 10; } return res; } // 注意上面的 total_digit_sum_by_cnt 函数中的 calc_range_sum 是实现难点。一个可行的O(d)实现是 ll calc_range_sum(ll L, ll R, int d) { ll sum 0; // 从最低位到最高位计算贡献 ll pow10 1; for (int pos 0; pos d; pos) { // 计算在[L, R]区间内当前数位上所有数字的和 // 数位循环周期为10 ll cycle (R - L 1) / 10; ll remainder (R - L 1) % 10; ll digit_sum_cycle 45 * cycle; // 每个完整周期(0-9)的和是45 // 处理剩余部分 ll start_digit (L / pow10) % 10; for (ll i 0; i remainder; i) { ll digit (start_digit i) % 10; digit_sum_cycle digit; } sum digit_sum_cycle * pow10; // 注意当前位的权重是pow10但这里我们加的是数字值不是数值。 // 等等这里有个误区我们计算的是数字值之和即每位数字直接相加。 // 例如数字123数字和是1236。我们不需要乘以位权。 // 所以对于每个位置我们只需要累加这个位置上所有数字的“值”不需要乘pow10。 // 修正 // sum digit_sum_cycle; // 直接累加当前位的数字和 // 但这样对吗我们是在对每个位置分别计算。对于区间[L,R]中的每个数其第pos位的数字都会被加到总和中。 // 所以总数字和 Σ_{numL}^{R} Σ_{pos0}^{d-1} digit(num, pos)。 // 交换求和顺序 Σ_{pos0}^{d-1} Σ_{numL}^{R} digit(num, pos)。 // 内层 Σ_{numL}^{R} digit(num, pos) 就是我们上面计算的 digit_sum_cycle对于第pos位。 // 因此 sum digit_sum_cycle; pow10 * 10; } return sum; }4.3 主查询逻辑与二分查找// 函数3给定字符位置x返回S(x)前x个字符的数字值之和 ll S(ll x) { if (x 0) return 0; // 二分查找最小的数字个数cnt使得 total_chars_by_cnt(cnt) x ll low 1, high 1e18; // 上界需要足够大例如1e18 ll cnt_full 0; while (low high) { ll mid (low high) / 2; if (total_chars_by_cnt(mid) x) { cnt_full mid; high mid - 1; } else { low mid 1; } } // cnt_full: 第x个字符所在的数字是第cnt_full个数字 // 前cnt_full-1个完整数字的总和 ll sum total_digit_sum_by_cnt(cnt_full - 1); // 计算第cnt_full个数字的部分和 ll chars_before total_chars_by_cnt(cnt_full - 1); // 前cnt_full-1个数字的总字符数 ll offset x - chars_before; // 在第cnt_full个数字中是第几个字符从1开始 // 找出第cnt_full个数字是多少 int d; ll base 1; for (d 1; d MAX_D; d) { if (cnt_prefix[d] cnt_full) break; base * 10; } ll prev_cnt cnt_prefix[d-1]; ll num base (cnt_full - prev_cnt - 1); // 第cnt_full个数字的实际值 // 计算数字num的前offset位数字之和 ll partial_sum 0; // 将num转为字符串或逐位取模 string num_str to_string(num); for (int i 0; i offset; i) { partial_sum num_str[i] - 0; } sum partial_sum; return sum; } // 主函数 int main() { init(); int Q; cin Q; while (Q--) { ll l, r; cin l r; cout S(r) - S(l - 1) endl; } return 0; }4.4 常见“坑点”与调试心得数据类型溢出这是最大的坑。l和r上限可达10^12甚至更大涉及的长度、数字个数、中间计算结果很容易超出int范围。必须全程使用long longC或int64其他语言。二分查找的边界二分查找cnt_full时上下界low和high的设定要足够宽。high可以设为一个很大的数如1e18因为total_chars_by_cnt(n)的增长速度比n快所以满足条件的n不会特别大。但也要注意不要设得太大导致total_chars_by_cnt(mid)计算溢出。下标与偏移量的转换在计算offset、cnt_in_d时是“从0开始”还是“从1开始”必须非常清晰并保持全程一致。一个错误的-1或1会导致结果全盘皆输。建议在关键步骤加上注释并用小数据如l,r很小进行验证。部分和计算的正确性计算calc_range_sum或total_digit_sum_by_cnt是本题最易错的部分。务必用暴力程序对拍小数据确保从1到N的数字和计算绝对正确。可以单独测试这个函数输入一些连续的区间与暴力累加的结果对比。预处理数组的大小MAX_D需要足够大以覆盖数据范围。如果l,r最大为10^18那么数字位数最多大约为18因为10^18是19位数但我们的序列从1开始最大的数字位数可能接近18或19。保险起见可以设到20。时间复杂度与常数优化虽然算法是O(Q log N)但total_digit_sum_by_cnt中的calc_range_sum如果实现不当如对每个数位进行了一个O(区间长度)的循环在极端情况下可能会超时。务必确保calc_range_sum是O(位数)的即O(log N)级别的。对拍与调试在竞赛中写一个暴力程序生成有限长度的字符串如前10000个字符用于对拍随机生成的l, r在暴力程序可处理的范围内是发现逻辑错误最有效的方法。5. 举一反三类似问题的解题模式与思维拓展“123”这道题的价值远不止于AC。它提供了一种处理“无限拼接序列”问题的经典范式。我们可以从中提炼出通用的解题步骤定义序列与映射明确序列的生成规则如本题的自然数拼接。建立从“索引”如字符位置k到“序列元素”如第几个数字、该数字的值、在该数字中的位置的映射关系。这通常需要结合数学规律位数、区间和二分查找。预处理与快速计算根据序列的规律预处理出一些前缀信息如len_prefix,cnt_prefix,sum_prefix以便在O(1)或O(log N)时间内回答关于区间和、定位的子问题。二分查找定位当需要根据一个“全局索引”找到对应的“生成元”时如根据字符位置找数字二分查找是利器前提是能快速计算某个“生成元”之前的总长度或总量。分段处理与合并对于区间查询问题将其分解为“完整块”和“不完整块”。完整块的信息可以用前缀和快速得到不完整块则利用定位功能单独计算。注意边界与溢出始终警惕数据范围和下标转换。这种模式可以迁移到许多类似问题例如“456”问题拼接序列变成平方数、斐波那契数列等。“数字1的个数”变体不是求和而是统计区间内某个特定数字如‘1’出现的次数。“第K小的特殊数”在某种生成规则下求第K个满足条件的数。本质上也是建立索引到数值的映射。解决这类问题的核心能力是剥离具体场景抽象出数学模型识别单调性并用二分加速最后小心处理边界细节。通过“123”这道题的深入练习能够极大提升对这类复合数据结构和二分查找应用的理解。在实际编码中清晰的函数划分如total_chars_by_cnt,total_digit_sum_by_cnt,S(x)和充分的边界测试是保证一次AC的关键。