IOI2024 D2T1 Hieroglyphs

zjy2008 · 2024-09-10 10:07:22 · 个人记录

做法贺自 @cmk666，并借鉴了 u 群 jiangly 的发言。

先考虑怎么 check 一个串 X 是否合法。首先这个串的长度一定是 \sum_i \min(cnt_{S,i},cnt_{T,i})，否则只需要单一字符就可以把它爆了。然后考虑枚举一个爆掉的串，我们先求出 X_i 贪心地匹配到 S_a 和 T_b。那么 X_{1\cdots i} 的子序列（包含 i） 就不可能再 S 上匹配到 >a，T 上匹配到 >b。但是如果 X_{1\cdots i} 的子序列在 S 上匹配到 <a，T 上匹配到 <b，那么只需要在后面接上 X_{i\cdots |X|} 就爆了。为了避免一些额外的讨论，我们可以假设 X_{|X|+1}= 通配符。

由上，我们可以考虑枚举 a，记录其对应的最小的b，那么如果 a 不在 S 和 X 匹配中，那么它对应的 b 必须要在匹配中，且其对应位置在 a 后。转移容易用数据结构维护。这个过程要交换 S 和 T 后再做一次。

然后考虑怎么求一个串，首先我们已经知道它的长度是 \sum_i \min(cnt_{S,i},cnt_{T,i})。那么可以变成有 2 个字符集不交的串 A,B，要求归并得到答案。考虑 A_0 和 B_0，如果第一个放 A_0 剩下的串仍能放下那么多 B_0（不考虑别的字符），就放 A_0。第一个放 B_0 剩下的串仍能放下那么多 A_0，就放 B_0。如果都能满足或都不能满足，都爆了。如果都能满足，说明你最终一定可以通过交换 A_0,B_0 使这个串爆。现在选择已经唯一，对于其他字符的影响显然可以在后面考虑。

总复杂度 O(n\log n)。