专栏文章

题解：B4377 [蓝桥杯青少年组省赛 2025] 平衡奇偶位置的字符交换

BBSHF_NOI_AU
B4377题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miodw1j4
此快照首次捕获于
2025/12/02 17:36
3 个月前
此快照最后确认于
2025/12/02 17:36
3 个月前
查看原文

前言

本蒟蒻在考场上这道题思考了20分钟才做了出来。

正文

这道题并非模拟题，而是找规律，我们先观察样例，
输入
MARKDOWN
AABABA
输出
MARKDOWN
1
因为奇数位置上的 A 的数量需要等于偶数位置上的 A 的数量。所以就需要将 A 的数量统计出来，再平分给奇数和偶数，如果A的数量是奇数，就代表平分不了，按照题目要求输出 −1-1 即可。
如果 A 的数量是偶数，就需要将 A 的总数平分，减去奇偶个数中较小的那个数，就是需要 A 和 B 交换的次数。即 (a+b)/2−min⁡(a,b)(a+b)/2-\min(a,b) 注：a 为奇数位置上的 A 的数量，b 为偶数位置上的 A 的数量。
如这个样例（自创）：
输入
MARKDOWN
AABABABABA
输出
MARKDOWN
2
A的数量为 66 个，奇数位上有 11 个，偶数位上有 55 个 ，故算式为 (5+1)/2−1=2(5+1)/2-1 = 2 。
操作：
  1. 交换位置 22 和 33 的字符（A 和 B）
  2. 交换位置 44 和 55 的字符（A 和 B）
此时奇数位上有 33 个 A，偶数位上有 33 个 A，故需交换两次。与计算结果相同。

Code：

CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
	string a;
	int sum = 0,cnt = 0; 
	cin>>a;
	int len = a.length();
	for(int i = 0;i<len;i++){//统计奇偶个数 
		if(a[i] == 'A'){
			if((i+1)%2 == 1){//+1是因为位置编号从 1 开始
				sum++;
			}else if((i+1)%2 == 0){
				cnt++;
			}
		}
	}
	if((sum+cnt)%2 == 1){//无法平分，输出-1 
		cout<<-1;
	}else{
		cout<<(sum+cnt)/2-min(sum,cnt);//先平分，再减去小的那个，就算是交换次数 
	}
	return 0;
}

评论

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

正在加载评论...