题解：P11361 [NOIP2024] 编辑字符串

llamn · 2024-11-30 18:41:58 · 题解

本题没那么难。

注意到题面中提到，相邻的字符才能交换，所以不能交换的字符会把字符串分割。我们这样把字符串分割，用前缀和分别记录每段中 0 和 1 的数量，并记录每一个位置属于第几段。

然后，一一比较每一个对应字符。
如果 t_{1,i} = t_{2,i} = 0 直接比较计算答案。
如果 t_{1,i} \neq t_{2,i} 的话，让能交换的那个字符优先把对应字符换到 i 处。这样做正确的原因是：如果有字符不换到 i 处，那么那个字符在另一个地方的贡献最大为 1，和在 i 时产生的贡献是相同的。
最后再用剩下的字符处理剩下的 t_{1,i} = t_{2,i} = 1 的位置。