题目链接：https://codeforces.com/contest/1385/problem/D
简单题意：给定一个字符串s，和good string的规则（太长了就不写了）。求至少改变多少个字符，使得s成为a-good string
直接暴力递归即可。考虑修改左边和右边分别需要的次数，取二者最小值。对于某个区间内有多少个特定字符，可以用前缀和小优化一下。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=150000+10;
int t,n,i,j,pre[30][maxn],ans;
char s[maxn];
int calc(int c,int l,int r){
if (l>r) return 0;
if (l==r) return (s[l]-‘a‘+1==c)?0:1;
int m=(l+r)/2;
int numl=n/(1<<c)-(pre[c][m]-pre[c][l-1]);
int numr=n/(1<<c)-(pre[c][r]-pre[c][m]);
return min(numl+calc(c+1,m+1,r),numr+calc(c+1,l,m));
}
int main(){
std::ios::sync_with_stdio(false);
cin>>t;
while (t--){
cin>>n;
cin>>s+1;n=strlen(s+1); //*
for (i=1;i<=26;i++){
pre[i][0]=0;
for (j=1;j<=n;j++) pre[i][j]=(s[j]-‘a‘+1==i)?pre[i][j-1]+1:pre[i][j-1];
}
cout<<calc(1,1,n)<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/13398429.html