1402-神秘电报密码


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:3 难度:3


题目描述:

看过谍战电影《风声》的观众都会对影片中神奇的消息传递惊叹不已!吴志国大队长在受了残忍的针刑之后躺在手术台上唱空城计,变了音调,把消息传给了护士,顾晓梦在衣服上缝补了长短不一的针脚……那么,片中无处不在的摩尔斯码到底是什么?它又有着怎样的神秘力量呢?

摩尔斯电码(Morse code)由点dot. )、划dash-)两种符号组成。它的基本原理是:把英文字母表中的字母、标点符号和空格按照出现的频率排序,然后用点和划的组合来代表这些字母、标点符号和空格,使频率最高的符号具有最短的点划组合。哈夫曼编码又称最佳前缀码,频率高的编码短,而且一个字符编码不是另一个字符编码的前缀。现有n个字符及其出现的频率,求每个字符的哈夫曼编码。


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个字符。
随后的n行,每行有一个字符ci和一个浮点数wi,表示字符ci的出现频率为wi。
输入数据保证每组测试数据的字符不会重复。

输出描述:

对于每一组输入,输出n个字符及其01编码。格式a: 888。
每组的输出占一行。

样例输入:

2
6
a 0.05
b 0.32
c 0.18
d 0.07
e 0.25
f 0.13
4
a 0.23
b 0.05
c 0.45
d 0.27

样例输出:

a: 1000 b:11 c: 00 d: 1001 e: 01 f: 101
a: 111 b: 110 c: 0 d: 10

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!