专栏文章

题解：AT_agc052_e [AGC052E] 3 Letters

ddrmr
AT_agc052_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqeu7gl
此快照首次捕获于
2025/12/04 03:38
3 个月前
此快照最后确认于
2025/12/04 03:38
3 个月前
查看原文
题意：给定两个长度为 NN 的字符串 S,TS, T，字符集 U={A,B,C}U = \{A, B, C\}。现在一次操作可以选择 1≤i≤N1 \le i \le N 和 K∈UK \in U，使 Si←KS_i \leftarrow K，且 Si−1≠K,Si+1≠KS_{i-1} \ne K, S_{i +1} \ne K。求把 SS 变为 TT 的最小步骤数，可以证明一定有解。
设整数数列 ss，使得 ∀1≤i≤N\forall 1 \le i \le N，sis_i 和 SiS_i 对于 33 同余，同理定义整数数列 tt。我们一定可以构造出一组 ss 使得 ∀1≤i<N\forall 1 \le i < N，有 ∣si−si+1∣=1|s_i - s_{i+1}| = 1。也同理约束 tt。
我们发现，若操作 ii，则 Si−1=Si+1S_{i-1} = S_{i+1}，此时 si−1=si+1=si±1s_{i-1} = s_{i+1} = s_i \pm 1。操作可以使 si←si±2s_i \leftarrow s_i \pm 2，操作后仍然满足相邻两数绝对值为 11 的限制。
通过贪心的证明，我们容易证明 ∑i∈[1,N]∣si−ti∣2\frac{\sum_{i \in [1, N]} |s_i - t_i|}{2} 是操作次数的下界。我们考虑最小化该值。
这个问题十分简单，如图，蓝线和橙线分别代表 ss 和 tt，那么当我们将蓝线向上移动时，si≥tis_i \ge t_i 的部分会将贡献加一，否则则会减一，因此 si≥tis_i \ge t_i 和 si<tis_i < t_i 的 ii 的数量越接近，答案越小，这等价于将两者的中位数对齐。然而，我们只能将 tt 整体加 33 的倍数，且需要保证 sis_i 和 tit_i 奇偶性相同，需要注意实现细节。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...