[bzoj4567]-[SCOI2016]背单词

神奇的trie

题目(BZOJ)

题目(洛谷)

 

首先咱们来反建串,这样后缀就转化为前缀问题。

因为这题不关心每个串的长度什么的,所以我们trie上那些空节点可以不要,这样就建好了一棵新树。

然后,对于问题中的条件1可以不管,因为代价太大,

剩下的条件2和3,直接在树上沿子树大小最小的开始走就可以了。

 

发表评论