自动搬运

查看原文

来自洛谷，原作者为

	tiger2005 Failure, as usual.

搬运于2025-08-24 23:03:50，当前版本为作者最后更新于2024-09-09 13:59:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题根据利用的性质不同可以衍生出各种做法。本文将尝试介绍其中一种做法。在本文中，字符串的下标从 $0$ 开始。

我们需要观察到一个明显的事实：

假设对于字符 $x$，其在 $A$ 出现了 $a$ 次，而在 $B$ 中出现了 $b$ 次，那么其在最终的 UCS 中出现了恰好 $\min(a, b)$ 次。这是因为必然存在一个长度为 $\min(a, b)$ 且全部为字符 $x$ 的公共子序列。

我们可以得到最终 UCS 的性质：

1. 对于每个字符 $x$，其在 UCS 出现的次数必然等于其在 $A$ 和 $B$ 出现次数的较小值。我们据此可以得到 UCS 的唯一长度；
2. 对于所有除了 UCS 外的公共子序列，其必须是 UCS 的一个子序列。

值得注意的是，性质 1 固定了 UCS 的长度，再通过题目给出的性质 2 可以知道满足题目条件的 UCS 是唯一的。

根据题目 Subtask 4 的约束，我们考虑将正解分为两个部分：

Step 1：通过性质 1 得到 UCS 的字符成分，再通过性质 2 的部分限制得到唯一的 UCS 候选；

Step 2：对于 UCS 候选判断性质 2 是否成立。

我们将会逐一分析这两个部分。不过在此之前，我们先给出若干定义。

Definition

我们对于 $A$ 和 $B$ 的一个公共子序列 $C_{0\cdots l}$，分别找到 $p_0 < p_1 < ... < p_l$ 以及 $q_0 < q_1 < ... < q_l$，使得 $A_{p_i} = B_{q_i} = C_i$ 成立。我们此时称序列 $p$ 和序列 $q$ 为一种 构造，而称 $(p_i, q_i)$ 为这个构造的一个 二元组。

对于字符串 $S$ 和它的某个子序列 $T$，定义 $S$ 对 $T$ 的 匹配位置 代表最小的 $p$，使得 $T$ 是字符串 $S_{0 \cdots p}$ 的子序列，而不是 $S_{0 \cdots p - 1}$ 的子序列。

Step 1

我们首先枚举所有字符 $x$，并确定其分别在 $A$ 和 $B$ 的出现次数 $a$ 和 $b$。如果 $a \leq b$，那么最终的 UCS 必然存在恰好 $a$ 个字符 $x$，并且字符串 $A$ 中字符 $x$ 出现的所有位置都会出现在 UCS 的任何一种构造中。我们称字符 $x$ 在字符串 $A$ 中出现的位置为 $A$ - 关键位置，并称字符 $x$ 为 $A$ - 关键字符。我们同理定义 $B$ - 关键位置，并且将二者统称为关键位置。

接下来是样例 1 对应的关键位置：

A: [0, 0, 1, 0, 1, 2]
                   ^
B: [2, 0, 1, 0, 2]
       ^  ^  ^

我们不妨回到 UCS 构造的性质上。根据关键位置的定义，我们可以知道：任何一个 UCS 构造中，每个二元组都恰好包含一个关键位置。另外，一个 UCS 可能包含多个构造，而为了保证在匹配的过程中不遗漏情况，我们采用和子序列匹配同等的贪心：对于两个串分别维护代表匹配位置的指针，对于 UCS 的每一个位置，判断其对应的关键位置，随后在另一个字符串上找到最靠左且字符等于当前字符的位置进行匹配，匹配位置的指针对应右移。这个贪心可以唯一确认一个构造，同时找到了字符串 $A$ 和 $B$ 对 UCS 候选的每个前缀的匹配位置。

我们对两个字符串维护一个当前匹配位置的指针，并将 UCS 置为空字符串。我们将会尝试每次在 UCS 后方追加一个关键位置，据此得到完整的 UCS 候选，或者报告没有符合条件的 UCS 候选。

假设当前两个字符串的匹配位置是 $pA$ 和 $pB$，对应的下一个关键位置为 $kA$ 和 $kB$。如果选择下一个 $A$ - 关键位置加入到 UCS 后方，则需要满足如下必要条件：

1. 下一个 $B$ - 关键位置没有被跳过，也就是字符串 $B$ 中位于 $[pB, kB)$ 的部分应当有一个字符等于 $A_{kA}$ 的位置；
2. 在完成匹配指针右移后，下一个 $B$ - 关键位置在字符串 $A$ 中拥有充足的字符用于对应，也就是字符串 $B$ 还未匹配且字符等于 $B_{kB}$ 的关键位置个数应当不多于字符串 $A$ 位于 $[kA + 1, |A|)$ 的部分中字符等于 $B_{kB}$ 的位置个数。

