十二省联考 2019 题解

Day 1

B 字符串问题

朴素的想法是，建一张 \(n_a+n_b\) 个点的有向图 \(G\)。对于一个支配关系 \((x,y)\)，从 \(x\) 向 \(y+n_a\) 连边。此外，枚举 \(1\le i\le n_b\)，对于每个满足 \(B_i\) 是 \(A_j\) 前缀的 \(j\)，从 \(i+n_a\) 向 \(j\) 连边。

若 \(G\) 内有环，则显然答案为 \(-1\)。否则，设点 \(u\) 的点权是 \([u\le n_a]\left(ra_u-la_u+1\right)\)，只需求出该图上点权和最大的一条路径即可。

上述做法的复杂度瓶颈在于建图，考虑如何优化。对 \(S\) 的反串建出后缀树，考虑两个子串 \(S_{l_1\dots r_1},S_{l_2\dots r_2}\)，设它们在反串后缀树上的点定位分别是 \(u_1,u_2\)。那么 \(S_{l_1\dots r_1}\) 是 \(S_{l_2\dots r_2}\) 的前缀，当且仅当：

• \(u_1\neq u_2\) 且 \(u_1\) 是 \(u_2\) 的祖先；
• 或者，\(u_1=u_2\) 且 \(r_1-l_1\le r_2-l_2\)。

考虑直接将后缀树的结构放进 \(G\) 中。设后缀树上共有 \(s\) 个节点，在 \(G\) 中新建 \(s\) 个节点并保留后缀树上的连边。对于每个 A 类串 \(A_i\)，设其点定位是 \(u\)，从 \(\mathrm{fa}_u\) 向 \(i\) 连边；对于每个 B 类串 \(B_j\)，从 \(j+n_a\) 向其点定位连边。

此时只剩下在相同节点上的字符串没有处理了。对于每个点 \(u\)，将所有点定位到 \(u\) 的字符串按照长度从小到大排序。对于每个串从它前面第一个 B 类串向它连边即可。

时间复杂度 \(O(|S|+m+(n_a+n_b)\log |S|)\)。

C 骗分过样例

别急。