BZOJ 3998 [TJOI2015] 弦论


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3998

题意:对于一个给定长度为 N 的字符串,求它的第 K 小子串是什么。


本质相同与否的子串算不算一个其实只影响了 SAM 上 right 集合大小的含义。

直接建 SAM,拓扑 DP 一下,从根开始贪心的 dfs 即可。

发现拓扑序即按照 mx 排序,可以大幅优化常数。一号板子题。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3998 [TJOI2015] 弦论


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,