SPOJ 5103. Top 10

这道题我一年前看到过。。。当时吓死了。。毫无思路。。
现在再看看。。发现好像是。。傻叉题?
https://www.spoj.pl/problems/TOP10/

首先注意到一个性质。。就是一些字符串按字典序排序后。。以某个字串开始的字符串是一个区间。。
那么对于这个题目。。我们将所有的字符串的后缀排序。。由于后缀的前缀就是子串。。所以对于一个询问
只需要用线段树来找区间前10大值就可以了。。

注意到显然不能直接将后缀提取再排序。。
可以使用hash搞。。复杂度NLogN^2。。

4 thoughts on “SPOJ 5103. Top 10

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>