对于下一个 $B$ - 关键位置同理。

对于两个判断，如果都不成立，那么显然无解；如果只有一个成立，则选择对应的关键位置加入到 UCS 中，并贪心移动匹配位置指针。如果两个均成立，我们将会证明：对于最后生成的所有 UCS，总能找到 $A$ 和 $B$ 的一个公共子序列，使得其不是这个 UCS 的子序列。

证明：假设下一个 $A$ - 关键位置和 $B$ - 关键位置对应的字符分别为 $x$ 和 $y$，通过对两个判断的分析，可以发现它们组成了如下情况：

... y ... x ... y ...
        /
       /
      /
... x ... y ... x ...

不妨假设接下来被加入到 UCS 的是字符 $x$（也就是图中斜线展示的方案），且后面还有 $k$ 个字符为 $x$ 的关键字符，那么最后生成的 UCS 包含前缀 pre，紧接着的是当前加入的字符 $x$，随后是后缀 suf，其包含了恰好 $k$ 个字符 $x$。

对于这个 UCS，考虑如下构造：pre 保持相同，而下一个加入的字符是 $y$（相当于加入了↘方向的斜线，而不是↙方向的斜线）。根据加入字符 $y$ 的判断 2，如果只考虑剩余 $k+1$ 个字符等于 $x$ 的关键位置，则它们是可以匹配的，那么在最后加上 $k+1$ 个字符 $x$ 即可。通过简单的验证即可证明这个字符串是 $A$ 和 $B$ 的公共子序列，而不是 UCS 的子序列。

实际上，这个构造方案可以从样例 3 扩展得到。

我们就证明了 UCS 构造方案的唯一性，也就可以写出完整的构造算法。整个部分的复杂度可以做到 $O(n + m + \alpha)$，其中 $\alpha$ 为字符集大小。为了降低编写难度，可以选择抛弃一些讨论，在最后判断 UCS 候选是否为 $A$ 和 $B$ 的公共子序列。

Step 2

考虑如何证明 UCS 候选符合题目条件。根据题意，我们尝试找到字符串 $A$ 和字符串 $B$ 的某个子序列，使得其不是 UCS 候选的子序列，那么可以找到这个子序列当且仅当 UCS 候选不满足题目要求。根据子序列匹配的性质，我们可以将其抽象为如下问题（令 UCS 候选为字符串 $C$）：

假设初始情况下有 $cp = cq = cr = -1$，每次操作中可以选择一个字符 $x$，并将 $cp$ 更新为字符 $x$ 在字符串 $A$ 位于 $[cp+1, |A|)$ 区间的位置中第一次出现的位置，$cq$ 和 $cr$ 同理通过字符串 $B$ 和 $C$ 候选更新。那么是否存在一个操作方案，使得最后 $cr$ 无法找到符合条件的位置，而 $cp$ 和 $cq$ 可以一直找到符合条件的位置？

我们在 Step 1 的求解过程中已经求出了字符串 $A$ 和 $B$ 对 UCS 的每个前缀的匹配位置，我们在此利用这些位置，画出下面的示意图：

string A
... p_i ... p_{i+1} ... p_{i+2} ...
     |         |           |
     |         |           |
... q_i ... q_{i+1} ... q_{i+2} ...
string B

下面是样例 1 对应的示意图：

A:    0  0  1  0  1  2
      |     |  |     |
B: 2  0     1  0     2

我们称 $p_{i}$ 和 $q_{i}$ 为配对位置，而其余部分为冗余位置。根据 UCS 候选的性质，字符串 $A$ 的冗余位置只会出现 $B$ - 关键字符，字符串 $B$ 的冗余位置只会出现 $A$ - 关键字符。

我们接下来分析抽象化后的问题。我们首先指出两个性质：

性质 1：在任何时刻，只要三个位置均能匹配成功，都会有 $cp \leq p_{cr}$ 和 $cq \leq q_{cr}$ 同时成立。

以 $cp$ 为例，$cp$ 是在字符串 $A$ 中对操作方案的匹配位置，而考虑到 $C$ 对操作方案的匹配位置为 $cr$，那么操作方案就是 $C_{0\cdots cr}$ 的某个子序列，故 $cp$ 显然不会超过对 $C_{0\cdots cr}$ 本身的匹配位置，也就是 $p_{cr}$。对于 $cq$ 也是一样的。

性质 2：在任何时刻，只要三个位置均能匹配成功，并且有 $cp < p_{cr}$ 和 $cq < q_{cr}$ 同时成立，那么总能找到一个后续操作方案，使其满足要求。

