题解：P5841 [CTSC2011] 字符串重排

· · 题解

[CTSC2011] 字符串重排

神仙题。

为了防止出现一个字符串是另一个字符串前缀的情况先在所有字符串的最后加上一个占位符。

先做第一问。注意到将字符串按照字典序排序后的排列答案一定是最大的，所以直接放到字典树上做一遍 dfs 排好序求相邻串在字典树上点的 lca 的深度即可。

然后考虑第二问，先想一下第一问这么做为什么是对的。因为在 dfs 的过程中我们相邻的两个串一定是到了最深的位置才统计的答案从（可以感性理解一下），这样可以保证最大。注意到这一点后不难发现其实只要最终的排列对应的点是字典树的任意一个 dfs 序的子序列就满足价值最大。

然后考虑最大化任务奖励。由于第 i 个任务的奖励是 2^i，所以从大到小判断每一任务。观察一下性质发现对于每个点，一个任务相当于规定了其子树作为字符串末尾出现的点的 dfs 序的第一个或最后一个或者规定两个点让它们连续出现，可以直接用链表维护子树内点的顺序。一个任务能否被满足只需要讨论每个点在其父亲的子树的 dfs 序中的位置是否是第一个或最后一个，随便判断一下即可。这里细节比较多，建议自己画几个图理解一下。最后如果满足限制就将两点在 lca 下方的祖先的链表暴力合并即可，由于链表大小是 \operatorname{O}(\left|\sum\right|) 的，不会影响复杂度。

第二问做完之后第三问就好做了。直接根据维护的链表 dfs，把顺序记下来即可。

但这样做是 \operatorname{O}(nq) 的。瓶颈在于对于一个任务所对应的串在字典树上的那两个点，我们要对其路径上的每一个点讨论其在子树的 dfn 序中的顺序。而路径长度可能会很长。

注意到如果一个点只有一个儿子那么直接把这个点连向其儿子的儿子不影响答案，所以可以删去这些点。删除了这些点后每个点的儿子数量都大于等于二，所以产生了一个深度为 i+1 的点必然有一个深度大于等于 i 的点。那么树高就变成 \operatorname{O}(\sqrt{l}) 级别的了。记 l 为所有字符串的长度，时间复杂度 \operatorname{O}(q\sqrt{l}+l\left|\sum\right|^2)。