题意

给定两个长度为 $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);
}