蓝桥杯备赛：Day7- U535982 C-小梦的AB交换

算法笔记U535982 C-小梦的AB交换1. 题目简述U535982 C-小梦的AB交换 - 洛谷输入一个长度为2 n 2n2n的A B ABAB串包含n nn个A AA和n nn个B BB。操作每次可以选择任意两个位置i , j i, ji,j交换字符。目标最少操作几次使得字符串变为交替排列即相邻字符不同。输出最小交换次数。2. 核心代码 (C 实现)#includebits/stdc.h using namespace std; typedef long long ll; void solve() { int T; if(!(cin T)) return; // 读入测试组数 while(T--) { ll n; cin n; string s; cin s; ll diff1 0, diff2 0; // 核心遍历 2*n 长度的串 for(int i 0; i 2 * n; i) { // 构造两种目标模式ABAB... 或 BABA... char target1 (i % 2 0) ? A : B; char target2 (i % 2 0) ? B : A; // 统计当前串与两种目标的差异点个数 if(s[i] ! target1) diff1; if(s[i] ! target2) diff2; } // 关键结论一次交换可以同时修复两个错误位置 cout min(diff1 / 2, diff2 / 2) \n; } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); // 内部已有 T 循环直接调用 return 0; }3. 核心考点与注意事项目标模式比对满足条件的字符串只有两种ABAB...和BABABA...。任意交换带来的简化由于题目允许交换任意位置我们不需要考虑移动距离只需要关心“有多少个位置放错了”。一次交换修两点因为 A 和 B 的总数固定。如果你有一个位置该放 A 却放了 B必然在另一个位置该放 B 却放了 A。交换这两个放错的字符可以同时修正 2 个差异位。4. 易错点回顾 (My Mistakes)1. 单引号 vs 双引号 (语法错误)错误经历写成了char target A;。纠正在 C 中char必须用单引号A双引号A是字符串常量赋值给char会导致编译失败。2. 变量未初始化 (运行结果错误)错误经历定义了ll diff1, diff2;但没有写 0。后果局部变量初始值为随机值导致计数结果变成天文数字。纠正定义计数器时务必手动初始化为 0。3. 循环范围与读入 (逻辑错误)错误经历数组只开了n长度或者循环只跑了n次。纠正题目给定的是n nn对 AB总长度是2 × n 2 \times n2×n读入和循环都必须以此为准。4. 输出位置错误 (多组数据逻辑)错误经历将cout放在了T循环之外。纠正这是多组测试数据每处理完一个n和s就要立刻输出一个结果并换行。