题解 CF1705D【Mark and Lightbulbs】
Anguei
2022-07-18 14:55:04
## 题意
给定两个长度为 $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$ 的首尾字符不同，一定不可能。
然后考虑哪些位置可以进行操作。
1. 由于能操作的位置需要满足 $s_{i-1} \not= s_{i+1}$，故对于任意一段连续的 0 或 1，只有其两端可以被进行操作（因为中间部分不能满足上述条件）。
2. 特殊地，若两段连续的 1 之间，仅有一个 0 隔开，这个孤立存在的 0 也是不能被操作的。
接着考虑操作之后会对 $s$ 串造成什么变化？
1. 由上述限制 1 得知，由于每次操作的都是端点，所以每段连续的 1 都可以在端点位置变成 0（缩短了），或者是对旁边 0 的端点进行操作，这相当于对 1 的延长。即：**每次操作之后，一段连续的 0 或 1，会被压缩或者拉长**。且：**每次压缩或拉长的距离等于操作的次数**。
2. 由上述限制 2 无论如何操作，两段被分隔开的连续的 1，无论如何都不可能连接到一起。即：**操作不会改变连续的 0 或 1 的串的数量**。
至此，此题做法呼之欲出：
1. 判断 $s$ 和 $t$ 的首尾字符是否相同；
2. 判断 $s$ 和 $t$ 中连续的 1 的子串个数是否相同；
3. 求出 $s$ 和 $t$ 中每段连续 1 的子串被压缩或拉长的距离总和，这个距离和就是最终答案。
时间复杂度 $\mathcal{O}(n)$。
当然，无论分析连续 0 还是连续 1，都是同样的。
## 代码
```cpp
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);
}
```