P10766

Link_Cut_Y · 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);

我真是分类讨论大师。