IOI2024 Day2T1

Rainbow_qwq · 2025-06-26 20:07:55 · 题解

首先考虑保证有解的情况，目标是找到一组可能的解，不需要 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。

code