爱站程序员基地原题链接：https://codeforces.com/contest/1385/problem/D
题意：给你一个由小写拉丁字母组成的字符串s[1…n]。对于某个k≥0的整数，保证n=2k。
如果满足以下三个条件中的至少一个，则字符串s[1…n]称为c-good：
s的长度为1，由字符c组成（即s1=c）；
s的长度大于1，字符串的前半部分只包含字符c（即s1=s2=⋯=sn2=c），而字符串的后半部分（即字符串sn2+1sn2+2…sn）是（c+1）-好字符串；
s的长度大于1，字符串的后半部分只包含字符c（即sn2+1=sn2+2=⋯=sn=c），字符串的前半部分（即字符串s1s2…sn2）是（c+1）-好字符串。
例如：“aabc”是“a”-好，“ffgheeee”是“e”-好。
我们可以进行一次改写操作，将任意一个字符改成我们想要的字符，给你一个字符串，问让它成为一个’a’-good字符串的最小操作次数。
解题思路：这题有着明显的递归分治的解题气息。我们这样来思考一下：针对一个’a’-good字符串它的条件就是左半部分全为a，右半部分为’a+1’-good字符串或者右半部分全为a，左半部分为’a+1’-good字符串。对于’a+1’字符串也是如此，所以我们解决将一个字符串变为一个’a’-good字符串的大问题就可以不断拆分，拆成最后只剩一个’c’字符了，当然我们拆分问题肯定是要按照题意来的，题意是分为了左半部分和右半部分，我们自然也要这样分，分的过程我们要统计至少要进行多少次改写操作，即每次取得小问题的最优解，最后组合在一个的一定是最优解。我们这里有两条路径，要注意从两条路径开始出发。OK我们具体看代码。
AC代码：
/**邮箱：[email protected]*blog:https://me.csdn.net/hzf0701*注：文章若有任何问题请私信我或评论区留言，谢谢支持。**/#include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define fi first#define se second#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大const int maxn = 2e7;//最大值。typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;typedef pair<int, int> pii;//*******************************分割线，以上为自定义代码模板***************************************//char str[maxn];int solve(int l,int r,char c){if(l==r){//说明符合要求，我们只需要将这个字符变为c字符即可。return str[l]!=c;}int cnt1=0,cnt2=0,mid=(l+r)>>1;//将左半区间或者将右半区间变成c字符。rep(i,l,mid){if(str[i]!=c)cnt1++;}rep(i,mid+1,r){if(str[i]!=c)cnt2++;}cnt1+=solve(mid+1,r,c+1);//左右递归cnt2+=solve(l,mid,c+1); //左右递归return min(cnt1,cnt2); //得到最优方案。}int main(){//freopen(\"in.txt\", \"r\", stdin);//提交的时候要注释掉IOS;int t,n;//t组测试用例，n为字符串的长度。while(cin>>t){while(t--){cin>>n>>str;cout<<solve(0,n-1,\'a\')<<endl;}}return 0;}
