https://codeforces.com/contest/1156/problem/B
题目大意
给出小写字母组成的字符串 $S$，要求重排字符串使得相邻位置，不能是字典序相邻的字符。（‘a’ 与 ‘z’ 不相邻）。有解时输出任意合法串，否则输出 ‘No answer’。
$|S| \le 100$
简要题解
观察：
- 相同字符连在一起是合法的
- 如果按 $c - ‘a’$ 的奇偶性分组那么每组内也是合法的。因为这样字符之间的距离至少为 $2$。
- 当字符种类足够多时，奇偶分完类总能有某种拼接使得结果合法
现在主要是看 $3$。
只有一组时，总是成立的，以下讨论都不赘述。
设字符种类数为 $m$ 则当 $m \ge 5$ 时对于较多的组我们有 $max(c_i) - min(c_i) \ge 4$。也就是说，短的组的开头元素，不可能同时和长的一组的最大最小元素都距离为 $1$。
当 $m = 4$ 时，简单讨论一下，其实要么两组长度是 $1, 3$ 要么是 $2, 2$ 其实也总是有解的。但我们也可以将其归类为 $3$ 以下的可能无解的情况直接暴力。
void solve() {
string s; cin >> s;
map<char, int> cnt;
for (char c : s) cnt[c]++;
auto check = [&](char a, char b) -> bool {
return abs(a - b) == 1;
};
vector<char> vis;
for (auto [v, c] : cnt) {
vis.push_back(v);
}
int m = vis.size();
vector<char> ord;
if (m <= 3) {
vector<int> p(m);
iota(p.begin(), p.end(), 0);
int f = 0;
ord.resize(m);
do {
for (int i = 0; i < m; i++) {
ord[i] = vis[p[i]];
}
int ff = 1;
for (int i = 1; i < m; i++) {
if (check(ord[i - 1], ord[i])) {
ff = 0;
break;
}
}
if (ff) {
f = 1;
break;
}
} while (next_permutation(p.begin(), p.end()));
if (!f) {
cout << "No answer\n";
return;
}
} else {
vector<char> odd, even;
for (char c : vis) {
if ((c - 'a') & 1) {
odd.push_back(c);
} else {
even.push_back(c);
}
}
if (odd.empty()) {
ord = even;
} else if (even.empty()) {
ord = odd;
} else {
int f = 0;
int m0 = even.size(), m1 = odd.size();
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (!check(odd[m1 - 1], even[0])) {
f = 1;
break;
}
reverse(even.begin(), even.end());
}
if (f) break;
reverse(odd.begin(), odd.end());
}
for (char c : odd) ord.push_back(c);
for (char c : even) ord.push_back(c);
}
}
for (auto c: ord) {
int cc = cnt[c];
for (int i = 0; i < cc; i++) {
cout << c;
}
}
cout << '\n';
}
下面假定这两组字符为 $a, b$。
对于 $m = 4$，如果是 $1, 3$ 分，显然总有 $1$ 放在 $3$ 的那种开头或结束是成立的（和 $m \ge 5$ 是一样的）。如果是 $2, 2$ 分，假设四个值是 $a_0, a_1, b_0, b_1$，显然，如果 $|a_0 - b_0| \neq 1$ 或者 $|a_0 - b_1| \neq 1$ 我们已经找到了所有解，否则假设 $b_0 + 1 = a_0 = b_1 - 1$ 此时必有 $a_1 \le b_0 - 1$ 或者 $a_1 \ge b_1 + 1$。前者 $|a_1 - b_1| \neq 1$ 后者 $|a_1 - b_0| \neq 1$ 则总有解。
仔细研究一下，$m = 3$ 的不行的情况，其实对应了 $b_0 + 1 = a_0 = b_1 - 1$ 也就是三个字符是连续的情况，显然中间字符放在任何位置都是不合法的。其余情况如果 $a_0$ 放于中间合法，则放于两头也合法。
$m = 2$ 相当于只有一种放法。
我们注意到所有情况相当于都只需要检查 $a, b$ 不同的开头结尾相连的所有情况。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
string s; cin >> s;
map<char, int> cnt;
for (char c : s) cnt[c]++;
auto check = [&](char a, char b) -> bool {
return abs(a - b) == 1;
};
vector<char> ord;
vector<char> odd, even;
for (auto [c, v] : cnt) {
if ((c - 'a') & 1) {
odd.push_back(c);
} else {
even.push_back(c);
}
}
int f = 0;
if (odd.empty()) {
ord = even;
f = 1;
} else if (even.empty()) {
ord = odd;
f = 1;
} else {
int m1 = odd.size();
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (!check(odd[m1 - 1], even[0])) {
f = 1;
break;
}
reverse(even.begin(), even.end());
}
if (f) break;
reverse(odd.begin(), odd.end());
}
for (char c : odd) ord.push_back(c);
for (char c : even) ord.push_back(c);
}
if (!f) {
cout << "No answer\n";
return;
}
for (auto c: ord) {
int cc = cnt[c];
for (int i = 0; i < cc; i++) {
cout << c;
}
}
cout << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Special Segments of Permutation - Educational Codeforces Round 64 (Rated for Div. 2)