算法竞赛比赛记录: IOI 2024

象形文字序列

首先需要观察到一个性质：

UCS 的长度

令字符集合 $S$ ，对于某个字符 $s\in S$ ，其在 $A$ 中出现 $C_A(s)$ 次，在 $B$ 中出现 $C_B(s)$ 次，则 UCS 的长度必须为

\sum_{s\in S} \min(C_A(s), C_B(s))

【简要证明】不妨 $C_A(s)\le C_B(s)$ ，如果 UCS 里 $s$ 只出现了 $C_A(s)-1$ 次，那么由于 $\underbrace{ss\dots s}_{C_A(s)}$ 是 $A,B$ 共同的子串，但是并不是 UCS 的子串，这与 UCS 的定义矛盾。因此 UCS 的长度其实是可以确定的。

那么，既然我们知道了 UCS 的字符构成，我们开始思考怎么去从给定的字符中构造 UCS. 由于字符串长度较长，所以应该是 $O(n)$ 或者 $O(n\log n)$ 的构造。

如果对于某个字符 $s\in S$ 且 $C_A(s)\le C_B(s)$ ，就说明 UCS 里出现的所有 $s$ 刚好和 $A$ 全部匹配上，把 $s$ 在 $A$ 里所有出现的位置记为 $s$ -critical-in- $A$ . 类似地有 $s$ -critical-in- $B$ . 把 $s$ 记为 critical char of $A/B$ ， $s$ 在 $A,B$ 里面的下标记为 critical position.

尝试一下“贪心构造再检查”的策略，那就是考虑怎么把 critical char of $A,B$ 放入 UCS. 同时我们要考虑到 critical char 之间的顺序：例如样例一， $A$ 的 critical char 为 $0,1,0,2$ ，那么 UCS 里就不能是 $2,0,1,0$ （不然的话 $2$ -critical-in- $A$ 就无法匹配了）。

由此我们得到了一个贪心的重要依据：字符串 $A,B$ 里的 critical char 必须按照这个 char 在 $A/B$ 内的顺序进行排列，也就是类似于双指针排序的过程（如果 $s_1$ 在 $A$ 字符串里排在 $s_2$ 前面，那么 $s_1$ 在 UCS 里也必须排在 $s_2$ 前面）。

所以，我们可以用双指针指向 $A,B$ ’s critical positions of $s$ ，每次判断该放 critical char of $B$ 还是 of $A$ .

然后，我们考虑如何判断。假设已经有了一段 UCS，分别匹配了前缀 $A[1,i],B[1,j]$ ，当前的 critical position of $A,B$ 分别为 $k_A,k_B$ . 如果 $A[k_A]$ 上的字符可以放入 UCS，那么：

$B[j,k_B-1]$ 这一段子串里，应该有一个字符等于 $A[k_A]$ ，这样才能匹配上并且 $k_B$ 这个字符不会被跳过（被跳过就无法放入 UCS 了）
放入 $A[k_A]$ 后，UCS 匹配的前缀是 $A[1,k_A]$ 。为了让 $B[k_B]$ 也能够完成匹配，在 $A[k_A+1, \texttt{end}]$ 这段后缀里，应该有足够多的字符让 $B$ ’s remaining critical chars 匹配。

对 $B[k_B]$ 也是同理。

如果都不能放，那么 UCS 无解。如果都可以放，那么也就是说， $A,B$ 之间有两个子序列，一个子序列在这个位置是 $A[k_A]$ 另一个却是 $B[k_B]$ （这两个字符不一样），而且长度还都是一样的，这样的情况下，这两个子序列不可能同时是 UCS 的子序列，所以也无解。

构造出 UCS 后，我们再来检查构造出来的 UCS 是否合法。对 $i\in [1,n]$ ，我们处理出对应的 $\min j$ 使得 $A[1,i]$ 可以匹配 $B[1,j]$ 而无法匹配 $B[1,j-1]$ . (prepare())

Code

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using vi        = std::vector<int>;
constexpr int V = 2e5 + 5;

struct Sequence {
    int length;
    int pos;

    vi first_of;
    vi next_same;
    vi count_same;
    vi data;

    Sequence(vi &T) : data{T} {
        length = T.size(), pos = 0;
        first_of.assign(V, length);
        next_same.assign(length + 1, length);
        count_same.assign(length + 1, 0);

        for (int i = length - 1; i >= 0; i--) {
            next_same[i]   = first_of[T[i]];
            first_of[T[i]] = i;
            count_same[i]  = count_same[next_same[i]] + 1;
        }
    }

    int next(int ch) const { return first_of[ch]; }
    int remain(int ch) const {
        int p = first_of[ch];
        return p < length ? count_same[p] : 0;
    }
    void step() {
        first_of[data[pos]] = next_same[pos];
        pos++;
    }
    void move_to(int new_pos) {
        while (pos < new_pos)
            step();
    }
    void match(int ch) { move_to(first_of[ch] + 1); }
};

