rt

思路：

$i$ 从 $1$ 到 $n$ 扫一遍，维护 $a$，$b$ 两个串中 $i$ 所在的连通块中剩余的 $0$ 和 $1$ 的个数（$s_{1,0/1}$ 表示 $a$ 串中剩余的 $0/1$，$s_{2,0/1}$ 表示 $b$ 串，同理），然后分四种情况：

• $c_i = d_i = 0$，若 $a_i = b_i$，答案加一；
• $c_i = 0, d_i = 1$，若 $s_{2,a_i}\ge 1$，答案加一，$s_{2,a_i}$ 减一，否则，$s_{2,1-a_i}$ 减一；
• $c_i = 1, d_i = 0$，与第二种情况类似；
• $c_i = d_i = 1$
  • 若 $s_{1,0}\ge 1,s_{2,0}\ge 1$ 答案加一，$s_{1,0},s_{2,0}$ 各减一；
  • 否则，若 $s_{1,1}\ge 1, s_{2,1}\ge 1$，答案加一，$s_{1,0},s_{2,0}$ 各减一；
  • 若以上两条都不满足，说明目前只能出两个不能抵消的数字，若 $s_{1,0}\ge 1$，则 $s_{1,0}$ 减一，否则 $s_{1,1}$ 减一，$s_2$ 同理。
• 另外，$c_i$ 或 $d_i$ 等于 $0$ 时，更新 $s$。

（“抵消”指能通过移动使得 $a_i=b_i$，下同）

个人拙见：

我个人认为这个做法很正确，每个数字只要能抵消就是最优的，与抵消的位置无关，所以让每个数字在前面抵消。

这个结论个人认为可以证明上述贪心做法。

对一些问题的思考

Q：若 $i$ 处可以抵消，但将 $i$ 处的两数拆开，能让后面原本不能抵消的位置抵消，如何选择最优？

A：显然，交换后答案不变。

Q：若某处既可以填两个 $0$，也可以填两个 $1$，如何选择最优？

A：选哪个对答案没有影响，可以转换成第一个问题思考。