IOI2024 Day2T1

首先考虑保证有解的情况，目标是找到一组可能的解，不需要 check。

如果一种字符在 $a$ 中出现 $x$ 次，在 $b$ 中出现 $y$ 次，那么在解 $c$ 中需要出现 $\min(x, y)$ 次。

将出现次数较少的一侧的元素标记为关键位，我们要将所有关键位在另一个序列中找到匹配，且匹配两两不交。

考虑两个序列中的第一个关键位 $a_{i}$ 和 $b_{j}$，接下来分类讨论：

如果它们相等，直接匹配即可。

否则，如果 $a_{i}$ 在 $b_{1 \dots j-1}$ 中没有出现，则 $b_{j}$ 需要匹配 $a_{1 \dots i-1}$ 中的某个字符，可以匹配然后递归；对于另一边同理。

剩下的情况是 $a_{i}$ 在 $b_{1 \dots j-1}$ 中出现且 $b_{j}$ 在 $a_{1 \dots i-1}$ 中出现。

如果 $a_{i+1 \dots n}$ 中 $b_{j}$ 的出现次数小于 $b_{j \dots m}$ 中 $b_{j}$ 的出现次数，则 $a_{i}$ 不能匹配 $b_{1 \dots j-1}$ 中的字符，可以直接将 $b_{j}$ 匹配掉然后递归。对于另一边同理。

剩下的情况可以说明其无解。

考虑 $n, m \leq 3000$ 的部分分，下面我们要设计算法 check $c$ 的正确性。

我们现在想要构造一个 $S$，使得 $S$ 不是 $c$ 的子序列，但为 $a,b$ 的子序列。

假设求出了 $c_{1 \dots i}$ 在 $a,b$ 中的匹配位置为 $pa_{i}, pb_{i}$。

依次加入字符，维护 $a,b,c$ 上分别匹配到了 $a_{1 \dots i}, b_{1 \dots j}, c_{1 \dots k}$。我们现在想让 $a,b$ 上匹配，$c$ 上失配。

如果 $i < pa_{k}$ 且 $j < pb_{k}$，则加入 $c_{k \dots}$，就能构造无解。

可以说明只有在某次走到 $i < pa_{k}$ 且 $j < pb_{k}$ 时，才能构造无解。

于是我们可以考虑 DP 计算 $i = pa_{k}$ 时最小的 $j$，设为 $f_{k}$。可以暴力枚举 $i$ 的上一个转移的位置，然后二分出新的匹配位置，在转移过程中可以判定有没有 $i < pa_{k}$ 且 $j < pb_{k}$ 的情况。

对于 $j = pb_{k}$ 时最小的 $i$，将 $a,b$ 交换做一遍即可。

时间复杂度 $O(n^2 \log n)$。

考虑优化时间复杂度。

对于可转移到 $i$ 前的一个点，可分为两个区间，一个满足走一步后 $i = pa_{k}$，另一个满足走一步后 $i < pa_{k}$。区间的端点可以二分得到。

用线段树维护 $f$ 的区间最小值，对于两个区间，前一个可以转移到 $f_{k}$，后一个可以用于判定无解。

设 $n,m$ 同阶，时间复杂度 $O(n \log n)$，期望得分 100。