题解

思路推导

第一行内部相邻字符不同的数量是固定的。若从左到右构造第二行，新增费用只与当前第二行字符、上方字符和前一个第二行字符有关，因此可以把问题看成两层 DAG 上的定长路径费用。

令 $dp_{i,c}$ 为处理前 $i$ 列且第二行末字符为 $c$ 时的全部可达费用集合。朴素转移枚举前一字符和费用即可。关键性质是：从第二列开始，两个集合都能表示为常数个互不相邻的整数区间。转移只包含集合平移、两个集合求并和再加当前竖边及第一行横边费用，因此合并区间即可在线性时间维护。

保存每个前缀的两个区间集合后，从右向左判断剩余费用属于哪个前驱集合，即可恢复一条路径和第二行。

做法

子任务 1 枚举全部 $2^n$ 个第二行字符串并直接计算费用。

子任务 2 用布尔数组维护 $dp_{i,c,k}$，时间复杂度 $O(nk)$，并保存全部前缀状态以恢复答案。

满分算法把每个可达费用集合压缩为互不相邻区间，转移时平移并归并区间，再按集合包含关系逆推答案。

正确性证明

在第 $i$ 列选择字符 $c$ 时，新增加的费用恰为竖边 $[c\ne s_i]$、第一行横边 $[s_i\ne s_{i-1}]$ 和第二行横边 $[c\ne c']$。因此从两个前驱末字符集合平移后取并，精确得到所有且仅有的可达费用。

区间算法只把相交或相邻整数区间合并，不添加区间外整数，也不删除原集合整数，所以每次压缩前后表示的集合相同。归纳可知最终集合包含 $k$ 当且仅当存在合法第二行。

逆推时选择一个使扣除当前三类边费用后的剩余值仍属于前驱集合的字符。该选择由 DP 转移保证存在；重复到第一列便得到总费用恰为原 $k$ 的完整字符串。

复杂度分析

满分算法时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。