首页 > [NOI2015]荷马史诗
开通博客写题解
头像 CCCCCHHHGG
发表于 2020-04-01 13:27:41
对于任意的 1≤i,j≤n，i≠j，都有：si 不是 sj 的前缀 这就是说要用到哈夫曼树题目还要保证最长的字符串长度最小，那么如果现在有两个权值相同的节点，我们应该优先选择深度较小的节点，因为我们如果选择了深度大的节点那么这个树的深度就会变长，我们选中深度较小的节点，那么我们深度较大的节点会在后面 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 louhc
发表于 2019-08-28 22:12:06
思路 先不考虑的长度,就是一个叉哈夫曼树.题中要求没有是的前缀恰好对应了这一点,因为所有单词编码都是叶子节点,不会出现某字符串是另一字符串前缀的情况.因为需要的长度尽量小,我们在合并的时候尽量选深度小的即可. 代码 #include<bits/stdc++.h> using namesp 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”