题意
给定一个长度为 \(n\) 的字符串 \(s\) 和一个正整数 \(k\)，每次可以进行如下两种操作当中的一种（字符串下标从 \(1\) 开始标号）：
- 选择 \(i \in \left[1, n - 2\right]\) 并交换 \(s_i\) 和 \(s_{i + 2}\)；
- 选择 \(i \in \left[1, n - k + 4\right]\) 并反转区间 \(\left[i, i + k - 1\right]\)。
不限操作次数，询问经过若干操作（可以不执行操作）可以得到的字典序最小的字符串。
数据范围：
- \(1 \le t \le 10^4\)；
- \(1 \le k < n \le 10^5\)；
- \(\sum n \le 10^5\)。
题解
将字符串按下标奇偶性划分为两个字符集，可以发现通过第一种操作可以将两个字符集内的元素分别排序至字典序最小。考虑如果最终结果可以更优，那么需要实现两个字符集元素的交换。
发现如果区间长度为奇数，那么通过第二种操作无法交换两个字符集的元素，所以无法达到更优结果；反之可以交换两个字符集内的元素，可以达到更优的结果，显然这个更优结果为整个字符串的字符集按字典序排序后的字符串。
按 \(k\) 的奇偶性分类讨论后排序即可，复杂度 \(\mathcal{O}(n \log n)\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef char charType;
typedef std::vector<charType> string;
int main() {
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N, K;
std::cin >> N >> K;
string S(N);
for (valueType i = 0; i < N; ++i)
std::cin >> S[i];
if (std::__gcd(K - 1, 2) == 1) {
std::sort(S.begin(), S.end());
for (auto const &iter: S)
std::cout << iter;
std::cout << '\n';
continue;
} else {
string odd, even;
for (valueType i = 0; i < N; ++i) {
if (i % 2 == 0)
even.push_back(S[i]);
else
odd.push_back(S[i]);
}
std::sort(odd.begin(), odd.end());
std::sort(even.begin(), even.end());
for (valueType i = 0; i < N; ++i) {
if (i % 2 == 0)
std::cout << even[i / 2];
else
std::cout << odd[i / 2];
}
std::cout << '\n';
continue;
}
}
std::cout << std::flush;
return 0;
}