题目大意：
让你求一个′a′−goodstring'a'-good\quad string，需要注意的是一个′a′−goodstring'a'-good\quad string是有递归定义的，也就是说要让他是一个′a′−goodstring'a'-good\quad string那么一半全是’′a′'a'但是另一半是′char+1′−goodstring'char+1'-good\quad string。
思路
根据题目大意我们考虑进行递归求解。
dfs(intl,intr,charch)
dfs(int\quad l,int\quad r,char\quad ch)
表示的是左边界右边界和此时是′ch′−goodstring'ch'-good\quad string，然后依次递归。
递归的边界是当l==rl==r时，此时我们开始回溯。全程更新最小操作值即可。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
//#define int long long
#define lson rt<<1
#define rson rt<<1|1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 1e6 + 10;
int n;
char str[maxn];
int dfs(int l,int r,char ch){
if(l==r){
return str[l]==ch?0:1;
}
int mid=l+r>>1;
int left=0,right=0;
for(int i=l;i<=mid;++i){
left+=str[i]==ch?0:1;
}
for(int i=mid+1;i<=r;++i){
right+=str[i]==ch?0:1;
}
return min(left+dfs(mid+1,r,ch+1),dfs(l,mid,ch+1)+right);
}
void solve() {
scanf("%d",&n);getchar();
scanf("%s",str+1);
printf("%d\n",dfs(1,n,'a'));
}
signed main() {
int __;
// cin >> __;
scanf("%d",&__);
while(__--) {
solve();
}
}
D. a-Good String
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a string s[1…n] consisting of lowercase Latin letters. It is guaranteed that n=2k for some integer k≥0.
The string s[1…n] is called c-good if at least one of the following three conditions is satisfied:
The length of s is 1, and it consists of the character c (i.e. s1=c);
The length of s is greater than 1, the first half of the string consists of only the character c (i.e. s1=s2=⋯=sn2=c) and the second half of the string (i.e. the string sn2+1sn2+2…sn) is a (c+1)-good string;
The length of s is greater than 1, the second half of the string consists of only the character c (i.e. sn2+1=sn2+2=⋯=sn=c) and the first half of the string (i.e. the string s1s2…sn2) is a (c+1)-good string.
For example: “aabc” is ‘a’-good, “ffgheeee” is ‘e’-good.
In one move, you can choose one index i from 1 to n and replace si with any lowercase Latin letter (any character from ‘a’ to ‘z’).
Your task is to find the minimum number of moves required to obtain an ‘a’-good string from s (i.e. c-good string for c= ‘a’). It is guaranteed that the answer always exists.
You have to answer t independent test cases.
Another example of an ‘a’-good string is as follows. Consider the string s=“cdbbaaaa”. It is an ‘a’-good string, because:
the second half of the string (“aaaa”) consists of only the character ‘a’;
the first half of the string (“cdbb”) is ‘b’-good string, because:
the second half of the string (“bb”) consists of only the character ‘b’;
the first half of the string (“cd”) is ‘c’-good string, because:
the first half of the string (“c”) consists of only the character ‘c’;
the second half of the string (“d”) is ‘d’-good string.
Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1≤n≤131 072) — the length of s. It is guaranteed that n=2k for some integer k≥0. The second line of the test case contains the string s consisting of n lowercase Latin letters.
It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).
Output
For each test case, print the answer — the minimum number of moves required to obtain an ‘a’-good string from s (i.e. c-good string with c= ‘a’). It is guaranteed that the answer exists.
本文地址：https://blog.csdn.net/weixin_45628245/article/details/107584206
