1. 从一道题看字符串构造的底层逻辑第一次看到 E1. Numerical Sequence (easy version) 这个题号的时候我下意识以为又是一道纯数学推导题毕竟 Codeforces Round #587 的 Div. 3 里E 题通常都是压轴级别的存在。但仔细读完题面才发现这其实是一道披着数学外衣的字符串构造与查询问题。它的核心操作非常朴素把所有的正整数按顺序拼成一个无限长的字符串然后回答若干次查询每次查询问这个无限长字符串的第 k 个字符是什么。听起来是不是特别简单我第一次做的时候也是这么想的觉得直接暴力拼接不就行了。但真正动手写的时候才发现这里面藏着好几个容易踩的坑尤其是当 k 的范围达到 10^9 甚至更大的时候暴力拼接的时间和空间都会直接爆炸。这道题在 Div. 3 里被定位为 easy version说明它的查询规模相对温和但即便如此如果不去思考字符串长度增长的规律照样会超时。这篇文章我打算从这道题出发把字符串构造类问题的通用分析思路、长度预估方法、以及实际编码时的优化技巧完整地拆一遍。不管你是刚接触算法竞赛的新手还是已经刷了几百道题想回头巩固基础的老手我相信这篇内容都能给你一些新的启发。尤其是那些对“无限长字符串”这类问题感到无从下手的朋友看完之后应该能建立起一套自己的分析框架。2. 题目核心需求与暴力解法的局限性2.1 无限字符串到底长什么样我们先把问题具象化。把正整数从 1 开始依次写出来中间不加任何分隔符得到的字符串就是123456789101112131415161718192021222324252627282930...这个字符串是无限长的因为正整数有无穷多个。题目要求我们回答的是在这个字符串中第 k 个位置上的字符是什么。注意这里的 k 是从 1 开始计数的也就是说第 1 个字符是 1第 2 个字符是 2第 9 个字符是 9第 10 个字符是 1来自数字 10 的十位第 11 个字符是 0来自数字 10 的个位以此类推。这个构造规则本身没有任何歧义问题在于如何高效地定位到第 k 个字符。如果你真的去模拟拼接这个过程当 k 达到 10^9 的时候你需要拼接的数字大概会到几亿的级别光是字符串的长度就超过 10^9 个字符内存直接爆掉。所以暴力模拟是绝对行不通的必须找到一种数学上的定位方法。2.2 暴力拼接为什么不可行我刚开始写这道题的时候第一反应就是用一个循环不断把数字转成字符串然后追加到一个大字符串后面直到长度超过 k然后直接返回对应位置的字符。这个思路在小规模数据下完全正确但问题在于它的时间复杂度是 O(k) 的。当 k 10^9 时你需要进行大约 10^9 次字符追加操作这在任何评测系统上都会超时。更致命的是空间复杂度。一个长度为 10^9 的字符串每个字符占 1 个字节那就是 1GB 的内存。就算评测机给你 256MB 的内存限制你也远远不够用。所以暴力法在空间和时间两个维度上都是不可接受的。那有没有办法不实际构造这个字符串而是通过数学计算直接定位呢答案是肯定的。我们需要做的是把“第 k 个字符”这个问题转化为“第 k 个字符属于哪个数字以及是这个数字的第几位”。只要能做到这一点我们就可以直接把这个数字算出来然后取出对应的那一位字符。2.3 分块思想按位数切分问题这里的关键洞察是数字的位数是分段的。1 到 9 都是一位数10 到 99 都是两位数100 到 999 都是三位数以此类推。每一段数字在字符串中占据的总长度是可以直接算出来的。比如 1 到 9 这 9 个数字每个占 1 个字符总共占 9 个字符。10 到 99 这 90 个数字每个占 2 个字符总共占 180 个字符。100 到 999 这 900 个数字每个占 3 个字符总共占 2700 个字符。一般地对于 d 位数它的范围是从 10^(d-1) 到 10^d - 1一共有 9 * 10^(d-1) 个数字每个数字占 d 个字符所以这一段的总长度是 9 * 10^(d-1) * d。有了这个公式我们就可以先确定第 k 个字符落在哪一段里。具体做法是从 d 1 开始不断减去当前段的长度直到 k 小于等于当前段的长度为止。此时我们就知道第 k 个字符属于一个 d 位数。这个思路其实和很多字符串构造题是相通的。比如有一类题是问“把 1 到 n 的所有数字拼起来第 k 位是什么”解法几乎一模一样。还有一类题是问“在某个进制下第 k 个字符是什么”也是同样的分块思想。所以掌握这一套方法可以解决一大类问题。3. 核心细节解析与实操要点3.1 如何确定第 k 位落在哪个数字上假设我们已经通过上面的分块方法确定了第 k 个字符属于一个 d 位数。接下来要做的就是在这个 d 位数的区间内找到具体是哪一个数字以及是这个数字的第几位。设当前段的起始数字是 start 10^(d-1)当前段中每个数字占 d 个字符。如果我们已经减去了前面所有段的长度剩下的 k 表示在当前段中的偏移量从 1 开始计数。那么第 k 个字符所属的数字是number start (k - 1) / d这个公式的原理很简单每个数字占 d 个字符所以 (k - 1) / d 就是当前数字相对于 start 的偏移量。注意这里用的是整数除法因为我们要找的是完整的数字个数。确定了数字之后还需要确定是这个数字的第几位。这个也很容易digit_index (k - 1) % d这个 digit_index 表示的是从最高位开始数的第几位0 表示最高位。比如数字是 12345digit_index 0 表示 1digit_index 1 表示 2以此类推。最后我们只需要把这个数字转成字符串然后取出第 digit_index 个字符即可。3.2 边界条件的处理在实际编码的时候有几个边界条件特别容易出错我在这里逐一说明。第一个是 k 正好落在某一段的最后一个字符上。比如 k 9 的时候它正好是数字 9 的个位也是第一段的最后一个字符。这时候用上面的公式计算number 1 (9 - 1) / 1 9digit_index (9 - 1) % 1 0结果是 9完全正确。但如果 k 10它属于第二段的第一个字符这时候前面的段长度是 9减去之后 k 变成 1number 10 (1 - 1) / 2 10digit_index (1 - 1) % 2 0结果是 1也就是数字 10 的最高位也是正确的。第二个是 k 非常大的时候比如 k 10^9。这时候我们需要计算到 d 9 甚至 d 10 的段。在计算段长度的时候要注意使用 64 位整数因为 9 * 10^8 * 9 已经接近 10^10 了32 位整数会溢出。这一点在 C 里尤其要注意建议统一使用 long long 类型。第三个是当 k 刚好等于某一段的总长度时减去之后 k 会变成 0。这时候需要特别处理因为我们的公式是基于 k 1 的。实际上如果 k 变成了 0说明第 k 个字符正好是上一段的最后一个字符。所以在减的时候应该先判断 k 是否大于当前段长度如果大于才减否则就留在当前段处理。3.3 预处理与查询的权衡这道题的 easy version 通常查询次数不会太多可能就几十次到几百次。但如果是 hard version查询次数可能会达到 10^5 甚至更多。这时候如果每次查询都从头开始算虽然单次查询的复杂度是 O(log k)但总复杂度就是 O(q * log k)在 q 10^5 的时候可能会有点紧张。一个常见的优化是预处理出每一段的累积长度这样每次查询的时候可以直接用二分查找来确定落在哪一段把单次查询的复杂度降到 O(log log k)。不过对于 easy version 来说直接线性扫描每一段就足够了因为 d 最多也就到 10 左右循环次数非常少。我在实际写的时候通常会先写一个函数来计算第 k 位是什么然后在主函数里循环处理每个查询。这样代码结构清晰也方便调试。如果遇到性能问题再考虑加预处理。4. 完整实操流程与代码实现4.1 算法步骤拆解在动手写代码之前我习惯先把算法的步骤用自然语言写清楚这样编码的时候不容易乱。这道题的完整步骤如下读入查询次数 q以及每次查询的 k。对于每个 k初始化当前段的起始数字 start 1当前段的位数 d 1。计算当前段的总长度 len 9 * start * d。如果 k len则 k - lenstart * 10d 1回到步骤 3。否则第 k 个字符属于一个 d 位数。计算 number start (k - 1) / ddigit_index (k - 1) % d。把 number 转成字符串输出第 digit_index 个字符。处理下一个查询直到所有查询处理完毕。这个流程非常直观基本上就是把前面的分析翻译成了代码。需要注意的是步骤 3 中的 len 可能会很大要用 64 位整数。步骤 4 中的 start * 10 也要注意不要溢出不过对于 k 10^9 的情况start 最多到 10^9 左右用 long long 完全够用。4.2 C 实现与注释下面是我自己写的 C 实现加上了详细的注释方便大家理解每一步在做什么。#include bits/stdc.h using namespace std; typedef long long ll; // 计算无限字符串中第 k 个字符是什么 char solve(ll k) { ll start 1; // 当前段的起始数字 int d 1; // 当前段每个数字的位数 while (true) { // 当前段的总长度9 * start * d // 注意 start 就是 10^(d-1)所以 9 * start 就是当前段数字的个数 ll len 9 * start * d; if (k len) { // 如果 k 不在当前段减去当前段长度进入下一段 k - len; start * 10; d 1; } else { // k 在当前段中 // 计算具体的数字 ll number start (k - 1) / d; // 计算是这个数字的第几位从最高位开始0-indexed int digit_index (k - 1) % d; // 转成字符串后取出对应字符 string s to_string(number); return s[digit_index]; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin q; while (q--) { ll k; cin k; cout solve(k) \n; } return 0; }这段代码的核心就是 solve 函数它接受一个 k返回对应的字符。主函数里循环处理每个查询输出结果。整体逻辑非常清晰没有什么复杂的技巧。4.3 关键参数的计算过程演示为了让大家更直观地理解这个算法的执行过程我拿几个具体的 k 值来手动走一遍。案例一k 10初始start 1, d 1, len 9 * 1 * 1 9k 10 9所以 k 10 - 9 1start 10, d 2现在 len 9 * 10 * 2 180k 1 180留在当前段number 10 (1 - 1) / 2 10digit_index (1 - 1) % 2 0数字 10 转成字符串是 10第 0 位是 1结果1案例二k 11初始start 1, d 1, len 9k 11 9k 11 - 9 2start 10, d 2len 180k 2 180number 10 (2 - 1) / 2 10digit_index (2 - 1) % 2 1数字 10 的第 1 位是 0结果0案例三k 100初始start 1, d 1, len 9k 100 9k 100 - 9 91start 10, d 2len 180k 91 180number 10 (91 - 1) / 2 10 45 55digit_index (91 - 1) % 2 0数字 55 的第 0 位是 5结果5通过这三个案例大家可以清楚地看到每一步的计算过程。实际编码的时候这些计算都是自动完成的我们只需要保证公式写对就行。4.4 时间复杂度与空间复杂度分析这个算法的时间复杂度是 O(log k)因为每次循环 d 增加 1而 d 最多到 log10(k) 左右。对于 k 10^9d 最多到 10循环次数不超过 10 次。每次循环内部都是常数时间的运算所以单次查询非常快。空间复杂度是 O(1)除了几个变量之外不需要额外的存储空间。这也是这种数学方法相对于暴力拼接的巨大优势。如果查询次数是 q那么总时间复杂度是 O(q * log k)。对于 q 1000 和 k 10^9总运算量大约是 10000 次完全可以在 1 毫秒内完成。所以这个算法在性能上是没有任何问题的。5. 常见问题与排查技巧实录5.1 整数溢出问题这是这道题最容易踩的坑没有之一。我在第一次提交的时候就是因为用了 int 类型来存储 len结果在 k 比较大的时候直接溢出了导致死循环或者错误答案。具体来说当 d 9 的时候start 10^8len 9 * 10^8 * 9 8.1 * 10^9。这个数字已经超过了 32 位有符号整数的最大值 2.147 * 10^9。如果你用 int 来存 len它就会变成一个负数然后 k len 的判断就会出错程序就会陷入死循环。解决办法很简单把所有涉及长度计算的变量都声明为 long long。在 C 里long long 是 64 位的最大值大约是 9.22 * 10^18足够容纳这道题的所有计算。我在代码里把 start、len、k 都用了 ll 类型就是为了避免这个问题。提示在算法竞赛中只要涉及到长度、和、乘积等可能超过 10^9 的量一律用 long long不要犹豫。多占一点内存无所谓溢出导致的错误才是最难排查的。5.2 边界条件的处理前面提到过当 k 刚好等于某一段的总长度时减去之后 k 会变成 0。这时候如果直接套公式number start (0 - 1) / d由于整数除法的特性(0 - 1) / d 在 C 里是 0因为 -1 / d 向零取整所以 number 会变成 start这其实是错误的。正确的做法是在判断的时候用 k len 而不是 k len。这样当 k len 时程序会留在当前段处理number start (len - 1) / d这个结果正好是当前段的最后一个数字digit_index (len - 1) % d正好是那个数字的最后一位。这样就完全正确了。我在代码里用的是 if (k len)这就是为了避免 k 变成 0 的情况。大家在自己写的时候一定要注意这个细节否则会在某些特定的 k 值上出错。5.3 查询次数很多时的优化虽然 easy version 的查询次数通常不多但如果你想把这道题当成 hard version 来练手就需要考虑查询次数达到 10^5 的情况。这时候每次查询都从头开始扫描每一段虽然单次很快但总时间可能会接近时限。一个简单的优化是预处理出每一段的累积长度存到一个数组里。然后每次查询的时候用二分查找upper_bound来找到 k 落在哪一段。这样单次查询的复杂度从 O(log k) 降到了 O(log log k)对于 10^5 次查询来说提升还是很明显的。不过对于 easy version 来说直接线性扫描就足够了因为 d 最多到 10循环次数非常少。我在实际比赛中也是用的线性扫描完全没有性能问题。5.4 常见错误速查表错误类型典型表现原因解决方法整数溢出死循环或错误答案用 int 存储 len改用 long long边界错误特定 k 值答案错误k 减到 0用 k len 判断索引错误输出字符不对digit_index 计算错误检查 (k-1)%d类型错误输出乱码to_string 用法错误确认 number 是整数超时程序运行超时暴力拼接改用数学定位法这张表里列的是我自己和身边朋友在写这道题时最常遇到的几个问题。如果你在调试的时候发现答案不对可以对照这张表逐一排查通常很快就能找到问题所在。5.5 独家避坑技巧除了上面这些常见问题我再分享几个自己在实践中总结的小技巧。第一个技巧是在写 solve 函数的时候先把所有变量都声明为 long long包括 d。虽然 d 实际上不会超过 10但统一类型可以避免很多隐式的类型转换问题。我在早期写代码的时候就因为 d 是 int 而 start 是 long long导致 9 * start * d 的计算过程中出现了溢出排查了很久才发现。第二个技巧是在计算 number 的时候先用一个临时变量存 (k - 1) / d然后再加到 start 上。这样如果中间结果有问题可以方便地打印出来调试。直接写成一行的好处是简洁但调试的时候不太方便。第三个技巧是对于 k 比较小的情况比如 k 100可以直接暴力构造字符串来验证自己的数学方法是否正确。我在写完 solve 函数之后通常会写一个暴力版本然后对 k 从 1 到 1000 逐一对比两个版本的结果确保完全一致。这个对拍的方法非常有效可以帮你发现绝大多数逻辑错误。6. 从这道题延伸出的通用解题框架6.1 字符串构造类问题的通用思路这道题虽然简单但它代表了一类非常典型的字符串构造问题。这类问题的共同特点是有一个明确的构造规则生成了一个很长的甚至是无限的字符串然后要求你回答某个位置上的字符是什么。对于这类问题通用的解题框架是分析字符串的构造规律找到可以分块的地方。计算每一块的长度通常可以用数学公式直接算出来。通过减去前面块的长度定位到目标字符所在的块。在块内继续定位直到找到具体的字符。这个框架不仅适用于这道题还适用于很多类似的题目。比如“把所有的平方数拼起来第 k 位是什么”、“把斐波那契数列拼起来第 k 位是什么”等等。只要你能找到分块的依据就能用同样的方法解决。6.2 数学定位法与模拟法的取舍在算法竞赛中数学定位法和模拟法是两种常见的解题思路。模拟法直观易懂但往往时间和空间复杂度较高数学定位法效率极高但需要一定的推导能力。我的经验是如果题目的数据范围允许模拟比如 k 10^6那么直接模拟是最稳妥的选择不容易出错。但如果数据范围很大比如 k 10^9 或更大就必须用数学定位法否则一定会超时。这道题的 easy version 其实数据范围并不大可能 k 最多到 10^9 左右。但即便如此暴力拼接 10^9 个字符也是不可接受的。所以从这道题开始练习数学定位法是一个很好的起点。6.3 类似题目的推荐练习路径如果你觉得这道题做起来很轻松想找类似的题目继续练习我推荐按照以下路径逐步提升第一步先做几道“把 1 到 n 拼起来第 k 位是什么”的题目巩固分块定位的基本功。第二步尝试“把平方数或立方数拼起来”的题目这类题目的分块依据稍微复杂一些需要你推导每一段的长度公式。第三步挑战“在某个进制下拼起来”的题目这类题目需要你处理进制转换难度会更高一些。通过这样的渐进式练习你可以逐步建立起对字符串构造类问题的直觉和信心。等到比赛的时候再遇到类似的题目就能很快找到思路。6.4 实际编码中的调试经验最后再分享一些调试经验。这类数学定位的题目最容易出错的地方就是边界条件和整数溢出。我的建议是在写完代码之后不要急着提交先自己构造一些测试数据来验证。具体来说可以写一个暴力版本的程序对于 k 从 1 到 10000 逐一计算答案然后和你的数学版本对比。如果所有结果都一致那么基本可以确定你的数学推导是正确的。如果发现不一致就找到第一个不一致的 k 值手动模拟一遍看看是哪一步出了问题。这个方法虽然看起来有点笨但非常有效。我在比赛中经常用这个方法来验证自己的解法尤其是在时间充裕的情况下对拍可以帮你避免很多不必要的罚时。注意对拍的时候要确保两个程序用的是同一套输入输出格式否则对比起来会很麻烦。另外暴力版本的程序要尽量写得简单直接不要引入额外的优化否则可能会掩盖问题。7. 个人实操体会与进阶建议这道题我从第一次见到到完全吃透大概花了半个小时。前二十分钟都在想怎么暴力模拟后十分钟才突然意识到可以用数学方法直接定位。这个转变的过程其实很有意思它让我重新审视了自己面对问题时的思维定式。很多时候我们拿到一道题第一反应就是“怎么模拟这个过程”但往往忽略了“这个过程有没有规律可循”。字符串构造类问题尤其如此因为字符串的拼接看起来是一个线性的过程但实际上它的长度增长是有明确数学规律的。一旦你抓住了这个规律问题就会变得非常简单。我现在做这类题的时候会先问自己三个问题第一这个字符串的长度增长有规律吗第二能不能用公式直接算出每一段的长度第三能不能通过减法快速定位到目标段如果这三个问题的答案都是肯定的那么基本上就可以用数学定位法来解决。对于想要进一步提升的朋友我建议多去研究一下“无限序列”相关的题目。这类题目在各大竞赛中出现的频率很高而且变种很多。掌握了基本的分析框架之后你会发现很多看似复杂的题目其实内核都是一样的。另外如果你对字符串处理本身感兴趣可以进一步学习一下后缀自动机、后缀数组这些高级数据结构。虽然这道题用不到但在更复杂的字符串问题中这些工具会非常有用。不过那是另一个话题了以后有机会再展开聊。最后说一个我在实际编码中的小习惯每次写完一个函数我都会用几个极端的测试用例跑一遍比如 k 1、k 9、k 10、k 10^9 这些。这些用例往往能暴露出边界条件和溢出问题。这个习惯帮我省下了很多次罚时推荐大家也养成。