形式化题目

一个长度为 $L$ 的字符串 $S = s_1 s_2 \cdots s_L$ 以行程编码的形式给出：第 $i$ 段是 $a_i$ 个字符 $c_i$，$L = \sum_{i=1}^{n} a_i$。

一次操作把某个位置上的字符改成任意小写字母。要求用最少次数的操作使 $S$ 成为回文串，即对所有 $i = 1, 2, \ldots, L$ 满足

这个式子说的是：把字符串从两端同时往里数，位置配成一对对，每一对的左右两个字符必须完全相同。

暴力解法

思路

按定义做：把行程编码展开成真正的字符串，然后从两端往中间扫，数一数有多少组对称位置的字符不同。

brute.cpp 就是这两步，s.push_back(ch) 循环 $a_i$ 次完成展开。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 18:55
 * update_at: 2026-10-31 18:58
 */
// brute.cpp：直接把字符串展开，再一组一组数对称位置上字符不同的组数。
// 只有字符串总长很小的时候才能用，专门用来和 main.cpp 对拍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; ++i) {
        ll len;
        char ch;
        cin >> len >> ch;
        for (ll k = 0; k < len; ++k) s.push_back(ch);
    }

    int L = (int)s.size();
    ll ans = 0;
    for (int i = 0; i < L / 2; ++i) {
        if (s[i] != s[L - 1 - i]) ++ans;
    }
    cout << ans << '\n';
    return 0;
}

复杂度

展开需要 $O(L)$ 时间与 $O(L)$ 空间，扫描再花 $O(L)$ 时间。$n \leqslant 2 \times 10^5$、$a_i \leqslant 10^9$ 时 $L$ 可以到 $2 \times 10^{14}$，展开这一步就已经放不下了。

瓶颈

瓶颈不在算法思路，而在“必须把字符串摊开成每一个位置”这个前提：行程编码只用 $n$ 个数就描述完了整个串。

所以要想通过全部测试点，做法不能依赖 $L$，只能依赖段数 $n$。

正解

关键观察

先把“改几个字符”变成“有几组冲突”。

• 位置 $i$ 与位置 $L+1-i$ 组成一对，回文要求这一对相等。
• 不同的对涉及的位置互不重叠，改动一对不会影响其他对。
• 一对字符不同，至少要改其中一个（改一个就够，把另一个复制过来）；一对字符相同，一个都不用改。

于是最少修改次数正好等于字符不相同的对称位置对数，也就是暴力解法数出来的那个数。剩下要做的只是在不展开字符串的前提下数出这个对数。

思路

想先跟着动画把双指针走一遍，可以打开 交互教程：节点是 [100 a] 这样的一段，每走一轮段长就被减短（[4 a] → [2 a]），左右指针从两端向中点靠拢。

把两个指针分别放在字符串的两端：左指针从第 1 个字符往右走，右指针从第 $L$ 个字符往左走。左右各自只需要走 $\lfloor L/2 \rfloor$ 步，因为这就是全部的配对组数（代码里记作 half）；奇数长度中间那个字符配给自己，不用管。

指针都按段移动。代码里把“这一段还剩几个字符”直接记在 $a$ 数组里：吃过多少就减多少，减到 0 就换下一段。于是全程只用盯着三件事：左边停在哪一段（下标 li）、右边停在哪一段（下标 ri）、已经配好了几组（done）。

每一轮能整批吃掉多少组，由三个数取最小决定：左段还剩 a[li]，右段还剩 a[ri]，还差 half - done 组。

take = min(a[li], a[ri], half - done)

三个候选分别回答：左边这一段还能给几个字符、右边这一段还能给几个字符、还差几组才凑满一半。取最小，才不会多配。

两侧字符不同时，这 take 组对称位置全都要改，答案加上 take；相同时一组都不用改。

然后两段的剩余量各减去 take，减到 0 就换下一段接着走。

以样例 #1 的 $S = \mathtt{aabbc}$（编码 2 a、2 b、1 c）为例，$L = 5$，只需配对 2 组：

第 2 轮把 2 组配满，答案 2，与样例一致；中间那个 b 配给自己。

