好思路（CF1615F）

__S08577__ · 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 使两字符串相同所需要的最小步数。