20260228：AtCoder Beginner Contest 447

百会（bestWit）| 百炼成钢，融会贯通，助力GESP备考

哈喽，备战GESP的同学们～ 百会（bestwit）AtCoder题解来啦！每周1次更新，聚焦竞赛高频题型，贴合GESP入门难度，帮大家拆解解题思路、掌握解题技巧，夯实编程基础，为GESP考试做好准备。

题目

题目编号：C ：Insert and Erase A  题目难度：★★★☆☆（贴合GESP 4-5级难度） 题目链接：C - Insert and Erase A

题目大意

由大写英文字母组成的字符串 S、T。你可以按照任意顺序执行以下 2 种操作任意次数（也可以执行 0 次）：

・在 S 的任意位置（包括开头和末尾）插入 1 个字符 A。

・选择 S 中包含的 1 个字符 A 并删除。删除后剩余的字符保持原有顺序。 请判断是否能将 S 变为 T；如果可以，求出所需操作次数总和的最小值。

限制条件：

• S、T 是由大写英文字母组成的字符串
• 长度为 1 以上、3×10⁵ 以下

输入输出

输入为如下格式：

S
T

输出为如下格式：

如果能将 S 变为 T，输出所需操作次数总和的最小值；

如果不能，输出 -1

输入样例：

ABC
BACA

输出样例：

3

解释：可以通过以下总计 3 次操作将 S 变为 T：

・在 S 的第 2 个字符和第 3 个字符之间插入 1 个 A，此时 S = ABAC。

・删除 S 中第 1 个字符的 A，此时 S = BAC。

・在 S 的末尾插入 1 个 A，此时 S = BACA。由于无法通过 2 次及以下操作将 S 变为 T，因此答案是 3。

解题思路

本题要求通过插入 A或删除 A两种操作，判断能否将字符串 S 转为 T，并求出最小操作次数。

关键结论：

• 非 A 字符无法被修改 / 插入 / 删除，因此若 S 和 T 剔除所有 A 后得到的字符串不一致，直接返回 - 1；
• 若剔除 A 后的字符串一致，只需计算 S 和 T 中 “非 A 字符分割出的各段 A 的数量差”，累加所有差值的绝对值即为最小操作次数（插入 / 删除 1 个 A 均计 1 次操作）。

代码

#include <bits/stdc++.h>

using namespace std;

string s,t,s1,t1;
int ans;
vector <int> c1,c2;

int main(){
    cin >> s >> t;

	//生成两个新的字符串(剔除原字符串中的所有A)
	//同时记录连续的每一段A的个数 ，保存在动态数组中 
	int tmp = 0;
	for (int i = 0;i < s.length();i++){
		//如果是A，记录A的连续个数 
		if (s[i] == 'A') tmp++;
		else {
			s1 += s[i]; //把非A的字符放到新的字符串中去
		    c1.push_back(tmp);
		    tmp = 0; //归零，开始新一轮的计数
		}
	}
	//把最后一个连续的A的数字记录一下 
	c1.push_back(tmp);
	
	//同样的逻辑处理T字符串
	tmp = 0; 
	for (int i = 0;i < t.length();i++){
		//如果是A，记录A的连续个数 
		if (t[i] == 'A') tmp++;
		else {
			t1 += t[i]; //把非A的字符放到新的字符串中去
		    c2.push_back(tmp);
		    tmp = 0; //归零，开始新一轮的计数
		}
	}
	//把最后一个连续的A的数字记录一下 
	c2.push_back(tmp);
	
	//S1和T1如果不相等，则绝对不可能符合条件 
	if (s1 != t1){
		cout << -1 << "\n";
		return 0;
	}
	
	//由于S1和T1相等，也就是说S和T数组被同样的非A字符给隔开了 
	//那么连个数组C1，C2的 长度必然相等
	for (int i = 0;i < c1.size();i++){
		ans += abs(c1[i] - c2[i]);
	}
 
	cout << ans;
}

总结

解题核心：剥离 A 的干扰，先通过剔除 A 后的字符串判断可行性，再统计各段 A 的数量差求最小操作次数；

• 关键逻辑：非 A 字符是 “锚点”，其顺序和内容必须完全一致，仅需调整锚点间 / 首尾的 A 数量；
• 代码亮点：通过一次遍历同时完成 “非 A 字符提取” 和 “A 段数量统计”，时间复杂度为 O (|S|+|T|)，符合题目时间限制要求。

最后，祝大家在后续的AtCoder比赛中，顺利AC每一道C题，稳步提升！后续我们会逐步更新难度更高的题解，贴合GESP进阶考点，陪大家一起“百炼成钢”。

下期预告：AtCoder Beginner Contest 448，经典的 300 点模拟类题目，记得关注公众号，第一时间获取更新通知～