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

考虑代数化：所求即为 $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$ 对）。