P6681 题解

EuphoricStar · 2024-01-25 13:48:56 · 题解

被 QOJ1193 Ambiguous Encoding 撞了。

考虑直接 dp，设 f_{i, j} 为较长的串未被较短的串覆盖的部分是第 i 个字符串的长为 j 的后缀。转移考虑枚举接在较短的串后面是第 k 个串，然后讨论一下 j 和第 k 个字符串的大小关系就可以确定转移到哪。

发现转移成环，考虑建图用最短路转移。这里 |E| = n^2m, |V| = nm，复杂度看似是 O(|E| \log |V|) = O(n^2m \log nm) 的。但是 Dijkstra 最短路复杂度中的 |E| 实际上是松弛次数，但是这题考虑最大边权 \le m 所以任意时刻队列距离的极差 \le m，所以每个点松弛次数 \le m，所以复杂度其实是 O(n^2m + nm \log nm)。这可以解释为什么 QOJ1193 Ambiguous Encoding 跑得那么快。

code