Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)

题目大意：

让你求一个$'a'-good\quad string$，需要注意的是一个$'a'-good\quad string$是有递归定义的，也就是说要让他是一个$'a'-good\quad string$那么一半全是’$'a'$但是另一半是$'char+1'-good\quad string$。

思路

根据题目大意我们考虑进行递归求解。
$dfs(int\quad l,int\quad r,char\quad ch)$
表示的是左边界右边界和此时是$'ch'-good\quad string$，然后依次递归。

递归的边界是当$l==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