自动搬运

查看原文

来自洛谷，原作者为

	Link_Cut_Y 菜就多练

搬运于2025-08-24 23:01:01，当前版本为作者最后更新于2024-07-13 21:23:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么会有这么蠢的紫题。

首先挖掘一下题目的性质。首先一个比较典的就是，翻转区间之间互不相交，覆盖区间之间互不相交。另外比较难观察的是，所有覆盖都可以在翻转后再进行，他们可以在相同步数内得到相同结果。

为什么是这样呢？假设覆盖的区间包含在翻转的区间内，假设先翻转，再覆盖成 $0$，显然我也可以用先覆盖成 $1$，在翻转来完成，他们有同样的效果。对于相交的情况也是一样的。

所以我们考虑，将原序列先全用覆盖操作，变成形如若干段与 $t$ 串相反和与 $t$ 串相同的串交替拼接的串。比如如果 $t = \{0, 0, 0, \cdots , 0\}$，可以先用覆盖把 $s$ 变成 $\{0, 0, 0, \cdots , 0, 1, 1, 1, \cdots, 0, 0, 0, \cdots\}$ 的形式，再用翻转操作，把 $1$ 都变成 $0$。当然这个例子举的不好。

由于翻转可以全在覆盖后做，我们不妨设 $f_{i, j, k}$，其中 $i \le n, j \in \{0, 1\}, k \in \{0, 1, 2\}$，表示已经考虑完了前 $i$ 个序列的覆盖操作，第 $i$ 个数和 $t_i$ 相同 $0$ 或相反 $1$，第 $i$ 个数被 $0$ 覆盖还是被 $1$ 覆盖还是没被覆盖 $2$。

分类讨论进行转移，这里的分类讨论就不细说了，大概就是如果 $i$ 被覆盖了，$j$ 也可以顺便接着覆盖而不需要代价，如果 $i$ 和 $t_i$ 相同而想让 $i + 1$ 和 $t_{i + 1}$ 相反就需要额外话翻转的代价等等。代码贴一下给大家参考吧，虽然考场上匆忙实现的有点丑。

read(n);
scanf("%s", s + 1);
scanf("%s", t + 1);
memset(f, 0x3f, sizeof f);
f[0][0][2] = 0;
rop(i, 0, n) {
	if (s[i + 1] == t[i + 1]) {
		if (s[i + 1] == '0') {
			chkmin(f[i + 1][0][0], f[i][0][0]);
			rep(j, 0, 2) chkmin(f[i + 1][0][2], f[i][0][j]);
			chkmin(f[i + 1][0][0], f[i][1][0]);
			rep(j, 0, 2) chkmin(f[i + 1][0][2], f[i][1][j]);
			chkmin(f[i + 1][1][1], f[i][1][1]);
			chkmin(f[i + 1][1][1], f[i][1][0] + 1);
			chkmin(f[i + 1][1][1], f[i][1][2] + 1);
			chkmin(f[i + 1][1][1], f[i][0][1] + 1);
			chkmin(f[i + 1][1][1], f[i][0][0] + 2);
			chkmin(f[i + 1][1][1], f[i][0][2] + 2);
		} else if (s[i + 1] == '1') {
			chkmin(f[i + 1][0][1], f[i][0][1]);
			rep(j, 0, 2) chkmin(f[i + 1][0][2], f[i][0][j]);
			chkmin(f[i + 1][0][1], f[i][1][1]);
			rep(j, 0, 2) chkmin(f[i + 1][0][2], f[i][1][j]);
			chkmin(f[i + 1][1][0], f[i][1][0]);
			chkmin(f[i + 1][1][0], f[i][1][1] + 1);
			chkmin(f[i + 1][1][0], f[i][1][2] + 1);
			chkmin(f[i + 1][1][0], f[i][0][0] + 1);
			chkmin(f[i + 1][1][0], f[i][0][1] + 2);
			chkmin(f[i + 1][1][0], f[i][0][2] + 2);
		}
	} else {
		if (s[i + 1] == '0') {
			chkmin(f[i + 1][1][0], f[i][1][0]);
			rep(j, 0, 2) chkmin(f[i + 1][1][2], f[i][1][j]);
			chkmin(f[i + 1][1][0], f[i][0][0] + 1);
			rep(j, 0, 2) chkmin(f[i + 1][1][2], f[i][0][j] + 1);
			chkmin(f[i + 1][0][1], f[i][1][1]);
			chkmin(f[i + 1][0][1], f[i][1][0] + 1);
			chkmin(f[i + 1][0][1], f[i][1][2] + 1);
			chkmin(f[i + 1][0][1], f[i][0][1]);
			chkmin(f[i + 1][0][1], f[i][0][0] + 1);
			chkmin(f[i + 1][0][1], f[i][0][2] + 1);
		} else if (s[i + 1] == '1') {
			chkmin(f[i + 1][1][1], f[i][1][1]);
			rep(j, 0, 2) chkmin(f[i + 1][1][2], f[i][1][j]);
			chkmin(f[i + 1][1][1], f[i][0][1] + 1);
			rep(j, 0, 2) chkmin(f[i + 1][1][2], f[i][0][j] + 1);
			chkmin(f[i + 1][0][0], f[i][1][0]);
			chkmin(f[i + 1][0][0], f[i][1][1] + 1);
			chkmin(f[i + 1][0][0], f[i][1][2] + 1);
			chkmin(f[i + 1][0][0], f[i][0][0]);
			chkmin(f[i + 1][0][0], f[i][0][1] + 1);
			chkmin(f[i + 1][0][0], f[i][0][2] + 1);
		}
	}
} 
int ans = 0x3f3f3f3f;
rep(j, 0, 1) rep(k, 0, 2) chkmin(ans, f[n][j][k]);
printf("%lld\n", ans);

我真是分类讨论大师。