比赛 4043级NOIP2022欢乐赛3rd 评测结果 AAAAAAATTT
题目名称 回文串回文 最终得分 70
用户昵称 op_组撒头屯 运行时间 3.000 s
代码语言 C++ 内存使用 2.01 MiB
提交时间 2022-11-04 20:46:55
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N=1000000+5;
char s[N]; 
int n;
int main(){
	freopen ("strts.in","r",stdin);
	freopen ("strts.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	int l=1,r=n;ll ans=0;
	while(l<r){
		if (s[l]==s[r]){
			l++,r--;
		}
		else{
			int p=l,q=r;
			while(s[p]!=s[r])p++;
			while(s[q]!=s[l])q--;
			int n1=p-l,n2=r-q;
			if (n1<=n2){
				ans+=n1;
				for (int i=p;i>l;i--)swap(s[i],s[i-1]);
			} 
			else{
				ans+=n2;
				for (int i=q;i<r;i++)swap(s[i],s[i+1]);
			} 
			l++,r--;
		}
	} 
	printf("%lld\n",ans);
	return 0;
}