3855: 合法哈夫曼(挖土机 CSP-J 模拟赛 ~ 第一场)

题目背景

33DAI 最近做洛谷的 CSP-J 第一轮模拟赛时看到了下面这道题目。

假设有一组字符 {g,h,i,j,k,l}，它们对应的频率分别为 $8\mathrm{\%},14\mathrm{\%},17\mathrm{\%},20\mathrm{\%},23\mathrm{\%},18\mathrm{\%}$。
请问以下哪个选项是字符 g,h,i,j,k,l 分别对应的一组哈夫曼编码？（ ）

• A. g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
• B. g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
• C. g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
• D. g: 110, h: 111, i: 101, l: 100, k: 0, j: 01

33DAI 发现直接哈夫曼树上构建的话，怎么都得不到某个选项。然后才学到了原来哈夫曼编码只需要保证长度没问题，且任意一个编码都不是其他编码的前缀即可。感谢洛谷带来的小知识。

题目描述

有 $�$ 个单词，编号从 $1\sim �$。第 $�$ 个单词的出现的次数为 ${�}_{�}$。

33DAI 对这些单词进行了二进制编码，第 $�$ 个单词编码后的二进制数用一个字符串 ${�}_{�}$ 表示。

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

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

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

第一行是 $\mathrm{<br>}$n。

第二行为空格隔开的 ${\mathrm{<span\; style="font-size:inherit;font-family:""><br>\; </span>}}_{}{\mathrm{<span\; style="font-family:"font-size:inherit;">a1\sim an</span>}}_{}$

接下来 $\mathrm{<br>}$n 行，第 $\mathrm{<br>}$i 行为 ${\mathrm{<br>}}_{}$si

按题目要求输出：

• 如果输入的是哈夫曼编码，输出两行：
  • 第一行为 Yes
  • 第二行为这个编码下的文章总长度
• 如果输入的不是哈夫曼编码，输出 $�+1$ 行：
  • 第一行为 No
  • 接下来 $�$ 行第 $�$ 行为第 $�$ 个单词对应的哈夫曼编码。
  • 如果有多种方案，输出任意一种即可。

6
8 14 17 20 23 18 
111
110
101
00
01
100

Yes
257