比赛详情
脑瘫一日复一日。
A
考场上对 \(t\) 建出 ACAM。一直在想枚举 \(\min/\max\) 对应的串，然后求答案，但是发现无论如何都不行，甚至 \(n = 2\) 都不会判。打了一个 \(50pts\)（挂成 \(40\)）。
实际上可以这样子，\(t_i\) 不是 \(P\) 的子串相当于 ACAM 中有些点不能经过（跳 fail 跳到某个 \(t_i\) 结尾就不能经过），直接删掉即可。剩下的点根据自动机转移形成一张图 \(G\)。\(P\) 就相当于可以在 \(G\) 上随便走，也就消掉了不能包含 \(t_i\) 的限制。
对于每个节点 \(u\)，设根到 \(u\) 的路径得到串 \(str\)。 \(s_{p_1}, s_{p_2}, \dots, s_{p_k}\) 是 \(str\) 的后缀（$u $跳 fail 跳到 \(s_{p_i}\) 的结尾），那么 \(Set(P)\) 就是 \(P\) 路径上经过的 \(u\) 对应 \(p\) 序列的并集。
然后就比较简单了，就是计算路径上经过的最小值和最大值。把 \(G\) 缩点后跑拓扑排序进行 DP 即可。
注意 \(s_i, t_i\) 都要插入到 ACAM 中。
时间复杂度是线性的。
总结
感觉钻牛角尖了，一直在想枚举 \(\min / \max\) 怎么做，实际上条件太多无从下手。要尝试先消掉一些条件，简化问题。