站外题求救!啊啊 qaq
  • 板块学术版
  • 楼主AstralSparkle
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/30 18:38
  • 上次更新2024/9/30 19:02:16
查看原帖
站外题求救!啊啊 qaq
1263338
AstralSparkle楼主2024/9/30 18:38

站外题求助,蒟蒻一头雾水 qaq

题面

nn 个单词,编号从 1n1\sim n。第 ii 个单词的出现的次数为 aia_i

某人对这些单词进行了二进制编码,第 ii 个单词编码后的二进制数用一个字符串 sis_i 表示。

请你判断此人的编码是不是这个出现次数下合法的哈夫曼编码。

如果是,输出 Yes,并计算出按照这个编码的文章总长度(二进制位数)。
否则,输出 No,并给出一组满足要求的哈夫曼编码。

注意:本题中只要保证了在该二进制编码下,文章总长度能达到最短;且任意一个编码都不是其他编码的前缀;就认为是一个合法的哈夫曼编码。


输入格式

第一行是 nn

第二行为空格隔开的 a1ana_1\sim a_n
接下来 nn 行,第 ii 行为 sis_i


输出格式

按题目要求输出:

如果输入的是哈夫曼编码,输出两行:
第一行为 Yes
第二行为这个编码下的文章总长度。

如果输入的不是哈夫曼编码,输出 n+1n+1
第一行为 No
接下来 nn 行,第 ii 行为第 ii 个单词对应的哈夫曼编码。
如果有多种方案,输出任意一种即可。

2024/9/30 18:38
加载中...