【TJOI2015】弦论


题意

对于一个给定的长度为 \(n\) 的字符串,求出它的第 \(k\) 小子串是什么。

有两个子问题,一个问题是子串的不同位置算一个;另一个子问题是子串的不同位置算多个。

分析

我们如果知道了每一个状态所表示的子串有多少种情况,在 DAG 上做一个前缀和,就可以贪心的选择要走的路了。

所以问题就是怎么求每一个状态所表示的子串的情况个数。

对于第一个子问题,显然每一个状态都表示的情况数有且只有一个。

对于第二个子问题,每一个状态所表示的情况数就是这样状态的出现次数,即 \(endpos\) 的大小。

于是这道题目就解决了。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 2,011

Categories

Archive