欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-12-02 16:14:10
题目大意:让你求一个′a′−goodstring'a'-good\quad string′a′−goodstring,需要注意的是一个′a′−goodstring'a'-good\quad string′a′−goodstring是有递归定义的,也就是说要让他是一个′a′−goodstring'a'-good\quad string′a′−goodstring那么一半全是’′a′'a'′a′但是另一半是′char+1′−goodstring'char+1'-good\quad string′char+1′...

题目大意:

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

思路

根据题目大意我们考虑进行递归求解。
dfs(intl,intr,charch) dfs(int\quad l,int\quad r,char\quad ch)
表示的是左边界右边界和此时是chgoodstring'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

相关标签: 题解 算法