[CF] B. Ugly Pairs - Educational Codeforces Round 64 (Rated for Div. 2)
Solutions Codeforces 构造 1800 Med
Lastmod: 2025-02-05 周三 00:27:45

https://codeforces.com/contest/1156/problem/B

题目大意

给出小写字母组成的字符串 S，要求重排字符串使得相邻位置，不能是字典序相邻的字符。（‘a’ 与 ‘z’ 不相邻）。有解时输出任意合法串，否则输出 ‘No answer’。

|S|≤100

简要题解

观察：

  1. 相同字符连在一起是合法的
  2. 如果按 c - ‘a’ 的奇偶性分组那么每组内也是合法的。因为这样字符之间的距离至少为 2。
  3. 当字符种类足够多时，奇偶分完类总能有某种拼接使得结果合法

现在主要是看 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;
}
Prev: [CF] A. Inscribed Figures - Educational Codeforces Round 64 (Rated for Div. 2)
Next: [CF] E. Special Segments of Permutation - Educational Codeforces Round 64 (Rated for Div. 2)

Gitalking ...