vi calculate_ucs(vi &A, vi &B, vi &pickA, vi &pickB) {
    int n = A.size(), m = B.size();
    vi cntA(V, 0), cntB(V, 0);
    for (int x : A)
        cntA[x]++;
    for (int x : B)
        cntB[x]++;

    vi partA, partB;
    for (int i = 0; i < n; i++)
        if (cntA[A[i]] <= cntB[A[i]])
            partA.push_back(i);
    for (int i = 0; i < m; i++)
        if (cntB[B[i]] < cntA[B[i]])
            partB.push_back(i);
    partA.push_back(n), partB.push_back(m);

    Sequence seqA(A), seqB(B);
    Sequence skipA(A), skipB(B);
    auto pA = partA.begin(), pB = partB.begin();
    skipA.move_to(*pA), skipB.move_to(*pB);
    vi candidate;

    while (*pA != n or *pB != m) {
        bool can_putA = true, can_putB = true;

        if (*pA != n) { // can we fill A[i]?
            can_putA &= seqB.remain(A[*pA]) > skipB.remain(A[*pA]);

            if (*pB != m) 
                can_putA &= skipA.remain(B[*pB]) >= skipB.remain(B[*pB]);
            
        } else
            can_putA = false;

        if (*pB != m) {
            can_putB &= seqA.remain(B[*pB]) > skipA.remain(B[*pB]);

            if (*pA != n) 
                can_putB &= skipB.remain(A[*pA]) >= skipA.remain(A[*pA]);
            
        } else
            can_putB = false;

        std::cerr << "pA: " << *pA << ", pB: " << *pB << ", can_putA: " << can_putA << ", can_putB: " << can_putB
                  << "\n";

        if (can_putA == can_putB)
            return {-1};
        else if (can_putA) {
            int cha = A[*pA];
            candidate.push_back(cha);
            seqB.match(cha);
            std::swap(seqA, skipA);
            seqA.step();
            pA++;
            skipA.move_to(*pA);
        } else {
            int chb = B[*pB];
            candidate.push_back(chb);
            seqA.match(chb);
            std::swap(seqB, skipB);
            seqB.step();
            pB++;
            skipB.move_to(*pB);
        }

        pickA.push_back(seqA.pos - 1);
        pickB.push_back(seqB.pos - 1);
    }

    return candidate;
}

vi prepare(vi &A, vi &B) {
    int n = A.size(), m = B.size();
    std::vector<vi> appear(V);
    for (int i = 0; i < m; i++)
        appear[B[i]].push_back(i);
    for (auto &v : appear)
        v.push_back(m);

    vi last(V, -1);
    std::vector<std::pair<int, int>> stack;
    stack.push_back({-1, -1});

    vi match(n, -1);
    for (int i = 0; i < n; i++) {
        int L     = last[A[i]];
        int where = std::lower_bound(stack.begin(), stack.end(), std::make_pair(L, -1))->second;
        if (where != m)
            where  = *std::upper_bound(appear[A[i]].begin(), appear[A[i]].end(), where);
        match[i] = where;

        while (!stack.empty() && stack.back().second >= where)
            stack.pop_back();
        stack.push_back({i, where});
        last[A[i]] = i;
    }

    return match;
}

bool check(vi &A, vi &B, vi &c, vi &posA, vi &posB) {
    int n = A.size(), m = B.size(), t = c.size();
    vi matchA = prepare(A, B);
    vi atA(n, -1), prev_atA(n + 1, -1);
    for (int i = 0; i < t; i++) {
        atA[posA[i]]          = i;
        prev_atA[posA[i] + 1] = i;
    }
    for (int i = 1; i <= n; i++)
        if (prev_atA[i] == -1)
            prev_atA[i] = prev_atA[i - 1];
    for (int i = 0; i < n; i++) {
        if (atA[i] != -1)
            continue;

        int index = prev_atA[i];
        if (index != -1 && matchA[i] <= posB[index])
            return false;
    }
    return true;
}

vi ucs(vi A, vi B) {
    vi posa, posb;
    auto ans = calculate_ucs(A, B, posa, posb);

    if (ans.size() == 1 && ans[0] == -1)
        return {-1};

    if (!check(A, B, ans, posa, posb))
        return {-1};
    if (!check(B, A, ans, posb, posa))
        return {-1};

    return ans;
}

int main() {
    int n, m;
    std::cin >> n >> m;
    vi A(n), B(m);
    for (int &x : A)
        std::cin >> x;
    for (int &x : B)
        std::cin >> x;
    vi result = ucs(A, B);
    std::cout << result.size() << '\n';
    for (auto x : result)
        std::cout << x << " ";
    std::cout << "\n";
}