CF2008E
题意简述
对题目给出的字符串进行一下两种操作：
- 删除一个字符（只能操作一次）
- 将一个字符变为另一个。
求变成一个交替字符串最少操作次数。
Solution
我们先进行分类讨论：
当 n n n 为偶数时，由于交替字符串的长度为偶数，而只有第一个操作可以改变字符串的长度，并且只能改变一次，所以无法把一个长度为 n n n 的字符串删成一个长度为 n − 2 n-2 n−2 的字符串，故只能进行第二次操作。我们可以统计奇数位和偶数位上每个字母的数量，找到最大值分别为 m a x n 1 , m a x n 2 maxn1, maxn2 maxn1,maxn2 答案就为 n − m a x n 1 − m a x n 2 n- maxn1- maxn2 n−maxn1−maxn2。
当 n n n 为奇数时，我们枚举每个位置的字符删去后变成交替字符串所需进行操作二的次数。
令 p o s pos pos 为此时枚举到的位置， s u m f i , 0 / 1 sumf_{i,0/1} sumfi,0/1 表示下标从 1 1 1 到 p o s pos pos 字符 i i i 在偶数位 / 奇数位的数量， s u m b i , 0 / 1 sumb_{i,0/1} sumbi,0/1 表示下标从 p o s + 1 pos+1 pos+1 到 n n n 字符 i i i 在偶数位 / 奇数位的数量（由于第 p o s pos pos 个字符已经删去，所以后缀和无需统计）。
考虑到删去一个字符后， p o s pos pos 后的字符奇偶性全部改变，而之前的都不变，故令 m a x n 1 maxn1 maxn1 为删去字符后偶数位上的最大值， m a x n 2 maxn2 maxn2 为删去字符后奇数位上的最大值。
m a x n 1 = m a x ( m a x n 1 , s u m f i , 0 + s u m b i , 1 ) , m a x n 2 = max ( m a x n 2 , s u m f i , 1 + s u m b i , 0 ) maxn1= max ( maxn1,sumf_{i,0}+sumb_{i,1}), maxn2= \max (maxn2,sumf_{i,1}+sumb_{i,0}) maxn1=max(maxn1,sumfi,0+sumbi,1),maxn2=max(maxn2,sumfi,1+sumbi,0)。
统计 m a x n 1 + m a x n 2 maxn1+maxn2 maxn1+maxn2 的最大值，最后输出即可。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=26;
int sumf[M+5][2],sumb[M+5][2];
char s[N];
int t,n;
int main(){
scanf("%d",&t);
while(t--){
memset(sumf,0,sizeof(sumf));
memset(sumb,0,sizeof(sumb));
int maxn1=0,maxn2=0;
scanf("%d",&n);
scanf("%s",s+1);
if(!(n&1)){ //长度为偶数的情况
for(int i=1;i<=n;i++) sumf[s[i]-'a'+1][i&1]++;
for(int i=1;i<=M;i++) maxn1=max(maxn1,sumf[i][0]);
for(int i=1;i<=M;i++) maxn2=max(maxn2,sumf[i][1]);
printf("%d\n",n-maxn1-maxn2);
continue;
}
for(int i=1;i<=n;i++) sumb[s[i]-'a'+1][i&1]+=1;
int res=0;
for(int i=1;i<=n;i++){
maxn1=maxn2=0;
if(i>1) sumf[s[i-1]-'a'+1][i&1^1]++;
sumb[s[i]-'a'+1][i&1]--; //统计好后缀和后在枚举时逐个改变即可
for(int j=1;j<=M;j++){
maxn1=max(maxn1,sumf[j][0]+sumb[j][1]);
maxn2=max(maxn2,sumf[j][1]+sumb[j][0]);
}
res=max(res,maxn1+maxn2);
}
printf("%d\n",n-res);
}
return 0;
}