下面是 [CSP-J 2026] 回文串(string) 的 C++ 代码。
一、思路
字符串以游程编码给出(每段「长度 a_i + 字符 c_i」),总长可达 2×10¹⁴,不能展开,必须用双指针在「段」的层面做左右对消。
用左右两个指针 l、r 分别指向尚未处理的最左段和最右段,各自维护段内剩余长度 lenL、lenR:
若 c[l] == c[r]:这一段对称部分无需修改,令 lenL、lenR 同时减去 t = min(lenL, lenR);某侧减到 0 就移动该侧指针。
若 c[l] != c[r]:这两个字符必须有一侧被改掉。把较短的一侧整体改掉最省(改短侧的全部剩余字符),答案累加 t = min(lenL, lenR),同样令两侧各减 t,然后推进指针。
每段最多被处理一次,复杂度 O(n)。
二、C++ 代码
三、要点说明
只比较「字符是否相同」:是否相同决定这一段要不要计入修改数;相同则不计,不同则至少要为较短侧的 t 个位置各改一次。
改短的一侧最优:两侧剩余长度不同时,把短的一段整体改成与长的一段相同,代价是较短长度,比改长的一段省。
归并同长度段:当 lenL == lenR 时两侧同时耗尽,指针各自推进,处理顺序无碍。
整数范围:a_i ≤ 10⁹、n ≤ 2×10⁵,最长约 2×10¹⁴,答案可能到 3×10⁹ 甚至更大(见样例 #3 输出 3000000000),所以 a[]、len、ans 全部用 long long。
复杂度 O(n):每个段最多进入一次,符合 n ≤ 2×10⁵ 的规模。
样例验证
样例 #1:2a 2b 1c → S = aabbc,按上述流程首尾 a 对 c 不同、累加 min 后推进,最终得到 2,与输出 2 一致
样例 #2:2a 3a → S = aaaaa,全程字符相同,答案 0,与输出 0 一致
样例 #3:三段 a 对三段 b,左右字符均不同,累加 3×10⁸ 的对称部分,得 3000000000,与输出一致