-
题意:有一个长度为\(n=2^k\)的字符串,对于某个字符\(c\),我们定义他是一个\(c-good\),如果:
1.\(len=1\),并且\(s[1]=c\).
2.\(len>1\),\(s[1]=s[2]=...=s[\frac{len}{2}]=c\),并且另外一半是一个\((c+1)-good\)字符串.
3.\(len>1\),\(s[\frac{len}{2}+1]=s[\frac{len}{2}+2]=...=s[len]=c\),并且另外一半是一个\((c+1)-good\)字符串.
你可以修改字符串的任意字符,使得它是一个\('a'-good\)字符串,求最少的修改次数.
-
题解:根据题意,如果想得到要求的字符串,那么我们每次都要对半分,使得一半全是相等的,另一半再继续对半分执行同样的操作,直到分完.那么这个过程我们就可以用dfs来搞.
首先我们dfs字符串\(s\),使得一半全是\('a'\),因为刚开始操作数是\(0\),所以\(dfs(s,'a',0)\),之后,我们将字符串\(s\)分成两半,分别统计变成全相等字符的次数,统计完后,我们再dfs剩下的另一半,这时候,我们要让\(c+1\),并且把统计的状态带入下一层,所以是\(dfs(tmp,c+1,cnt)\),当字符串长度为\(1\)时,我们只需要判断它是否是我们所需要的字符,然后维护答案的最小值即可返回上一层.
-
代码:
int t;
int n;
int ans=INF;
int cnt;
string s; void dfs(string q,char c,int cnt){
int len=q.size();
int res=cnt;
if(len==1){
if(q[0]!=c) cnt++;
ans=min(ans,cnt);
return;
}
for(int i=0;i<len/2;++i){
if(q[i]!=c) cnt++;
}
string tmp=q.substr(len/2,len/2);
dfs(tmp,c+1,cnt);
cnt=res;
for(int i=len/2;i<len;++i){
if(q[i]!=c) cnt++;
}
tmp=q.substr(0,len/2);
dfs(tmp,c+1,cnt);
return ;
} int main() {
ios::sync_with_stdio(false);cin.tie(0);
cin>>t;
while(t--){
cin>>n>>s;
ans=INF;
dfs(s,'a',0); cout<<ans<<endl;
} return 0;
}