P11361 [NOIP2024] 编辑字符串

思路讲解

要多写，如果实在没有思路就数学化。

参考思路如下。

不难发现，我们要最小化下面👇。

$\sum_{i=1}^{n}(s[i]-s'[i])^2 \Rightarrow \sum_{i=1}^{n}s[i]^2+s'[i]^2-2s[i]s'[i]$

常数分离以后，我们其实就是要最大化👇。

相当于我们要最大化 $\sum_{i=1}^{n}s[i]s'[i]$ 。不过我们发现好像没什么用？非常有用，我们就知道了，1 1 非常重要，要尽量多的出现1 1，其他不重要。

当然，如果光有这个想法是不行的。我们还需要用到分块思想。

首先那，分块，我们自然是同时只能按照一个字符串分块的，因此我们按照 $s$ 可不可以交换分块。

但是，我们按照 $s$ 分块以后，我们可以再对 $s'$ 进行分块。这个听起来很抽象是吧？其实也简单，就是说 $s’$ 其实如果不是落在整段 $s$ 可交换块上，可以部分落在 s 的可交换块上，然后我们的策略其实就是尽量多的出现1 1。

源代码