P17828 [CSP-J 2026] 回文串 / string 详细解题报告

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×105ai≤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←l1,r←r−1l \gets l1, r \gets r-1l←l1,r←r−1。时间复杂度O(L)O(L)O(L)空间O(L)O(L)O(L)。仅能通过LLL较小的测试点如测试点 1–4无法处理aia_iai​达到10910^9109的数据。#includeiostream#includestringusingnamespacestd;intmain(){intn;cinn;string s;for(inti1;in;i){intlen;charch;cinlench;for(intj1;jlen;j){sch;}}intans0;intleft0;intright(int)s.size()-1;while(leftright){if(s[left]!s[right]){ans;}left;right--;}coutans\n;return0;}洛谷测试拿 68 分2.2 特殊性质所有段字符相同若所有cic_ici​相同例如样例 22 a、3 a实际字符串aaaaa则字符串本身已经是回文串答案为 0。这个性质可用于对拍时的边界验证。2.3 特殊性质ai1a_i 1ai​1若每段长度均为 1则退化为普通字符串的回文判定直接用双指针比较字符即可答案为字符不同的对称位置对数。3. 正解推导双指针 RLE 区间贪心配对3.1 核心观察回文串的约束是sisL1−is_i s_{L1-i}si​sL1−i​。在游程编码表示下字符串被划分为若干同字符的连续区间。从两端向中间配对时同一时刻左右指针可能分别位于某个区间内部。由于区间内的字符完全相同我们不需要逐字符移动而可以一次性消耗掉左右两个区间中较短长度的部分。具体地维护两个指针lll和rrr分别表示当前尚未配对的最左段和最右段。同时维护ala_lal​和ara_rar​的剩余长度初始为输入的段长。每次取kmin⁡(al,ar)k \min(a_l, a_r)kmin(al​,ar​)然后如果clcrc_l c_rcl​cr​这kkk对字符已经相同不需要修改。如果cl≠crc_l \neq c_rcl​cr​这kkk对字符每一对都不同需要修改其中一侧的kkk个字符答案增加kkk。随后将al←al−ka_l \gets a_l - kal​←al​−kar←ar−ka_r \gets a_r - kar​←ar​−k。如果某一侧长度减为 0则将对应的指针向内移动一段l←l1l \gets l1l←l1或r←r−1r \gets r-1r←r−1并加载新的段长。当lrl rlr或lrl rlr且当前段是中间段时配对结束。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. 样例模拟样例 12 a2 b1 c→ 字符串aabbc初始l1l1l1c1ac_1ac1​a剩余 2r3r3r3c3cc_3cc3​c剩余 1。步骤kkk字符对是否相同答案增量操作后剩余1min⁡(2,1)1\min(2,1)1min(2,1)1aaavsccc否1左aaa剩 1右ccc耗尽 →rrr移到段 22min⁡(1,2)1\min(1,2)1min(1,2)1aaavsbbb否1左aaa耗尽 →lll移到段 2右bbb剩 1此时l2l2l2bbb剩 1r2r2r2bbb剩 1左右指向同一段的同一个剩余部分配对结束。总答案 112112112与样例输出一致。样例 22 a3 a→ 字符串aaaaa左段aaa剩余 2右段aaa剩余 3。kmin⁡(2,3)2k\min(2,3)2kmin(2,3)2字符相同答案增量 0。左段耗尽lll移到右段同一段结束。总答案 0。样例 31000000000 a×41000000000 b×3展开长度为7×1097 \times 10^97×109。双指针会先配对左右两侧的aaa与bbbk109k 10^9k109字符不同答案增加10910^9109共 3 对aaa–bbb累计3×1093 \times 10^93×109。之后剩余的aaa段在中间自身配对无消耗。输出3000000000需要使用long long。5. 代码实现参考代码 1#includeiostreamusingnamespacestd;constintMAXN2e510;intn;longlonga[MAXN];charc[MAXN];intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;for(inti1;in;i){cina[i]c[i];}intlt1;intrtn;longlongremLa[1];longlongremRa[n];longlongans0;while(ltrt){longlongkmin(remL,remR);if(c[lt]!c[rt]){ansk;}remL-k;remR-k;if(remL0){lt;remLa[lt];}if(remR0){rt--;remRa[rt];}}coutans\n;return0;}说明remL和remR分别记录左右指针当前所在段的剩余未配对长度。当某一侧剩余长度减为 0 时指针向内移动并重新加载该段的总长度。循环条件l r保证左右指针不会交叉如果最终lrl rlr说明中间剩下的是同一个段其内部字符完全相同天然关于自身中心对称不需要任何修改因此不计入答案。参考代码 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 数据生成器#includeiostream#includecstdlib#includectimeusingnamespacestd;intmain(){srand(time(0));intnrand()%51;coutn\n;for(inti1;in;i){intlenrand()%31;charcharand()%3;coutlen ch\n;}return0;}使用上述生成器生成 1000 组随机数据分别运行正解和暴力程序比较输出。所有测试组结果完全一致验证了双指针贪心算法在游程编码下的正确性。7. 总结思路总结回文串的每一对对称位置独立判定相同则 0 次修改不同则 1 次修改。在游程编码下不需要展开字符串而是用双指针维护左右两侧当前段的剩余长度。每次取两侧剩余长度的较小值kkk一次性配对kkk对字符根据字符是否相同累加答案kkk或 0。某一侧耗尽时指针向内移动一段。当左右指针相遇时停止。时间复杂度O(n)O(n)O(n)答案使用long long防止溢出。