正经题解｜字符串处理

【算法分析】

题目已经告诉这是个递归。$dfs(l,r)$ 表示处理 $l \sim r$ 的字符串。递归终止条件时当字符串长度是 $1$ 时。

【参考代码】

#include <bits/stdc++.h>
using namespace std;

char s[1100];
void dfs(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    reverse(s + l, s + mid + 1);
    dfs(l, mid);
    sort(s + mid + 1, s + r + 1);
    dfs(mid + 1, r);
}
int main() {
    int k;
    cin >> k;
    cin >> (s + 1);
    dfs(1, 1 << k);
    cout << s + 1;
    return 0;
}

【时间复杂度】

$O(2^k*log(2^k)*log(2^k))$

【预计得分】

$100pts$