奇怪题

· · 题解

首先，方便起见，我们以 2,0,1 代替 A,B,C（方便直接 ASCII 取模）。接下来，我们试图为一个好串 S 找到一个长为 n 的序列刻画方式，其中 n 是 S 的长度。

我们意识到，相邻字母只要不同，转换为数值后模 3 之差一定是 1 或 -1，那么我们不妨对序列 A 给出如下约束：

我们把这样的序列称作“好序列”。不难发现，固定 S 与 A_1 后，好序列是唯一的。但注意 A_1 不固定时好序列不是唯一的，且所有这些不唯一的好序列都能对应到同一个 S 上。

我们注意到，对于 S 中相邻的三个字母，如果它们两两不同，那么中间那个字母是一定无法变化的（不然变完一定失去好串性质）。那么为了变化中间的字母，两端的字母一定要相同（也就是得是类似于 010 的形式）。这样一来，在 A 序列中，两端的数值一定是相同的，而中间的数值在变化前后分别是两端的数值加一或减一（也就是 x,x+1,x 变成 x,x-1,x 或反之）。如此一来，我们发现，在序列维持是好序列的前提下，单个元素单次变化的绝对值一定是 |1-(-1)|=2。以上讨论没有专门分变化位置在边界的类，但其实是一样的。

回到原问题。我们不妨考虑我们已经确定了 S，T 对应出的好序列 A，B。由于两个好序列可以同步平移，我们事实上可以不妨直接定下 A。注意到我们每一次操作并不会改变元素的奇偶性，所以必须满足 A 与 B 每个对应位置的奇偶性都相同。考虑到 A 的相邻位置一定有奇偶变化（B 同理），实际上只需要做到 A_1 与 B_1 奇偶性相同。

接下来我们考虑至少要多少步能把 A，B 变成同一个序列（事实上由于变化是可逆的，具体变成什么样其实我们并不关心）。容易发现，答案的下界是 \frac 1 2\sum_{i=1}^{n}|A_i-B_i|，考虑到我们最优情况下每一步也只能让它减少一。而我们猜测答案就是这个值，那我们断言存在一种策略能保证每一步都能让它减少一。换句话说，每一步一定会找到一个 A_i\gt B_i 的位置并把 A_i 减二，或是一个 A_i\lt B_i 的位置把 B_i 减二。这两者没有区别。

由于 A 和 B 还不完全相同，我们不妨存在位置使得 A_i\gt B_i（反之一定存在位置使得 A_i\lt B_i，完全同理即可）。我们找到所有这样的位置中 A_i 最大的那一个，试图证明 A_{i-1} 和 A_{i+1}（均若存在）一定都等于 A_i-1。反之，不妨 A_{i-1}=A_i+1，注意到 B_{i-1}\le B_i+1\lt A_i+1=A_{i-1}，那么 i-1 也是一个符合条件的位置，与 A_i 的最大性矛盾！

如此一来，我们只要确定了 A 和 B，答案便能通过 \frac 1 2\sum_{i=1}^{n}|A_i-B_i| 快速计算。实际上，A 是确定的，B_i-B_1 是确定的，我们不妨记 B_1=x，那么 x 只需要满足 x\equiv A_1(\bmod\ 2) 且 x\equiv T_1(\bmod\ 3) 即可。再设 x=6y+k（其中 k 是由以上两个约束计算得出的常数），A_i-B_i+B_1-k=C_i，那么答案实际上便化为了 \frac 1 2\sum_{i=1}^{n}|C_i-6y|。注意到此时 y 已经是一个完全自由的变元，枚举 6y 在 C 中位数两端计算答案取 \min 即可。

在代码中，下标从 0 开始，且计算的 b 数组实际上是 B_i-B_1+k，注意不要混淆。另外注意到 C++ 除号在被除数是负数的时候取整可能不能如我们所愿，所以简单一点就中间+两边三项取 \min 就不会有问题了（这部分可以参考代码理解）。

#include <bits/stdc++.h>
using namespace std;
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  string s, t;
  cin >> n >> s >> t;
  vector<int> a(n), b(n), c(n);
  a[0] = s[0] % 3, b[0] = t[0] % 3;
  if ((a[0] ^ b[0]) & 1) b[0] += 3;
  for (int i = 1; i < n; ++i) {
    a[i] = a[i - 1] + 1, b[i] = b[i - 1] + 1;
    if ((s[i] - a[i]) % 3) a[i] -= 2;
    if ((t[i] - b[i]) % 3) b[i] -= 2;
  }
  for (int i = 0; i < n; ++i) c[i] = a[i] - b[i];
  nth_element(c.begin(), c.begin() + (n >> 1), c.end());
  auto calc = [&](int x) {
    long long ret = 0;
    for (int i = 0; i < n; ++i) ret += abs(c[i] - x);
    return ret;
  };
  int w = c[n >> 1] / 6 * 6;
  return cout << (min({calc(w), calc(w - 6), calc(w + 6)}) >> 1) << endl, 0;
}