两侧撞进同一段怎么办？ 左边那一段的剩余量减到 0 之后，li 加一可能正好等于 ri，两个指针停在同一段上。既然左右指针都在这段里，中间还没配的那段区间也整个落在这一段内：左右各吃掉 done 个字符，剩下的正好是原串的第 done + 1 个到第 L - done 个字符。这一段里的字符全都相同，所以剩下的组一组都不用改，答案不会再变，直接结束。

再拿 3 a、2 b、4 a、3 b 走一遍（$L = 12$，要配 6 组），列的读法和上一张表一样：

第 2 轮打完，第 2 段 2 b 用完，左指针向右换段；右指针本来就停在第 3 段上，已经从这一段右端吃掉了 2 个，还剩 2 个。于是两个指针都落在第 3 段，第 3 行那两列都是 2 就来自这里。这时还差 1 组，但没配的字符全在这一段里，直接收工，答案停在 5。

数据规模决定了两处必须用 long long：$L$ 最大约 $2 \times 10^{14}$，答案最大也可以到 $10^{14}$ 量级。样例 #3 的答案 $3 \times 10^9$ 就已经超过 int 上限。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-31 18:55
 * update_at: 2026-10-31 20:00
 */
// main.cpp：答案等于「字符不同的对称位置对数」。
// 两侧的段指针同时向中间走，每段还剩多少直接记在 a[] 里（边走边减）；
// 两侧撞进同一段时，剩下的字符全都在这一段、字符必然相同，直接收工。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;
int n;
ll a[maxn];    // 第 i 段的长度，跑的过程中会被减掉已经配掉的字符数
char c[maxn];  // 第 i 段全是字符 c[i]

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

    cin >> n;
    ll L = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> c[i];
        L += a[i];
    }

    ll half = L / 2;   // 一共要配几组，奇数长度时正中间的字符配给自己
    ll done = 0;       // 已经配好几组
    ll ans = 0;
    int li = 0, ri = n - 1;   // 左端当前段、右端当前段

    while (done < half) {
        if (li == ri) {
            // 两侧已经走进同一段：还没配的字符全在这段里，字符都一样，
            // 这些组一组都不用改，答案不会再变，直接结束。
            break;
        }
        // 两侧还在不同的段：各能提供多少个字符就吃多少，但别超过还差的组数
        ll take = min(min(a[li], a[ri]), half - done);
        if (c[li] != c[ri]) ans += take;   // 这一批 take 组对称位置全都要改
        a[li] -= take;
        a[ri] -= take;
        done += take;
        if (a[li] == 0) ++li;   // 这一段用完了，换成下一段
        if (a[ri] == 0) --ri;
    }

    cout << ans << '\n';
    return 0;
}

复杂度

• 时间：每一轮要么让某一侧的段减到 0（指针换段），要么让 done 凑满 $\lfloor L/2 \rfloor$ 组，要么两侧撞进同一段直接收工；两个指针最多各换 $n$ 次段，所以是 $O(n)$。
• 空间：只存行程编码本身；段长是在 $a$ 数组上就地减的，没有额外开数组，$O(n)$。

总结

这道题有两次“换个说法”。

第一步是把“最少改几个字符”换成“有几组对称位置冲突”。冲突对数是最小修改量的下界（每组至少改一个），而每组改一个就能达到这个下界，所以两者相等。这一步完成后问题不再关心具体改成什么字母。

第二步是把“数冲突”从展开后的字符串移到行程编码上。编码里一段连续相同的字符，与对方同一段的连续字符配对时，结论整批相同，于是可以按段批量处理，复杂度从 $O(L)$ 降到 $O(n)$，也就不再需要 $2 \times 10^{14}$ 的字符串空间。

代码最后有两个写法上的选择：

• 段长直接减在 $a$ 数组里，不另开“已经用掉多少”的偏移变量。于是每轮的三个候选数就是 a[li]、a[ri]、half - done，读出来就是“左边还剩、右边还剩、还差几组”，也不会出现“段内偏移忘了清零”这类错。代价是 $a$ 被改写，本题只要答案，不需要保留原串。
• 两侧走进同一段就直接结束：未配对的字符全在这一段里，字符必然相同，一组都不用改。这样“相遇”从取小运算里的隐式行为变成代码里显式的一行，读者能看见它。

相关 rbook 文章

做这题用到的知识点在 rbook 算法书 上有专门章节：

行程编码本身（一段连续相同的字符打包成“个数 + 字符”）rbook 还没有专文；本题的难点正是“不能把编码展开”。