题解
2026-11-08 18:30:20
发布于:新疆
下面是 [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++ 代码
#include <bits/stdc++.h>
using namespace std;
/*
* [CSP-J 2026] 回文串 (string)
*
* 题意:字符串 S 由 n 段游程编码给出(每段 a_i 个字符 c_i),
* 每次可把任意位置改成任意小写字母,求使 S 成为回文串的最少修改次数。
*
* 关键:总长 L 可达 6e8 ~ 2e14,不能展开字符串,必须在"段"上做双指针对消。
*
* 做法:左右指针 l、r,各维护段内剩余长度 lenL、lenR。
* - 若 c[l] == c[r]:对称部分直接匹配,两侧各减去 t = min(lenL, lenR);
* - 若 c[l] != c[r]:必须改掉一侧的 t 个字符,累加 t 到答案,两侧各减 t。
* 某侧长度减到 0 就移动对应指针,直到 l > r。
*
* 数据范围:1 <= n <= 2e5,1 <= a_i <= 1e9,答案可能达 1e14,必须用 long long。
* 复杂度:O(n)。
*/
const int MAXN = 200005;
int n;
long long a[MAXN]; // 每段长度
char c[MAXN]; // 每段字符
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i] >> c[i];
int l = 1, r = n;
long long lenL = a[l], lenR = a[r];
long long ans = 0;
while (l < r) {
if (c[l] == c[r]) {
// 对称字符相同,这段不用改
long long t = min(lenL, lenR);
lenL -= t;
lenR -= t;
} else {
// 对称字符不同,改掉较短一侧的 t 个字符最省
long long t = min(lenL, lenR);
ans += t;
lenL -= t;
lenR -= t;
}
// 某侧耗尽,推进指针并加载新段
if (lenL == 0 && l < r) {
++l;
lenL = a[l];
}
if (lenR == 0 && l < r) {
--r;
lenR = a[r];
}
}
cout << ans << '\n';
return 0;
}
三、要点说明
只比较「字符是否相同」:是否相同决定这一段要不要计入修改数;相同则不计,不同则至少要为较短侧的 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,与输出一致
这里空空如也







有帮助,赞一个