[BZOJ4567/Luogu3294][SCOI2016]背单词(Trie树,贪心)

发布于 2018-04-08  134 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4567/Luogu3294][SCOI2016]背单词(Trie树,贪心)

Description

Lweb 面对如山的英语单词,陷入了深深的沉思,“我怎么样才能快点学完,然后去玩三国杀呢?”。这时候睿智的凤老师从远处飘来,他送给了 Lweb 一本计划册和一大缸泡椒,他的计划册是长这样的:
—————
序号 单词
—————
1
2
……
n-2
n-1
n
—————
然后凤老师告诉 Lweb ,我知道你要学习的单词总共有 n 个,现在我们从上往下完成计划表,对于一个序号为 x 的单词(序号 1...x-1 都已经被填入):
1) 如果存在一个单词是它的后缀,并且当前没有被填入表内,那他需要吃 n×n 颗泡椒才能学会;
2) 当它的所有后缀都被填入表内的情况下,如果在 1...x-1 的位置上的单词都不是它的后缀,那么你吃 x 颗泡椒就能记住它;
3) 当它的所有后缀都被填入表内的情况下,如果 1...x-1的位置上存在是它后缀的单词,所有是它后缀的单词中,序号最大为 y ,那么你只要吃 x-y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友,所以请你帮助 Lweb ,寻找一种最优的填写单词方案,使得他记住这 n 个单词的情况下,吃最少的泡椒。

Tag

Trie树,贪心

解决思路

首先肯定是要尽量避免第一种情况的,那么就让一个串的所有后缀的位置一定优于这个串。所以可以想到把字符串反过来插入到Trie树中,这样我们就可以处理后缀的问题了。
把Trie树中所有是单词结尾的地方以及0号根节点单独提出来,建立一棵新的树。现在的问题是,如歌分配这些点的编号使得所有的儿子-父亲的编号之和最小。
贪心地想到,每一次向下走的时候,优先走size更小的子树,这样使得差值会尽量小。所以统计出size后,对每一个点的儿子按照size排序,优先走小的进行编号。
注意对根节点0的特殊处理

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4567/Luogu3294][SCOI2016]背单词(Trie树,贪心)


HNCJ OIer