icontofig | 发布于 2019-08-03 20:32:45 | 阅读量 228 | Trie 贪心 启发式合并
发布于 2019-08-03 20:32:45 | Trie 贪心 启发式合并
Codeforces 965E Short Code Trie树+贪心(启发式合并)
题目大意给你n个串,让你用每个串的某个前缀串重命名这个串并保证重命名后不会有重复的字符串。 题解题目很显然需要我们处理n个串的前缀,所以很自然的想到用Trie树(字典树)来降低时间复杂度和空间复杂度。 所以我们先对n个串建立一棵Trie树,然后在这个Trie树上进行操作。 很多人都说后面是启发式合并,我也不是很清楚下面的思路算不算是启发式合并。 后面我们直接dfs整棵Trie树,并自叶节点向上维护信息。 对于每一个节点,维护一个大根堆(用优先队列实现即可),记录其与其子树上的所有的字符串的长度,若我们没有把某个字符串缩到当前节点,那么我们就将子树中深度最深节点所表示的字符串重命名为当前节点所表
继续阅读