P17828 [CSP-J 2026] 回文串 / string 详细解题报告
1. 题目分析与需求概括
题目模型：给定一个由nnn个“游程”构成的字符串SSS。第iii段由aia_iai个字符cic_ici组成，所有段依次拼接得到长度为L=∑aiL = \sum a_iL=∑ai的字符串SSS。允许将任意位置的字符修改为任意小写字母。求将SSS变成回文串所需的最少修改次数。
数据范围：n≤2×105n \le 2 \times 10^5n≤2×105，ai≤109a_i \le 10^9ai≤109。字符串的展开长度可达2×10142 \times 10^{14}2×1014，不可能显式构造字符串。答案可能超过 32 位整数范围，需使用 64 位整数。
关键需求：在游程编码（RLE）表示下，直接完成回文配对与修改次数统计，时间复杂度必须接近O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)。
2. 暴力写法与特殊性质
2.1 暴力展开（小数据）
直接将SSS展开为字符数组，然后用双指针从两端向中间配对：若sl≠srs_l \neq s_rsl=sr，答案加一；否则不变；然后l←l+1,r←r−1l \gets l+1, r \gets r-1l←l+1,r←r−1。时间复杂度O(L)O(L)O(L)，空间O(L)O(L)O(L)。仅能通过LLL较小的测试点（如测试点 1–4），无法处理aia_iai达到10910^9109的数据。
#include<iostream>#include<string>usingnamespacestd;intmain(){intn;cin>>n;string s="";for(inti=1;i<=n;i++){intlen;charch;cin>>len>>ch;for(intj=1;j<=len;j++){s+=ch;}}intans=0;intleft=0;intright=(int)s.size()-1;while(left<right){if(s[left]!=s[right]){ans++;}left++;right--;}cout<<ans<<"\n";return0;}洛谷测试拿 68 分
2.2 特殊性质：所有段字符相同
若所有cic_ici相同（例如样例 2：2 a、3 a，实际字符串aaaaa），则字符串本身已经是回文串，答案为 0。这个性质可用于对拍时的边界验证。
2.3 特殊性质：ai=1a_i = 1ai=1
若每段长度均为 1，则退化为普通字符串的回文判定，直接用双指针比较字符即可，答案为字符不同的对称位置对数。
3. 正解推导：双指针 + RLE 区间贪心配对
3.1 核心观察
回文串的约束是si=sL+1−is_i = s_{L+1-i}si=sL+1−i。在游程编码表示下，字符串被划分为若干同字符的连续区间。从两端向中间配对时，同一时刻左右指针可能分别位于某个区间内部。由于区间内的字符完全相同，我们不需要逐字符移动，而可以一次性消耗掉左右两个区间中较短长度的部分。
具体地，维护两个指针lll和rrr，分别表示当前尚未配对的最左段和最右段。同时维护ala_lal和ara_rar的剩余长度（初始为输入的段长）。每次取k=min(al,ar)k = \min(a_l, a_r)k=min(al,ar)，然后：
- 如果cl=crc_l = c_rcl=cr：这kkk对字符已经相同，不需要修改。
- 如果cl≠crc_l \neq c_rcl=cr：这kkk对字符每一对都不同，需要修改其中一侧的kkk个字符，答案增加kkk。
随后，将al←al−ka_l \gets a_l - kal←al−k，ar←ar−ka_r \gets a_r - kar←ar−k。如果某一侧长度减为 0，则将对应的指针向内移动一段（l←l+1l \gets l+1l←l+1或r←r−1r \gets r-1r←r−1），并加载新的段长。当l>rl > rl>r或l=rl = rl=r且当前段是中间段时，配对结束。
3.2 为什么贪心是正确的？
对于任意一对对称位置，如果两侧字符不同，修改任意一侧的代价都是 1，且修改这一侧不会对更内层或更外层的配对产生“额外收益”——因为每次修改只影响当前这一对字符的相等性。因此，对于每一对字符不同的对称位置，至少需要 1 次修改；对于字符相同的对称位置，不需要修改。双指针贪心恰好按照“每一对独立处理”的方式累加下界，并且可以通过实际修改达到这个下界，因此是最优的。
3.3 复杂度分析
每次迭代至少使lll或rrr中的一个指针移动一次（或使当前段长度减为 0）。指针最多移动nnn次，因此总迭代次数为O(n)O(n)O(n)。每次迭代O(1)O(1)O(1)，总时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)，完全满足n≤2×105n \le 2 \times 10^5n≤2×105的要求。答案使用long long存储。
4. 样例模拟
样例 1：2 a，2 b，1 c→ 字符串aabbc
初始：l=1l=1l=1（c1=ac_1=ac1=a，剩余 2），r=3r=3r=3（c3=cc_3=cc3=c，剩余 1）。
| 步骤 | kkk | 字符对 | 是否相同 | 答案增量 | 操作后剩余 |
|---|---|---|---|---|---|
| 1 | min(2,1)=1\min(2,1)=1min(2,1)=1 | aaavsccc | 否 | +1 | 左aaa剩 1，右ccc耗尽 →rrr移到段 2 |
| 2 | min(1,2)=1\min(1,2)=1min(1,2)=1 | aaavsbbb | 否 | +1 | 左aaa耗尽 →lll移到段 2；右bbb剩 1 |
此时l=2l=2l=2（bbb剩 1），r=2r=2r=2（bbb剩 1），左右指向同一段的同一个剩余部分，配对结束。总答案 =1+1=21+1=21+1=2，与样例输出一致。
样例 2：2 a，3 a→ 字符串aaaaa
左段aaa剩余 2，右段aaa剩余 3。k=min(2,3)=2k=\min(2,3)=2k=min(2,3)=2，字符相同，答案增量 0。左段耗尽，lll移到右段（同一段），结束。总答案 0。
样例 3：1000000000 a×4，1000000000 b×3
展开长度为7×1097 \times 10^97×109。双指针会先配对左右两侧的aaa与bbb：k=109k = 10^9k=109，字符不同，答案增加10910^9109；共 3 对aaa–bbb，累计3×1093 \times 10^93×109。之后剩余的aaa段在中间自身配对，无消耗。输出3000000000，需要使用long long。
5. 代码实现
参考代码 1
#include<iostream>usingnamespacestd;constintMAXN=2e5+10;intn;longlonga[MAXN];charc[MAXN];intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(inti=1;i<=n;i++){cin>>a[i]>>c[i];}intlt=1;intrt=n;longlongremL=a[1];longlongremR=a[n];longlongans=0;while(lt<rt){longlongk=min(remL,remR);if(c[lt]!=c[rt]){ans+=k;}remL-=k;remR-=k;if(remL==0){lt++;remL=a[lt];}if(remR==0){rt--;remR=a[rt];}}cout<<ans<<"\n";return0;}说明：remL和remR分别记录左右指针当前所在段的剩余未配对长度。当某一侧剩余长度减为 0 时，指针向内移动并重新加载该段的总长度。循环条件l < r保证左右指针不会交叉；如果最终l=rl = rl=r，说明中间剩下的是同一个段，其内部字符完全相同，天然关于自身中心对称，不需要任何修改，因此不计入答案。
参考代码 2
#include <iostream> using namespace std; const int N = 2e5 + 10; long long ans = 0; int a[N]; char b[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } int lt = 1, rt = n; while (lt < rt) { bool flag = false; if (b[lt] != b[rt]) { flag = true; } int step = 0; if (a[lt] == a[rt]) { step = a[lt]; lt++, rt--; } else if (a[lt] < a[rt]) { step = a[lt]; a[rt] -= step; lt++; } else { step = a[rt]; a[lt] -= step; rt--; } if (flag) { ans += step; } } cout << ans << endl; return 0; }6. 对拍验证
6.1 暴力程序
参考上面暴力代码6.2 数据生成器
#include<iostream>#include<cstdlib>#include<ctime>usingnamespacestd;intmain(){srand(time(0));intn=rand()%5+1;cout<<n<<"\n";for(inti=1;i<=n;i++){intlen=rand()%3+1;charch='a'+rand()%3;cout<<len<<" "<<ch<<"\n";}return0;}使用上述生成器生成 1000 组随机数据，分别运行正解和暴力程序，比较输出。所有测试组结果完全一致，验证了双指针贪心算法在游程编码下的正确性。
7. 总结
思路总结：
- 回文串的每一对对称位置独立判定：相同则 0 次修改，不同则 1 次修改。
- 在游程编码下，不需要展开字符串，而是用双指针维护左右两侧当前段的剩余长度。
- 每次取两侧剩余长度的较小值kkk，一次性配对kkk对字符，根据字符是否相同累加答案kkk或 0。
- 某一侧耗尽时，指针向内移动一段。当左右指针相遇时停止。
- 时间复杂度O(n)O(n)O(n)，答案使用
long long防止溢出。
