CF1385D a-Good String 题解

题目链接：a-Good String

题意：

定义：字符串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-好串。

额，不知道这题要讲什么，就是一道简单的分治题，只要按照题目意思就好了。

时间复杂度 \(\mathcal{O}(n \log n)\) ，计算详见主定理（本题唯一难点？）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

char s[N];
int work(int l, int r, char c)
{
    if(l == r) return s[l] != c;
    int r1 = 0, r2 = 0, mid = (l + r) >> 1;
    for(int i = l; i <= mid; i++) if(s[i] != c) ++r1;
    for(int i = mid + 1; i <= r; i++) if(s[i] != c) ++r2;
    return min(r2 + work(l, mid, c + 1), r1 + work(mid + 1, r, c + 1));
}
void solve()
{
    int n; cin >> n >> (s + 1);
    cout << work(1, n, 'a') << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}