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

keatsli · 2024-11-30 22:03:32 · 题解

考虑代数化：所求即为 n-\sum\limits_{i=1}^n(s_{1,i}-s_{2,i})^2=n-\sum\limits_{i=1}^n s_{1,i}^2-\sum\limits_{i=1}^n s_{2,i}^2+2\sum\limits_{i=1}^n s_{1,i}s_{2,i}。

前三项是定值，故考虑最大化最后一项。

将 s 按是否可以交换分段，对 s 的限制即变为了若干个三元组 (l_{i,j},r_{i,j},d_{i,j}) 表示 s_i 中 [l_{i,j},r_{i,j}] 中有 d_{i,j} 个 1（因为可以交换，所以只关心连续一段的数量）。

于是可以直接双指针扫一遍 s_2 中的段，从前往后贪心地取 s_1 中的段中的 1，因为是从前往后取，故一定不劣（即放弃一个 1\to 1 对最多在未来增加一个 1\to 1 对）。