蒟蒻第一次写题解。
题意概括
给定 $n$ 个字符串，求将其拼接后任意更改字符的情况下，转换为回文串的最小操作步数。
思路
首先不难发现，对于一个非回文串，如果要通过任意更改字符变成回文串，最小操作数量应当为左右两边字符不相同的数量。（后附正确性证明）
但是本题并没有直接给字符串 $s$，而是给了它的具体组成，因此应当从两边开始处理组成，若有字符余下，则不往里缩进，而是减少字符数量（题目中的 $a_i$）。
考虑双指针做法。左指针 $l$ 与右指针 $r$ 分别往内部缩进，超越时即为边界。
特别的，若两边数量恰好相等，两边都需要缩进。
最坏情况下答案约为 $\frac{1}{2}\sum a_i \le \frac{1}{2}\times 2\times10^5\times10^9=10^{14}$，超过 int 范围，需用 long long。
AC代码如下：
#include<bits/stdc++.h>
using namespace std;
int a[200005];char c[200005];
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n;long long ans=0;cin>>n; //答案可以达到10^14量级，注意long long
for(int i=0;i<n;i++) cin>>a[i]>>c[i];
int l=0,r=n-1;
while(l<=r){ //边界，l<r也可以，因为l==r时c[l]==c[r]，不做任何处理
if(a[l]<a[r]){ //对左、右指针处数量的比较
ans+=(c[l]==c[r]?0:a[l]); //只有在字符不一致时才记录操作次数
a[r]-=a[l];
l++; //左缩进
}else if(a[r]<a[l]){
ans+=(c[l]==c[r]?0:a[r]);
a[l]-=a[r];
r--; //右缩进
}else{ //a[l]==a[r]
ans+=(c[l]==c[r]?0:a[r]);
l++;r--; //左右数量相等时需要同时缩进
}
}cout<<ans<<endl;
return 0;
}三目运算符可扩写为：
if(c[l]!=c[r]){
ans+=a[l]; //或者a[r]
}当然，本题的while循环内并不需要直接并列三个 if 语句，而是蒟蒻考场上这么写。
这里还有一种做法：
while(l<r){
long long p=min(a[l],a[r]);
a[l]-=p;a[r]-=p;
ans+=(c[l]==c[r]?0:p);
if(a[l]==0) l++; //等于0表示已经判断完，需要缩进
if(a[r]==0) r--;
}特别的，明显第二种做法更优。
正确性说明
回文串要求第 $i$ 个字符和第 $L+1−i$ 个字符相同。我们从两端向中间配对。
每一对配对的字符，如果相同则无需修改；如果不同，则至少需要修改其中一个。
由于每段内字符相同，左右两端各取 $min(a[l], a[r])$ 个字符进行配对，这些配对要么全部相同（即 $c_l=c_r$），要么全部不同（即 $c_l \neq c_r$）。不同的那些对，每对修改一个字符即可，因此贡献为 $min(a[l], a[r])$。
消去后继续处理剩余部分，直到所有位置配对完毕。
每一步的贡献都是下界，且可以同时达到，所以贪心最优。
时间复杂度
由于每个段只会被遍历 $1$ 次，且 $l$ 只增，$r$ 只减，因此时间复杂度为 $O(n)$。
需要存储 $a_i$ 与 $c_i$ 数组，因此空间复杂度为 $O(n)$。
没有评论