第二题：回文串——小 R 的“镜子大挑战”
这道题看起来像是要把一个很长的字符串改成回文串，但题目有一个特别重要的条件：字符串没有直接给出来，而是用一段一段的“重复字符”来描述。
比如输入：
3 2 a 2 b 1 c表示：
先写 2 个
a：aa再写 2 个
b：bb最后写 1 个
c：c
拼起来就是：
aabbc小 X 喜欢回文串。回文串就像照镜子：从左往右读和从右往左读一样，例如aba、abba。
我们的任务是：最少修改多少个字符，才能让字符串变成回文串？
一、先从短字符串找规律
把aabbc写成一排：
位置： 1 2 3 4 5 字符： a a b b c ↘ ↙ ↘ ↙ ↘ ↙回文串要求两端对应的字符相同：
第 1 个字符要和第 5 个字符相同：
a和c不同，至少要改一个；第 2 个字符要和第 4 个字符相同：
a和b不同，至少要改一个；第 3 个字符在正中间，没有另一个字符与它配对，不需要修改。
所以最少修改 2 个位置。
关键规律
把字符串想象成一面镜子：
左边第 1 个和右边第 1 个是一对；
左边第 2 个和右边第 2 个是一对；
依次向中间靠拢；
一对字符不同，就需要修改其中一个；一对字符相同，就不用修改。
因此，答案就是：有多少对镜像位置的字符不相同。
二、难点：字符串可能长得“像一条巨龙”
题目中的长度可能非常大。例如：
1000000000 a代表十亿个a。我们不能真的把十亿个字符放进字符串里，既浪费内存，也会浪费时间。
不过，题目已经把字符串压缩成了“字符 + 重复次数”的形式。我们就可以不展开字符串，直接在这些段上进行比较。
例如：
a a b b c可以看成三段：
左边 右边 [ a a ] [ b b ] [ c ]我们从两端开始：
左边当前段是
a，右边当前段是c；左右两段字符不同，配对的字符都不相同；
左边这段有 2 个字符，右边这段有 1 个字符，所以先处理 1 对；
右边的
c用完了，右指针向左移动；再比较左边剩下的
a和右边的b。
这就像两位同学从队伍两端向中间走，每次比较当前面对面的那一段。
三、算法：左右两位“镜像检查员”
我们准备：
l：指向左边当前的段；r：指向右边当前的段；leftRem：左边当前段还剩多少个字符；rightRem：右边当前段还剩多少个字符；pairs：还需要检查多少对镜像字符；ans：已经发现多少对不相同的字符。
每次处理左右两段中能够配对的最小数量：
k = min(leftRem, rightRem, pairs);如果两段字符不同，这k对都不相同，答案增加k。
然后把左右两段各自减少k个字符。如果某一段用完了，就移动指针，进入下一段。
因为字符串长度可能达到十亿甚至更大，ai、总长度和答案都要使用long long，不能只用int。
四、完整 C++ 程序
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<long long> a(n); vector<char> c(n); long long total = 0; // 读取每一段的长度和字符 for (int i = 0; i < n; i++) { cin >> a[i] >> c[i]; total += a[i]; } // 回文串只需要比较前一半和后一半 long long pairs = total / 2; int l = 0; int r = n - 1; long long leftRem = a[l]; long long rightRem = a[r]; long long ans = 0; while (pairs > 0) { // 这次最多能比较多少对 long long k = min(leftRem, rightRem); k = min(k, pairs); // 两边字符不同，这 k 对都需要修改其中一个字符 if (c[l] != c[r]) { ans += k; } // 左右两段各消耗 k 个字符 leftRem -= k; rightRem -= k; pairs -= k; // 左边这一段用完了，进入下一段 if (leftRem == 0 && pairs > 0) { l++; leftRem = a[l]; } // 右边这一段用完了，进入前一段 if (rightRem == 0 && pairs > 0) { r--; rightRem = a[r]; } } cout << ans << endl; return 0; }五、用样例走一遍
输入：
3 2 a 2 b 1 c总长度是：
2 + 2 + 1 = 5只需要比较前一半，所以要检查：
5 / 2 = 2 对当前比较 | 左边字符 | 右边字符 | 处理数量 | 答案增加 |
|---|---|---|---|---|
第 1 次 |
|
| 1 对 | 1 |
第 2 次 |
|
| 1 对 | 1 |
最终答案：
2六、举一反三：这道题考察我们什么？
这道题的核心思想不只是“回文串”，而是一个非常有用的算法技巧：
当数据很长，但相邻的一大段内容都相同时，可以不展开数据，而是按段处理。
例如：
一排相同颜色的积木，可以记录“颜色 + 数量”；
很长的连续数字，可以记录“数字 + 出现次数”；
连续相同字符的字符串，可以记录“字符 + 长度”。
遇到这种题时，可以问自己三个问题：
数据是不是由很多段连续相同的内容组成？
我能不能只记录每段的内容和长度？
能不能每次处理一整段，而不是一个一个处理？
如果答案是可以，就可能用到这种双指针 + 分段处理的思路。
最后记住：这题不是把字符串真的造出来再检查，而是让左右两位“镜像检查员”按段向中间走。这样即使字符串长达十亿个字符，程序也不需要逐个访问十亿个位置。
