【算法分析】 题目已经告诉这是个递归。dfs(l,r)dfs(l,r)dfs(l,r) 表示处理 l∼rl \sim rl∼r 的字符串。递归终止条件时当字符串长度是 111 时。 【参考代码】 【时间复杂度】 O(2k∗log(2k)∗log(2k))O(2^k*log(2^k)*log(2^k))O(2k∗log(2k)∗log(2k)) 【预计得分】 100pts100pts100pts

#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; }

使用 string 类型，用了 reverse 和 sort 方法，代码简单明了。