Codeforces Global Round 18

C

C. Menorah
给定字符串 $a, b$，每一次可以选择字符串 $a$ 中的 $1$，并且令这一位 $1$ 保持不变
其他位反转，问最少需要经过多少次能够将 $a$ 变换到 $b$

这类置换问题，首先应该想到的是奇偶性
首先对于 $a, b$ 中原本就相同的部分，如果反转偶数次，相等的部分是不变的，那么问题就取决于
对不同的部分要操作多少次，是不是偶数次呢？
进一步，如果操作偶数次，除了 $1$ 这个操作位之外，并不会改变其他位置的值
如果 $a_i = 0, b_i = 0$，记存在一个 $(0, 0)$ 对，其他情况类似

先来看简单的情况，对不同的部分，如果有如下形式

$$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \longrightarrow \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$$

也就是说，一组
$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ 经过 $2$ 次变换，一定能够变成相同的，并且变换次数是偶数，它对 $a, b$ 其他位置的值没有影响
那么可以发现

如果 $a, b$ 不同的部分，能够分成相等的 $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ 组合

即 $(0, 1)$ 对和 $(1, 0)$ 对相等，那么答案一定是可以的
换句话说，记 $\text{diff}$ 为 $a, b$ 不同的位置个数，$\text{diffc}(0)$ 表示 $(a_i = 0, b_i = 1)$ 的位置个数
$\text{diffc}(1)$ 表示 $(a_i = 1, b_i = 0)$ 的位置个数
当且仅当 $\text{diff}$ 是偶数并且 $\text{diffc}(0) = \text{diffc}(1)$ 时，一定可以完成操作
此时最少的操作代价是 $\text{diff}$

否则的话，经过上面的操作，会有多出来的一位不同，我们需要用额外的 $\begin{pmatrix}1 \\ 1\end{pmatrix}$ 位来控制
让其反转，那么记 $\text{same}$ 为 $a, b$ 相同位置的个数，除了 $\begin{pmatrix}1 \\ 1\end{pmatrix}$ 这个控制位外
还有 $\text{same} - 1$ 个相同的位置
用控制位做一次反转操作，那么这 $\text{same}-1$ 个位置变成不同的数了，其他位置仍然相同
这就转换成偶数的情况，有解当且仅当 $\text{same} - 1$ 为偶数，并且这 $\text{same}-1$ 个数中
$(0, 0)$ 对的个数和 $(1, 1)$ 对的个数必须相同，用 $\text{cnt}(0)$ 记录 $(0, 0)$ 对，$\text{cnt}(1)$ 记录 $(1, 1)$
那么这种情况，必须有 $\text{same}$ 为奇数，并且 $\text{cnt}(1) - \text{cnt}(0) = 1$（多出来的这个 $1$ 作为控制位）
答案为 $\text{same} - 1 + 1$ 次操作