# 克隆缸：题解

## 解法比较

出题人解法分别讨论中心不修改和修改，将前后半段逐位配对。相同对的代价为零或二，不同对为一或二；先取每对较小字符并优先向零调整，再从右向左维护剩余修改数的两种奇偶候选，记录转移并还原字符串，最后比较两种中心选择。其依据是字典序首先由左侧差异决定，修补额外代价应优先放到靠右位置；两种奇偶状态区分能否消耗最后一单位代价。出题人实现各遍历均线性，时间、辅助空间为 $O(n)$ .

Codex（GPT-6）采用的实现保留逐位字典序贪心，用下文证明的剩余代价连续区间直接判定每个候选是否可完成，不再固定中心后维护奇偶候选。时间仍为 $O(n)$ ，除输入输出字符串外只需 $O(1)$ 空间。优势是可行性判断与证明更直接，且不需候选与回溯数组；这是同阶替代方案。

## 剩余部分是否可行

把位置 $i$ 与 $h+1+i$ 看作一对。若原字符相同，这一对的修改代价可以是 $0$ 或 $2$ ；若原字符不同，代价可以是 $1$ 或 $2$ .四种字符保证不同字符对总能选到第三种字符，使代价为 $2$ .中间位置的代价可以是 $0$ 或 $1$ .

若尚未决定的部分有 $e$ 对相同字符、$d$ 对不同字符，以及中心位置，那么所有可实现的修改次数恰好为

$$[d,\ 2(e+d)+1]$$

证明：先给每个不同字符对分配最小代价 $1$ .这些对还能各增加 $1$ ，中心还能增加 $1$ ，合起来可增加 $0$ 到 $d+1$ .每个相同字符对还能增加 $0$ 或 $2$ .因为前一段至少有两个连续整数，把它平移 $0,2,4,\ldots,2e$ 后，各段相接或重叠，恰好覆盖上述完整区间。

## 逐位贪心

先统计所有不同字符对的数量。若它大于 $m$ ，无解；其余情况下有解。

从左到右决定前半段。决定第 $i$ 对之前，从剩余计数中移除这一对。依次尝试字符 `0` 、`1` 、`2` 、`3` ，计算把这一对都改成该字符的代价 $c$ .若剩余预算 $m-c$ 落在未决定部分的可行区间内，就选择这个字符，并扣掉 $c$ .

前半段决定之后，剩余预算只能为 $0$ 或 $1$ .为 $0$ 时保留中心字符；为 $1$ 时选择与原字符不同的最小字符。右半段已由前半段确定。

## 正确性与复杂度

可行区间的结论精确判断一个候选字符是否能扩展为合法结果。每一步选择最小且仍可完成的字符，因此任何字典序更小的字符串都必然在第一个不同位置选择了不可行的字符。中心也按同样原则取最小值，故最终结果是字典序最小的合法字符串。

每一对至多尝试四个字符，时间为 $O(n)$ ，所有询问总时间 $O(\sum n)$ .程序直接在输入字符串内写入结果，除字符串外只用 $O(1)$ 额外空间，峰值空间 $O(\max n)$ .