本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-17 19:36:18

题面

对于两个长度为 $n$ 的 $01$ 串 $s,t$ ，你可以对 $s$ 进行两种操作：把相邻两个 $0$ 变成 $1$ 或把相邻两个 $1$ 变成 $0$ ，定义 $s$ 到 $t$ 的距离为最少操作次数使得 $s$ 变成 $t$ ，如过没法变则距离为 $0$ 。

现在你有两个不完整的字符串，可以把其中的 $?$ 变成 $0$ 或 $1$ ，求所有情况所得到的两个 $01$ 串的距离之和。

思路

我们发现，直接按照题意操作是非常复杂且不雅的。有一个十分新奇的思路（难绷）：将s和t的奇数位取反。

设 $s=100111011000$，$t=111100011011$，则最少操作步数为3次，（2,3/5,6/11,12)，我们将奇数位取反后发现，$s'=001101110010$，$t'=010110110001$。此时，我们便发现，原问题转化为有两01串，我们可以将 $01$ 转成 $10$ 或将 $10$ 转成 $01$ 使两字符串相同所需要的最小步数。