一、题目重现

椰程信奥 - T2 回文串

题目描述

小 R 有一个长度为 L、只含小写英文字母的字符串 S。虽然 S 可能很长，但它可以分成 n 个连续的段：第 i 段由 a_i 个相同的小写字母 c_i 构成，把这 n 段依次拼接起来就是 S。相邻两段的字符可以相同。

若一个字符串反转后与原字符串相同，就称它是回文串，例如 aba、abba 是回文串，aabbc 不是。也就是说，第 1 个字符要等于倒数第 1 个，第 2 个要等于倒数第 2 个……

小 R 可以把 S 中任意一个位置的字符改成任意小写英文字母。求最少修改多少个位置，才能让 S 变成回文串。

输入格式

第一行一个正整数 n。接下来 n 行，每行一个正整数 a_i 和一个小写英文字母 c_i。

输出格式

一行一个整数，表示最少修改次数。

输入输出样例

样例 1

3
2 a
2 b
1 c

输出：

2

解释：拼出来是 aabbc。把最后的 c 和倒数第二个 b 都改成 a，得到回文串 aabaa，共改 2 处。

样例 2

2
2 a
3 a

输出 0：拼出来是 aaaaa，本来就是回文串。

样例 3

6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b

输出：

3000000000

数据范围与约定

• 1 ≤ n ≤ 2×10^5，1 ≤ a_i ≤ 10^9；
• 部分测试点 n 很小但 a_i 达到 10^9，另有测试点 n 与 a_i 同时取到上限；
• 答案可能超过 32 位整数的范围，请使用 64 位整数；
• 原题时限 1.0 秒，内存 1024 MiB。

二、先把样例玩一遍（小学生版）

aabbc 一共 5 个位置，照镜子配对：

改成 aabaa，共 2 处，与题面一致。

规律马上冒出来：不同的配对，改 1 处就够；相同的配对，一处都不用改；各对之间互不打扰。所以答案就是「字符不同的配对有多少对」。

为什么改 1 处就够？把其中一个字母改成另一个，这一对就一样了。为什么至少要改 1 处？两个不同的字母，不动其中一个，永远不可能相同。

三、笨办法为什么不行

最直觉的做法：把 aabbc 真的存进一个 string，左右各放一根手指，一个字符一个字符往中间挪。

但 n 最大 2×10^5，每段最多 10^9 个字母，拼起来最长是：

200000 × 1000000000 = 200000000000000 个字母（200 万亿）

别说内存装不下，就算一秒数一亿个，也要数二十多天。这题真正考的是：不把字符串造出来，也能算出答案。

四、妙招：两摞硬币，一次对齐一摞

把左右两边各看成一摞硬币，同一摞上的字母都一样：

1. 一次能配多少对？看两边谁先不够：take = min(左边剩的个数, 右边剩的个数)；
2. 如果两摞字母不同，这 take 对每对都要改 1 处，一口气加 take，不用一个一个加；
3. 两边各减掉 take，谁变成 0 就换下一段；
4. 一直做到左右两只手碰到同一段为止——那是中间段，自己和自己照镜子，字母必然相同，不用改。

打个比方：不是一颗一颗数米，而是「左边这袋 2 斤、右边这袋 1 斤，一次称 1 斤」，一袋一袋过秤。

跟着手算样例 1

段：① 2个a ｜ ② 2个b ｜ ③ 1个c，l 指左、r 指右。

输出 2。样例 2 同理：两边都是 a，take = 2 但不加，输出 0。

从这里还能看出：相邻两段字母相同，不需要先合并。算法按「还剩多少个」一段段消耗，不合并照样对，别给自己加额外工作。

五、为什么答案一定最少

1. 回文要求第 p 个与倒数第 p 个相同，整个字符串被分成若干互不相干的配对（长度为奇数时，最中间那个自己跟自己配，天然相同）；
2. 一对里字母不同，至少要改 1 个，改 1 个就够，所以每对恰好贡献 0 或 1；
3. 不同对之间改谁都不影响别的对，答案就是所有对的贡献相加；
4. 两摞硬币只是把「连续一大片相同字母的配对」打包一次性加完，没有多算也没有漏算。

六、一个必须记住的数字

样例 3 里前三段全是 a、后三段全是 b，三段对三段，每段 10 亿个字符都不同：

答案 = 1000000000 × 3 = 3000000000

而 int 最多只装到约 2147483647（21 亿）。3000000000 装进去会溢出变成负数，直接 WA。所以 len、left、right、ans 全部用 long long。

顺带一提：样例 3 用我们的算法只走 3 轮就出答案，30 亿个字符一个都没真的写出来。

七、参考代码（AC）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> len(n);
    vector<char> ch(n);
    for (int i = 0; i < n; ++i) cin >> len[i] >> ch[i];

    // 回文把位置 p 与 L+1-p 配对；每对字符不同只需改一次，且各对独立。
    int l = 0, r = n - 1;
    long long left = len[l], right = len[r], ans = 0;
    while (l < r) {
        long long take = min(left, right);
        if (ch[l] != ch[r]) ans += take;
        left -= take;
        right -= take;
        if (left == 0) {
            ++l;
            if (l < r) left = len[l];
        }
        if (right == 0) {
            --r;
            if (l < r) right = len[r];
        }
    }
    // l == r 时是同一段自己配对，字符必然相同，不产生修改。
    cout << ans << '\n';
    return 0;
}

八、代码逐段解析

• vector<long long> len(n) 存每段长度，vector<char> ch(n) 存每段字母；长度用 long long 是因为要参与大数累加。
• left、right 是两只手当前那一摞还剩几个，ans 是答案。
• take = min(left, right) 一次配一批；if (ch[l] != ch[r]) ans += take; 一口气加，不是 +1。
• 两个 if 分别处理左右换段，不能写成 if/else：两边可能在同一轮同时用完。
• while (l < r) 而不是 l <= r：相遇时是中间段，自己配自己，不用改；里面的 if (l < r) 保护是防止相遇后还去读不存在的「新一摞」。
• ios::sync_with_stdio(false); cin.tie(nullptr); 给 20 万行读入提速。

九、复杂度分析

每一段只会被「用完」一次，左指针往右走 n 步、右指针往左走 n 步：时间 O(n)，内存 O(n)。n 最大 20 万，1 秒绰绰有余。若写成按字符逐个循环，就是 O(L)、L 最大 200 万亿，必超时。

十、易错点清单

1. 绝对不要把字符串真的展开（内存和时间都爆）。
2. ans 与 len 用 long long：样例 3 的 3000000000 会撑爆 int。
3. 一次加 take 而不是 +1，否则又退化成按字符循环。
4. 循环条件写 l < r，写成 <= 可能在中间段越界。
5. 两边同时换段：一轮里左右可能同时用完，两个 if 都要写。
6. 换段后判断 l < r：相遇了就别再取新段。
7. 相邻同字母段不用合并，算法天然支持。
8. 文件输入输出：原题要求 string.in / string.out，本文代码改用标准输入输出；OJ 提交时请按题目要求加回 freopen。

十一、考点总结

一句话记住：回文是照镜子，不同的一对改一个；长串别展开，两摞硬币一次称一批。

本文题面整理自 CCF CSP-J 2026 第二轮（入门组）试题，题目版权归中国计算机学会所有。题解与代码由椰程信奥整理撰写，参考答案仅供参考，最终以 CCF 官方公布为准。