题意
给定两个长度为 $n$ 的 0-1 串 $s$ 和 $t$,每次操作可以:选择 $s$ 在 $[2, n-1]$ 区间内的一个字符,若 $s_{i-1} \not= s_{i+1}$ 则将 $s_i$ 取反。
问,能否通过一定次数的操作,把字符串 $s$ 转换成 $t$?如果能,求出最小操作次数。
分析
性质观察题。
首先,由于每次操作仅能选择 $[2, n-1]$ 区间内的字符,所以若 $s$ 和 $t$ 的首尾字符不同,一定不可能。
然后考虑哪些位置可以进行操作。
- 由于能操作的位置需要满足 $s_{i-1} \not= s_{i+1}$,故对于任意一段连续的 0 或 1,只有其两端可以被进行操作(因为中间部分不能满足上述条件)。
- 特殊地,若两段连续的 1 之间,仅有一个 0 隔开,这个孤立存在的 0 也是不能被操作的。
接着考虑操作之后会对 $s$ 串造成什么变化?
- 由上述限制 1 得知,由于每次操作的都是端点,所以每段连续的 1 都可以在端点位置变成 0(缩短了),或者是对旁边 0 的端点进行操作,这相当于对 1 的延长。即:每次操作之后,一段连续的 0 或 1,会被压缩或者拉长。且:每次压缩或拉长的距离等于操作的次数。
- 由上述限制 2 无论如何操作,两段被分隔开的连续的 1,无论如何都不可能连接到一起。即:操作不会改变连续的 0 或 1 的串的数量。
至此,此题做法呼之欲出:
- 判断 $s$ 和 $t$ 的首尾字符是否相同;
- 判断 $s$ 和 $t$ 中连续的 1 的子串个数是否相同;
- 求出 $s$ 和 $t$ 中每段连续 1 的子串被压缩或拉长的距离总和,这个距离和就是最终答案。
时间复杂度 $\mathcal{O}(n)$。
当然,无论分析连续 0 还是连续 1,都是同样的。
代码
void solution() {
int n;
read(n);
std::string s, t;
std::cin >> s >> t;
if (s.front() != t.front()) return print(-1);
if (s.back() != t.back()) return print(-1);
s = " " + s;
t = " " + t;
std::vector<pii> segS, segT;
// 处理 s 串当中连续 1 的子串的首尾坐标
for (int i = 1; i <= n; ++i) {
if (s[i] == '0') continue;
int j = i;
while (j + 1 <= n && s[j + 1] == '1') ++j;
segS.emplace_back(i, j);
i = j;
}
// 处理 t 串当中连续 1 的子串的首尾坐标
for (int i = 1; i <= n; ++i) {
if (t[i] == '0') continue;
int j = i;
while (j + 1 <= n && t[j + 1] == '1') ++j;
segT.emplace_back(i, j);
i = j;
}
if (segT.size() != segS.size()) return print(-1);
ll ans = 0;
int m = int(segS.size());
// 对压缩或伸长的总距离求和,就是最终答案
for (int i = 0; i < m; ++i) ans += std::abs(segS[i].first - segT[i].first);
for (int i = 0; i < m; ++i) ans += std::abs(segS[i].second - segT[i].second);
print(ans);
}