题解 CF1705D【Mark and Lightbulbs】

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,都是同样的。

代码

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);
}