AT_arc132_d.[ARC132D] Between Two Binary Strings

我们将一个字符串的美丽度定义为该字符串中相邻且相同的 $2$ 个字符的位置数。例如，00011 的美丽度为 $3$，10101 的美丽度为 $0$。

记 $S_{n,m}$ 为由 $n$ 个字符 0 和 $m$ 个字符 1 组成的、长度为 $n+m$ 的所有字符串的集合。

对于 $s_1, s_2 \in S_{n,m}$，定义 $s_1$ 和 $s_2$ 的距离 $d(s_1, s_2)$ 为：将字符串 $s_1$ 通过若干次相邻两个字符交换操作变换为字符串 $s_2$ 所需的最小操作次数。

此外，对于 $s_1, s_2, s_3 \in S_{n,m}$，若满足 $d(s_1, s_3) = d(s_1, s_2) + d(s_2, s_3)$，则称 $s_2$ 在 $s_1$ 和 $s_3$ 之间。

给定 $s, t \in S_{n,m}$，请输出在 $s$ 和 $t$ 之间的字符串的美丽度的最大值。

输入从标准输入中按以下格式给出。

$n$ $m$ $s$ $t$

请输出在 $s$ 和 $t$ 之间的字符串的美丽度的最大值。

限制条件

• $2 \leq n + m \leq 3 \times 10^5$
• $0 \leq n, m$
• $s, t$ 是由 $n$ 个 0 和 $m$ 个 1 组成的、长度为 $n+m$ 的字符串

样例解释 1

10110 和 01101 的距离为 $2$，它们之间的字符串有：10110、01110、01101、10101。它们的美丽度分别为 $1, 2, 1, 0$，因此答案为 $2$。

样例解释 2

000011 和 110000 的距离为 $8$。美丽度最大的字符串是 000011 和 110000，答案为 $4$。

由 ChatGPT 4.1 翻译