IOI2024 D2T1 sol
这道题根据利用的性质不同可以衍生出各种做法。本文将尝试介绍其中一种做法。在本文中，字符串的下标从
我们需要观察到一个明显的事实：
假设对于字符
x ，其在A 出现了a 次，而在B 中出现了b 次，那么其在最终的 UCS 中出现了恰好\min(a, b) 次。这是因为必然存在一个长度为\min(a, b) 且全部为字符x 的公共子序列。
我们可以得到最终 UCS 的性质：
- 对于每个字符
x ，其在 UCS 出现的次数必然等于其在A 和B 出现次数的较小值。我们据此可以得到 UCS 的唯一长度； - 对于所有除了 UCS 外的公共子序列，其必须是 UCS 的一个子序列。
值得注意的是，性质 1 固定了 UCS 的长度，再通过题目给出的性质 2 可以知道满足题目条件的 UCS 是唯一的。
根据题目 Subtask 4 的约束，我们考虑将正解分为两个部分：
Step 1：通过性质 1 得到 UCS 的字符成分，再通过性质 2 的部分限制得到唯一的 UCS 候选；
Step 2：对于 UCS 候选判断性质 2 是否成立。
我们将会逐一分析这两个部分。不过在此之前，我们先给出若干定义。
Definition
我们对于
对于字符串
Step 1
我们首先枚举所有字符
接下来是样例 1 对应的关键位置：
A: [0, 0, 1, 0, 1, 2]
^
B: [2, 0, 1, 0, 2]
^ ^ ^我们不妨回到 UCS 构造的性质上。根据关键位置的定义，我们可以知道：任何一个 UCS 构造中，每个二元组都恰好包含一个关键位置。另外，一个 UCS 可能包含多个构造，而为了保证在匹配的过程中不遗漏情况，我们采用和子序列匹配同等的贪心：对于两个串分别维护代表匹配位置的指针，对于 UCS 的每一个位置，判断其对应的关键位置，随后在另一个字符串上找到最靠左且字符等于当前字符的位置进行匹配，匹配位置的指针对应右移。这个贪心可以唯一确认一个构造，同时找到了字符串
我们对两个字符串维护一个当前匹配位置的指针，并将 UCS 置为空字符串。我们将会尝试每次在 UCS 后方追加一个关键位置，据此得到完整的 UCS 候选，或者报告没有符合条件的 UCS 候选。
假设当前两个字符串的匹配位置是
- 下一个
B - 关键位置没有被跳过，也就是字符串B 中位于[pB, kB) 的部分应当有一个字符等于A_{kA} 的位置； - 在完成匹配指针右移后，下一个
B - 关键位置在字符串A 中拥有充足的字符用于对应，也就是字符串B 还未匹配且字符等于B_{kB} 的关键位置个数应当不多于字符串A 位于[kA + 1, |A|) 的部分中字符等于B_{kB} 的位置个数。
对于下一个
对于两个判断，如果都不成立，那么显然无解；如果只有一个成立，则选择对应的关键位置加入到 UCS 中，并贪心移动匹配位置指针。如果两个均成立，我们将会证明：对于最后生成的所有 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 构造方案的唯一性，也就可以写出完整的构造算法。整个部分的复杂度可以做到
Step 2
考虑如何证明 UCS 候选符合题目条件。根据题意，我们尝试找到字符串
假设初始情况下有
cp = cq = cr = -1 ，每次操作中可以选择一个字符x ，并将cp 更新为字符x 在字符串A 位于[cp+1, |A|) 区间的位置中第一次出现的位置，cq 和cr 同理通过字符串B 和C 候选更新。那么是否存在一个操作方案，使得最后cr 无法找到符合条件的位置，而cp 和cq 可以一直找到符合条件的位置？
我们在 Step 1 的求解过程中已经求出了字符串
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我们称
我们接下来分析抽象化后的问题。我们首先指出两个性质：
性质 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} ，即可得到等于后续操作方案的子序列，故最终必然可以匹配成功。
我们称三元组
情况 1：
情况 1 的状态可以生成一些情况 1 的状态，也可以生成另一些情况，下面称其为情况 2。
情况 2：
- 假如
cp' 为配对位置，那么字符串A 在(cp, cp') 部分不存在等于字符x 的位置，通过简单讨论可知cp' = p_{cr'} ，也就是回到了情况 2； - 假如
cp' 为冗余位置，此时将会转移到一个新的情况，我们将这个情况设定为情况 3。
情况 2 的状态只可以生成符合情况 1、情况 2 或情况 3 的某些状态。
情况 3：
我们重新梳理一下整个讨论流程。如果我们可以在所有的状态中找到某一个状态，使得其满足情况 3 及其镜像状态，那么可以直接构造出符合要求的操作方案，进一步证明 UCS 候选不满足题目条件；否则根据转移情况，所有的状态只可能是情况 1 和情况 2 的状态，此时
整道题目终于被转换为一个较为容易的版本：判断情况 3 状态是否存在。对此，考虑枚举字符串
预处理部分可以使用树状数组或者单调栈算出，时间复杂度
#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;
}