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 翻译