题解：AT_agc052_e [AGC052E] 3 Letters

· · 题解

题意：给定两个长度为 N 的字符串 S, T，字符集 U = \{A, B, C\}。现在一次操作可以选择 1 \le i \le N 和 K \in U，使 S_i \leftarrow K，且 S_{i-1} \ne K, S_{i +1} \ne K。求把 S 变为 T 的最小步骤数，可以证明一定有解。

设整数数列 s，使得 \forall 1 \le i \le N，s_i 和 S_i 对于 3 同余，同理定义整数数列 t。我们一定可以构造出一组 s 使得 \forall 1 \le i < N，有 |s_i - s_{i+1}| = 1。也同理约束 t。

我们发现，若操作 i，则 S_{i-1} = S_{i+1}，此时 s_{i-1} = s_{i+1} = s_i \pm 1。操作可以使 s_i \leftarrow s_i \pm 2，操作后仍然满足相邻两数绝对值为 1 的限制。

通过贪心的证明，我们容易证明 \frac{\sum_{i \in [1, N]} |s_i - t_i|}{2} 是操作次数的下界。我们考虑最小化该值。

这个问题十分简单，如图，蓝线和橙线分别代表 s 和 t，那么当我们将蓝线向上移动时，s_i \ge t_i 的部分会将贡献加一，否则则会减一，因此 s_i \ge t_i 和 s_i < t_i 的 i 的数量越接近，答案越小，这等价于将两者的中位数对齐。然而，我们只能将 t 整体加 3 的倍数，且需要保证 s_i 和 t_i 奇偶性相同，需要注意实现细节。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5;
int n, a[N], b[N], c[100][100], d, ans, p[N], q[N];
string s, t;

signed main(){
    cin >> n >> s >> t, s = "@" + s, t = "@" + t;

    c['A']['B'] = 1, c['A']['C'] = -1;
    c['B']['C'] = 1, c['B']['A'] = -1;
    c['C']['A'] = 1, c['C']['B'] = -1;

    a[1] = s[1] % 3;
    for(int i = 2; i <= n; i++)
        a[i] = a[i - 1] + c[s[i - 1]][s[i]];
    b[1] = t[1] % 3;
    for(int i = 2; i <= n; i++)
        b[i] = b[i - 1] + c[t[i - 1]][t[i]];

    for(int i = 1; i <= n; i++) p[i] = q[i] = i;
    sort(p + 1, p + 1 + n, [](int x, int y){return a[x] < a[y];});
    sort(q + 1, q + 1 + n, [](int x, int y){return b[x] < b[y];});

    int d = a[p[(n + 1) / 2]] - b[q[(n + 1) / 2]], mn = 1e18;
    for(int e = d / 3 * 3 - 18; e <= d / 3 * 3 + 18; e += 3){
        if(((b[1] + e) ^ a[1]) & 1) continue;
        ans = 0;
        for(int i = 1; i <= n; i++)
            ans += abs(a[i] - b[i] - e);
        mn = min(mn, ans);
    }
    cout << mn / 2;
    return 0;
}