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

归档56

题解34 未分类7 游寄6 “你需要知道的一切”系列4 博客指南3 网络前端1 闲话1

464 字

2 分钟

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

2025-08-12

2026-10-27

浏览量加载中...

考场做法逆天，结果发现是正解……

卡卡常（其实也没怎么卡）直接最优解榜一（查看时间：2025/08/12 09<08>）

先说结论：令奇数位的 A 有 $X$ 个，偶数位的 A 有 $Y$ 个，那么如果 $\left| X - Y \right|$ 是奇数那么无解，否则答案是 $\dfrac{\left| X - Y \right|}{2}$ 。

为什么呢？其实证明也很简单。

首先我们发现题目只和字母 $A$ 相关，而且关键在于奇数位的 A 和偶数位的 A，于是我们分别对其计数。

然后我们考虑操作会产生什么影响。

每次可以选择交换两个位置相邻的字符。——题目

相邻的两个数显然是一奇一偶，而交换这两个只可能是奇数位换到偶数位（或偶数换到奇数位）。

这样就可以让奇数的数量减少一个，偶数增加一个（或者反过来）。

一个加一，另一个减一，它们的差当然是减少 $2$ 了。而且每次操作都会减少 $2$ ，因为必然是奇换偶或偶换奇。因此得到了上面的结论，证毕。

带注释 AC Code：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int a, b, n;  // a 是偶数位，b 是奇数位，n 是字符串长度
6
string s;
7

8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(0), cout.tie(0);
11
    cin >> s;
12
    n = s.size();
13
      for (int i = 0;i < n;++i) if (s[i] == 'A') {  // 注意到和 B 无关因此要判断
14
        if (i % 2) ++b;  // %2 余 0 就是 false，余 1 就是 true，正好分别对应偶数和奇数
15
        else ++a;
16
    }
17
    if ((abs(b - a)) % 2) cout << -1 << endl;  // 不知道谁大谁小，因此要取绝对值
18
    else cout << ((abs(b - a)) >> 1) << endl;  // 右移 1 位相当于除以 2，因为是非负数所以和 / 2 没有区别
19
    return 0;
20
}