题解：CF1615F LEGOndary Grandmaster

2huk · 2024-08-09 19:53:48 · 题解

拜谢 @WA_QJ 大佬/bx/bx

题意

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

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

做法

第一次见这个 trick。第一个想出这个 trick 的人一定不是人。

首先考虑没有问号，直接求两个字符串的距离怎么做。

我们将 s, t 的所有奇数位上的数取反（\texttt0 变 \texttt1，\texttt1 变 \texttt0）。那么原来将 s 中的两个相邻且相同的位置取反，等价于现在将 s 中的两个相邻且不同的位置交换（即 s_i = \texttt0, s_{i+1}=\texttt1 或 s_{i}=\texttt1,s_{i+1}=\texttt0 时，交换 s_i, s_{i+1}）。

若新的 s, t 中 \texttt1 的数量不同，无解。

不难发现多次进行交换可以看作是一个 \texttt1 在很多 \texttt0 之间移动。例如对于 s = \texttt{0010}，那么先交换 s_2,s_3 再交换 s_1, s_2 得到的字符串 s' = \texttt{1000}，可以看作是 1 向左移动了两位。此时 \texttt1 的移动位数即操作次数。

那么我们想让 s 中的每个 \texttt1 都移动到某个位置，使得 s = t，且移动次数最小。这是简单贪心，不难得出若令 [i_1, i_2, \dots, i_m] 为 s 中的 \texttt1 的出现位置（已排序），[j_1, j_2, \dots, j_m] 为 t 中的 \texttt1 的出现位置（已排序），那么答案为 \sum_{k=1}^m |i_k - j_k|。

对于带 \texttt ? 的原题，我们考虑 DP。

设 f(i, j) 表示 s[1\dots i], t[1 \dots j] 的答案（即每个合法的 s, t 的距离和），且保证 s_i = t_j = \texttt1，g(i, j) 表示方案数。显然只有在 s_i \ne \texttt 0 且 t_i \ne \texttt 0 时 f(i, j), g(i, j) 才有意义。

转移枚举两个串分别的倒数第二个 \texttt1 的位置。

其中 p_i 表示 s 中 i 之前第一个 \texttt1 的位置，q_i 是 t 的。因为 i', j' 是倒数第二个 \texttt1，所以 [i'+1, i-1], [j'+1, j-1] 不能跨越任何一个 \texttt1。

这里 g(i, j) \times |i - j| 是拆贡献，表示 |i - j| 在 g(i, j) 个串中有用。

复杂度 \mathcal O(n^4)。二维前缀和优化转移即可做到 \mathcal O(n^2)。

代码去看这篇题解吧。