考虑选择 $C_{cr\cdots |C| - 1}$ 作为后续操作方案，对于 $cr$ 而言，每次匹配需要至少增加 $1$，而接下来还需要匹配 $|C| - cr$ 次，那么最终必然不可能匹配成功；对于字符串 $A$ 和字符串 $B$，只需要选择 $p_{cr\cdots |C| - 1}$ 和 $q_{cr \cdots |C| - 1}$，即可得到等于后续操作方案的子序列，故最终必然可以匹配成功。

我们称三元组 $(cp, cq, cr)$ 为一个状态，不难发现对状态后续转移的分析和之前已经进行的操作无关。为了方便论述，我们加入定义 $p_{-1} = q_{-1} = -1$。那么我们初始的状态是 $cp = cq = cr = -1$，也就是 $cp = p_{cr}, cq = q_{cr}$。

---

情况 1：$cp = p_{cr}$ 和 $cq = q_{cr}$ 都成立。不妨假设接下来选择的是某个 $A$ - 关键字符 $x$，且 $cr$ 将会变为 $cr'$。由于在字符串 $A$ 中，$p_{cr+1\cdots cr' - 1}$ 对应的配对位置上不存在等于字符 $x$ 的位置，且冗余位置不可能存在 $x$，那么 $cp' = p_{cr'}$ 成立。而对于 $cq$，如果在 $(cq, q_{cr'})$ 区间上存在某个冗余位置 $i$ 使得 $B_i = x$，那么 $cq' = i$，否则 $cq' = q_{cr'}$。

情况 1 的状态可以生成一些情况 1 的状态，也可以生成另一些情况，下面称其为情况 2。

---

情况 2：$cp = p_{cr}$ 和 $cq = q_{cr}$ 有一个成立。不妨假设 $cp = p_{cr}$，且 $cq < q_{cr}$。假设接下来选择的是某个字符 $x$，那么对于字符串 $B$，如果在 $(cq, q_{cr}]$ 部分都不存在位置等于字符 $x$，那么当前情况将会退化为情况 1，因为对匹配的讨论和情况 1 是等价的。否则，有 $cq' \leq q_{cr}$，对于 $cp$ 而言，考虑到我们没有约定 $x$ 是不是 $A$ - 关键字符，那么 $cp'$ 可能为配对位置或者冗余位置。

1. 假如 $cp'$ 为配对位置，那么字符串 $A$ 在 $(cp, cp')$ 部分不存在等于字符 $x$ 的位置，通过简单讨论可知 $cp' = p_{cr'}$，也就是回到了情况 2；
2. 假如 $cp'$ 为冗余位置，此时将会转移到一个新的情况，我们将这个情况设定为情况 3。

情况 2 的状态只可以生成符合情况 1、情况 2 或情况 3 的某些状态。

---

情况 3：$cp$ 为冗余位置，同时 $\exists i$，使得 $cq \leq q_{i}$ 和 $p_{i} < cp$ 同时成立（对应了情况 2 时的 $cr$）。对于镜像情况讨论基本相同。根据性质 1，“$cp$ 为冗余位置”的条件蕴含了“$cr$ 无法匹配或者 $cp < p_{cr}$”的条件，那么性质 2 告诉我们，只要可以到达这个状态，就必然可以构造出符合要求的操作方案。我们也就无需进一步讨论其转移。

---

我们重新梳理一下整个讨论流程。如果我们可以在所有的状态中找到某一个状态，使得其满足情况 3 及其镜像状态，那么可以直接构造出符合要求的操作方案，进一步证明 UCS 候选不满足题目条件；否则根据转移情况，所有的状态只可能是情况 1 和情况 2 的状态，此时 $cp = p_{cr}$ 和 $cq = q_{cr}$ 至少有一个成立，可以发现 $cp$ 和 $cq$ 必然有一个随着 $cr$ 的失配而失配，也就无法找到符合要求的操作方案，UCS 候选就符合题目条件。

整道题目终于被转换为一个较为容易的版本：判断情况 3 状态是否存在。对此，考虑枚举字符串 $A$ 的所有冗余位置 $a$，并找到最大的位置 $pos$，使得 $p_{pos} < a$。预处理出字符串 $A$ 匹配到 $a$ 时，字符串 $B$ 匹配位置的最小可能值 $b$。那么只要检查 $b \leq q_{pos}$ 是否成立即可。最后需要交换两个字符串再做一次。

预处理部分可以使用树状数组或者单调栈算出，时间复杂度 $O((n + m) \log \min(n, m)+ \alpha)$。

#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

const int ALPHABET = 200001;

