# 再来一小段题解

## 解法比较

完整构造与按需输出是并列方案：完整构造减少递归与查找开销，按需输出避免保存最大字符串。标程采用按需输出。

出题人解法先读入所有询问，求出最大版本，逐次把当前串的指定前缀复制到尾部，实际构造最大版本。各版本互为前缀，所以每次询问只需输出这个大串相应长度的前缀。设最大版本号为 $V$ 、最大串长为 $L_{max}$ 、询问数为 $Q$ 、输出总字符数为 $C$ ，时间为 $O(V+Q+L_{max}+C)$ ，空间为 $O(L_{max}+V+Q)$ .

Codex（GPT-6）采用的实现只保存初串和各版本长度，按拼接关系递归输出所需前缀；这种分解与完整构造中的实际复制完全等价。额外空间降为 $O(V+|s_1|)$ ，适合本题内存限制；时间上界为 $O(V+(C+Q)\log(V+1))$ .代价是递归和查找版本的开销，输出的 $C$ 个字符仍然必须逐个写出，按需输出的优势在于空间。

## 先算长度

记 $L_k=|s_k|$ ，则

$$L_1=|s_1|,\qquad L_k=L_{k-1}+\left\lceil L_{k-1}/5\right\rceil$$

用整数运算 `(L + 4) / 5` 实现向上取整。长度严格递增，而且每个版本都是后续版本的前缀。只需保存 70 个长度和最初的字符串。

## 按前缀递归输出

定义 `PrintPrefix(t)` ：输出任意一个长度至少为 $t$ 的版本的前 $t$ 个字符。由于较短的版本总是较长版本的前缀，选择哪个足够长的版本都不会影响结果。

- 若 $t\le L_1$ ，直接输出 $s_1$ 的前 $t$ 个字符。
- 否则二分找到最小的 $k$ ，使 $L_k\ge t$ ，此时有 $L_{k-1}<t$ . 所求前缀由完整的 $s_{k-1}$ 和其前 $t-L_{k-1}$ 个字符组成。先递归输出长度为 $L_{k-1}$ 的前缀，再递归输出长度为 $t-L_{k-1}$ 的前缀。

回答询问 $x$ 时，递归输出长度为 $L_x$ 的前缀，随后输出换行。写出的字符直接进入输出流，不在内存中保存完整的大字符串。标程的 `Lengths` 数组从下标 $0$ 开始，因此版本 $x$ 的长度存储在 `Lengths[x - 1]` 中。

## 正确性

初始字符串的前缀显然正确。对 $t>L_1$ ，选出的最小版本 $k$ 满足 $L_{k-1}<t\le L_k$ . 根据定义，$s_k$ 的前 $L_{k-1}$ 个字符恰好是 $s_{k-1}$ ，余下部分是 $s_{k-1}$ 的前缀。两次递归的长度均小于 $t$ ，由归纳假设输出正确，拼接后就是要求的前缀。因此每次询问都输出正确的版本。

## 复杂度与内存

设最大版本编号为 $V=70$ ，所有询问的输出字符总数为 $C$（Characters，不含换行）。每次非叶递归都拆成两个非空部分，因此递归调用总数为 $O(C+Q)$ ；每次二分花费 $O(\log V)$ . 总时间为 $O(V+(C+Q)\log V)$ ，额外空间为 $O(V+|s_1|)$ ，另有标准输出流的缓冲区。

递归中的版本编号严格下降，深度至多 $V$ . 这种输出方式无需存储数百万字符，适合本题的 8 MB 内存限制。