[IOI2024] 象形文字序列

zhouhuanyi · 2024-09-12 17:04:06 · 题解

首先 \text{UCS} 的长度显然是 \sum_{i=1}^{cnt}\min(a_{i},b_{i})，其中 a,b 分别表示字符 i 在两个串的出现次数，这也就意味着每个字符至少有一侧会匹配完，且是次数最小的一侧。

那么 \text{UCS} 的元素实际上与出现次数小的一侧的元素有着一一对应的关系，令左侧小的称为 A 元素，右侧小的称为 B 元素，那么 A,B 元素内部的偏序关系是唯一确定的，我们只需要确定 A,B 元素之间的关系就可以唯一确定 \text{UCS} 是什么，现在就是要能快速判定在 \text{UCS} 的匹配当中一个 A 元素 x 与一个 B 元素 y 在 A 元素的匹配 z 相比，x 与 z 的大小关系。

手完一下 01 序列之后不难发现大小关系是确定的，对于 01 序列，对于一个 A 与 一个 B (不妨令 0 为 A，1 为 B)，由于不能原串与翻转都不能有未配 0，匹配 1，匹配 0，未配 1 状自序列，因为可以得到 匹配 1，匹配 0 的新匹配方案，所以只有 S+k\times 1+T，S+R+T 或 S+R+T，S+k \times 0+T 的一个形式，匹配是非常固定的，S,T 内部互相匹配，中间的之间匹配，但由于中间的匹配只被一种元素控制，所以不会被偏序关系产生影响，可以任意匹配。实际上只要把左右两侧匹配对就可以了，可以通过匹配左侧时前面 0 的个数是否相同来判定是否真的是在左侧，否则就认为在右侧，这样我们就可以快速比较两个元素在 \text{UCS} 序列中的先后顺序，还原只需归并两个序列即可。

现在仅需判定是否合法即可，首先通过 \text{UCS} 我们可以先贪心求出一组合法匹配，合法那么对于任意两个元素构成的 01 序列肯定要合法，这个就是判定是否有未配 x，匹配 y，匹配 x，未配 y 自序列，是一个二维数点的形式，可以用并查集快速解决，但这样还是不够的，会 \text{WA} 在 \text{Subtask5} 的 test16。实际上还存在未配 x，匹配 y，匹配 x，匹配 z，匹配 y，未配 z 的自序列，因为 x,z 匹配到两侧后中间的 y 可以构建一个交叉来交换顺序，这个相当于对于每一个 y，x 出现位置的最小值要小于 z 出现位置的最大值，也可以使用并查集解决。

由于第一部分归并时需要二分求个数，所以总复杂度为 O(n\log n)。