题解 CF486C 【Palindrome Transformation】

貌似现在只有一篇$O(n\log n)$的题解？给一个$O(n)$的吧。

我们先预处理出来每一个字符要想和其对应位置的字符相同，所需的操作次数。
以样例为例子：

aeabcaez
10011001

$\texttt{a}$变成$\texttt{z}$要1步，$\texttt{b}$变成$\texttt{c}$要1步
然后分类讨论k的位置即可，详见代码注释

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int c[100005]; 
int f(char ch1,char ch2){
	int x=ch1-96,y=ch2-96;
	return min(abs(x-y),min(abs(x+26-y),abs(x-y-26)));
}//预处理
int main(){
	int n,k,ans=0;
	string s;
	cin>>n>>k>>s;
	k--;
	for(int i=0;i<n;i++){
		c[i]=f(s[i],s[n-i-1]);
	}
	int L=-1,R=-1;
	if(k<n/2){//k在前半部分
		for(int i=0;i+i<=n;i++)if(c[i]){L=i;break;}
		for(int i=n/2-1;i>=0;i--)if(c[i]){R=i;break;}//确认要经过的范围
		if(L==R&&L==-1){
			cout<<0;
			return 0;
		}//直接回文串的话处理掉就行
		if(k<=L){
			ans+=R-k;
		}//k在要经过范围左侧
		else if(k>=R){
			ans+=k-L;
		}//右侧
		else{
			ans+=R-L+min(k-L,R-k); 
		}//内部
		for(int i=L;i<=R;i++){
			ans+=c[i];
		}
		cout<<ans;
	}
	else{//k在后半部分，其他同上
		for(int i=n/2;i<=n;i++)if(c[i]){L=i;break;}
		for(int i=n;i>=n/2;i--)if(c[i]){R=i;break;}
		if(L==R&&L==-1){
			cout<<0;
			return 0;
		}
		if(k<=L){
			ans+=R-k;
		}
		else if(k>=R){
			ans+=k-L;
		}
		else{
			ans+=R-L+min(k-L,R-k); 
		}
		for(int i=L;i<=R;i++){
			ans+=c[i];
		}
		cout<<ans;
		
	}
	return 0;
}

很明显，时间复杂度是$O(n)$的