CF578E Walking! 题解

Description

• 给定一个长度为 $n$ 的只包含 L,R 的字符串 $s$。
• 构造一个 $n$ 排列 $p$ 满足 $s[p_i] \ne s[p_{i+1}](1 \le i < n)$。
• 最小化 $p$ 中 $p_i > p_{i+1}(1 \le i < n)$ 的数量。
• $n \le 10^5$，数据保证有解。

Solution

考虑把 $p$ 中的每个极长连续上升子序列拿出来，显然这些子序列为 $1,2,\ldots,n$ 的一个划分，使得每个子序列一定是 LR 交错出现。

所以第一问的答案为把 $1,2,\ldots,n$ 划分成最少的子序列数$-1$，使得每个子序列是 LR 交错出现。

有一个显然的贪心策略是从前往后扫，不妨设 $s_i$ 为 L，如果 $s_i$ 能找到末尾与其不同的子序列就把它加到那个子序列末尾，如果找不到就创建一个新的子序列。

证明就考虑如果能找到但是不加，就说明当前答案会 $+1$，如果加了顶多是后面的一个 R 找不到 L 与其配对，也只会 $+1$，并且在这之前答案一直更优。

然后需要构造方案，用 $cnt_{ij}$ 表示开头为 $i$，末尾为 $j$ 的子序列数量。

容易发现当 $cnt_{LR},cnt_{RL}\neq 0,cnt_{LL}=cnt_{RR}=0$ 时是无法直接构造方案的，这时可以任意取一对 LR 和 RL 的序列，把末尾更靠后的那个序列的末尾放到另一个序列的末尾，这样就有了 LL 和 RR。

注意到 $|cnt_{LL}-cnt_{RR}|\leq 1$，不妨设 $cnt_{LL}\geq cnt_{RR}$，可以构造：LR、LR、…、LR、LL、RL、RL、…、RL、RR、LL、RR、LL、…

时间复杂度：$O(n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int n, tot;
std::string str;
std::vector<int> vec[2], vv[kMaxN], id[2][2];

void fix() {
  int x = id[0][1].back(), y = id[1][0].back();
  id[0][1].pop_back(), id[1][0].pop_back();
  if (vv[x].back() < vv[y].back()) std::swap(x, y);
  vv[y].emplace_back(vv[x].back()), vv[x].pop_back();
  id[str[vv[x].front()] == 'R'][str[vv[x].back()] == 'R'].emplace_back(x);
  id[str[vv[y].front()] == 'R'][str[vv[y].back()] == 'R'].emplace_back(y);
}

void print(int x) {
  for (auto i : vv[x]) std::cout << i << ' ';
}

void dickdreamer() {
  std::cin >> str;
  n = str.size(); str = " " + str;
  for (int i = 1; i <= n; ++i) {
    int c = (str[i] == 'R');
    if (!vec[c ^ 1].size()) {
      vec[c].emplace_back(++tot);
      vv[tot] = {i};
    } else {
      int t = vec[c ^ 1].back(); vec[c ^ 1].pop_back();
      vv[t].emplace_back(i), vec[c].emplace_back(t);
    }
  }
  std::cout << tot - 1 << '\n';
  for (int i = 1; i <= tot; ++i)
    id[str[vv[i].front()] == 'R'][str[vv[i].back()] == 'R'].emplace_back(i);
  if (id[0][1].size() && id[1][0].size() && !id[0][0].size() && !id[1][1].size()) fix();
  int o = 0;
  if (id[0][0].size() < id[1][1].size()) o = 1;
  for (auto x : id[o][o ^ 1]) print(x);
  if (id[o][o].size()) print(id[o][o].front());
  for (auto x : id[o ^ 1][o]) print(x);
  for (int i = 0; i < (int)id[o ^ 1][o ^ 1].size(); ++i) {
    print(id[o ^ 1][o ^ 1][i]);
    if (i + 1 < (int)id[o][o].size()) print(id[o][o][i + 1]);
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}