// ensure linear complexity of Step 1
struct JumpList {
  vector<int> O;
  vector<int> nxt;
  vector<int> alphab;
  vector<int> cnt;
  int n;
  int pos;
  JumpList(const vector<int> &T): O(T) {
    n = T.size();
    pos = 0;
    nxt.resize(n + 1);
    cnt.resize(n + 1);
    alphab.assign(ALPHABET, n);
    for (int i = n - 1; i >= 0; i --) {
      nxt[i] = alphab[T[i]];
      cnt[i] = cnt[nxt[i]] + 1;
      alphab[T[i]] = i;
    }
  }
  void step() {
    alphab[O[pos]] = nxt[pos];
    ++ pos;
  }
  void moveTo(int npos) {
    while (pos < npos)
      step();
  }
  void matchAlpha(int u) {
    moveTo(alphab[u] + 1);
  }
  int next(int u) {
    return alphab[u];
  }
  int count(int u) {
    return cnt[alphab[u]];
  }
};

vector<int> construct(const vector<int> &A, const vector<int> &B, vector<int> &P, vector<int> &Q) {
  int n = A.size(), m = B.size();
  vector<int> C;
  vector<int> cntA(ALPHABET), cntB(ALPHABET);
  for (auto e: A)
    ++ cntA[e];
  for (auto e: B)
    ++ cntB[e];
  vector<int> posA, posB;
  for (int i = 0; i < n; i ++)
    if (cntA[A[i]] <= cntB[A[i]])
      posA.push_back(i);
  for (int i = 0; i < m; i ++)
    if (cntB[B[i]] < cntA[B[i]])
      posB.push_back(i);
  posA.push_back(n);
  posB.push_back(m);

  JumpList curA(A), curB(B);
  JumpList forwA = curA, forwB = curB;
  forwA.moveTo(posA[0]);
  forwB.moveTo(posB[0]);
  auto pA = posA.begin(), pB = posB.begin();

  while (*pA != n || *pB != m) {
    bool flg1 = true, flg2 = true;
    if (*pA != n) {
      flg1 &= curB.count(A[*pA]) > forwB.count(A[*pA]);
      flg2 &= forwB.count(A[*pA]) >= forwA.count(A[*pA]);
    }
    else
      flg1 = false;
    if (*pB != m) {
      flg2 &= curA.count(B[*pB]) > forwA.count(B[*pB]);
      flg1 &= forwA.count(B[*pB]) >= forwB.count(B[*pB]);
    }
    else
      flg2 = false;
    if (!(flg1 ^ flg2))
      return {-1};
    if (flg1) {
      C.push_back(A[*pA]);
      curB.matchAlpha(A[*pA]);
      swap(forwA, curA);
      curA.step();
      forwA.moveTo(*(++ pA));
    }
    else {
      C.push_back(B[*pB]);
      curA.matchAlpha(B[*pB]);
      swap(forwB, curB);
      curB.step();
      forwB.moveTo(*(++ pB));
    }
    P.push_back(curA.pos - 1);
    Q.push_back(curB.pos - 1);
  }
  return C;
}

vector<int> preMatch(const vector<int> &A, const vector<int> &B) {
  int n = A.size(), m = B.size();
  vector<vector<int>> appear(ALPHABET);
  for (int i = 0; i < m; i ++)
    appear[B[i]].push_back(i);
  for (int i = 0; i < ALPHABET; i ++)
    appear[i].push_back(m);

  vector<pair<int, int>> stk;
  stk.push_back({-1, -1});
  vector<int> lastCh(ALPHABET, -1), res;
  for (int i = 0; i < n; i ++) {
    int num = lower_bound(stk.begin(), stk.end(), pair<int, int>{lastCh[A[i]], -1}) -> second;
    if (num != m)
      num = *lower_bound(appear[A[i]].begin(), appear[A[i]].end(), num + 1);
    res.push_back(num);
    while (stk.back().second >= num)
      stk.pop_back();
    stk.push_back({i, num});
    lastCh[A[i]] = i;
  }
  return res;
}

bool check(const vector<int> &A, const vector<int> &B, const vector<int> &T, const vector<int> &P, const vector<int> &Q) {
  int n = A.size(), m = B.size(), c = T.size();
  vector<int> pMatch = preMatch(A, B);
  vector<int> matchA(n, -1);
  vector<int> prvMatch(n + 1, -1);
  for (int i = 0; i < c; i ++)
    matchA[P[i]] = i, prvMatch[P[i] + 1] = i;
  for (int i = 1; i < n; i ++) if (prvMatch[i] == -1)
    prvMatch[i] = prvMatch[i - 1];
  for (int i = 0; i < n; i ++)
    if (matchA[i] == -1 && prvMatch[i] != -1 && pMatch[i] <= Q[prvMatch[i]])
      return false;
  return true;
}

vector<int> ucs(vector<int> A, vector<int> B) {
  vector<int> P, Q;
  auto res = construct(A, B, P, Q);
  if (res == vector<int>{-1}
    || !check(A, B, res, P, Q) || !check(B, A, res, Q, P))
    return {-1};
  return res;
}