题解：P10646 [NordicOI 2023] ChatNOI

light_searcher · 2025-11-14 08:52:26 · 题解

很妙的题。

每次加入一个字符串可以看作是一种转移，可以把这个过程抽象成一个图论问题。那么就可以把 k 个连续的单词看作是一个点，对于每个连续 k+1 的单词，从前 k 个单词的点连一条到后 k 个单词所代表的点的边，边权是这个长度为 k+1 的连续段的出现次数。

由于每个长度为 k+1 的连续段对应着唯一的一条边，所以边权总和是不超过 n 的，容易证明边权种类数至多是 \mathcal O(\sqrt n) 的。

这样子假设最终答案的字符串组质量为 x，那么相当于从起点开始走 m 步，每次经过的边权必须不小于 x。

那么我们可以把询问离线下来，从大到小枚举边权的种类，把边从大到小加入，然后建反图跑拓扑排序，求出每个点开始的最长路，然后更新答案即可。如果从某个点开始能经过环，那么从这个点开始就可以无限走。

由于边权种类至多是 \mathcal O(\sqrt n) 的，所以上述做法是 \mathcal O(\sqrt n(n+q)) 的，实际上跑不满，很容易通过。