题解 CF1385D 【a-Good String】

• 2020 年 7 月 19 日
• 笔记
• CF, 字符串, 模拟, 题解

传送门

题意

定义：字符串s 为一个c-好串（c 为一个字符）时，必须满足：

1. 当\(|s| = 1\) ，\(s = c\)

2. 当\(|s| > 1\), \(s\) 的左半部分为全为 \(c\)，右半部分为一个 (c+1)-好串 或者 \(s\) 的右半部分为全为 \(c\)，左半部分为一个 (c+1)-好串

其中 \(|s|\) 代表 字符串 \(s\) 的长度。

举个例子：当 \(s=“cdbbaaaa”\)时，\(s\) 是一个 a-好串

现在，给你一个字符串 \(s\) ( \(|s| = 2^k\) ),问最少替换多少个字符，使其为一个 a-好串。

思路

我们可以按照题意递归求解。

返回边界 ： 当前串长度为 1

每次将串分成左右两部分，分类讨论，最后取最小值作为答案。

具体见代码。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>

#define ll long long
using namespace std;

const int MAXN = 131075;
int n;
char s[MAXN];
// getans 代表将[l,r] 变为一个 c-好串 所需最小改动
int getans(int l,int r,char c){
	if(l==r) return s[l]!=c; // 如果该串已经符合要求，则不需要改动，返回 0
	int tot1 = 0,tot2 = 0;
	int mid = (l+r)>>1;
	for(int i = l;i <= mid;i++) if(s[i]!=c) tot1++;
	for(int i = mid+1;i <= r;i++) if(s[i]!=c) tot2++;
	tot1 += getans(mid+1,r,c+1);
	tot2 += getans(l,mid,c+1);
	return min(tot1,tot2);
// tot1 代表将左区间全变为 c， 右区间变为一个c+1 好串所需最小改动
// tot2 代表将右区间全变为 c， 左区间变为一个c+1 好串所需最小改动
}
int main (){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		scanf("%s",s+1);
		printf("%d\n",getans(1,n,'a'));
	}
}