构造huffman编码,果断对字符进行状态压缩。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; #define MAXN 255
char s[MAXN];
int cnt[], lens[]; typedef struct node_t {
int v;
int n;
node_t() { }
node_t(int vv, int nn) {
v = vv; n = nn;
}
friend bool operator <(node_t a, node_t b) {
return a.n > b.n;
}
} node_t; void addBits(int x) {
for (int i=; i<; ++i) {
if(x & (<<i))
++lens[i];
}
} void bfs() {
priority_queue<node_t> Q;
int i; memset(cnt, , sizeof(cnt));
memset(lens, , sizeof(lens));
for (i=; s[i]; ++i)
if (s[i] == '_')
++cnt[];
else
++cnt[s[i]-'A']; for (i=; i<; ++i)
if (cnt[i])
Q.push(node_t(<<i, cnt[i])); if (Q.size() == ) {
node_t a = Q.top();
addBits(a.v);
return ;
} while (Q.size() > ) {
node_t a = Q.top();
addBits(a.v);
Q.pop();
node_t b = Q.top();
Q.pop();
addBits(b.v);
Q.push(node_t(a.v|b.v, a.n+b.n));
}
} int main() {
int len, sum, ans; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif while (scanf("%s", s) != EOF) {
if (strcmp(s, "END") == )
break;
bfs();
len = strlen(s);
sum = len<<;
ans = ;
for (int i=; i<; ++i)
if (cnt[i])
ans += cnt[i]*lens[i]; printf("%d %d %.1lf\n", sum, ans, sum*1.0/ans);
} return ;
}

最新文章

  1. 为什么类和接口不能使用private和protected?接口的方法不能使用private、protected、default
  2. HDU 4801 Pocket Cube
  3. destoon去掉会员注册email验证
  4. save(),saveorupdate()还有marqe()
  5. JEECMS v8 发布,java 开源 CMS 系统
  6. php数据库访问
  7. fibonacci数列的和取余(2)
  8. HDU 4435 charge-station bfs图论问题
  9. jquery之wrap(),wrap(),unwrap()方法详解
  10. js String方法集合
  11. 20150303--从SQL中获取数据的三级联动
  12. 射频识别技术漫谈(13)&mdash;&mdash;Mifare S50与S70【worldisng笔记】
  13. C#中方法的参数修饰符
  14. IE, FireFox, Opera 浏览器支持CSS实现Alpha透明的方法 兼容问题
  15. UVALive - 4026 Difficult Melody(暴力)
  16. yii2 创建ActiveForm(表单)
  17. 汇编指令-str存储指令(4)
  18. LeetCode - 661. Image Smoother
  19. select下拉框插件jquery.editable-select
  20. docker 导入导出镜像

热门文章

  1. C# WinForm登录窗口代码
  2. iOS iOS8新特性--UIPopoverPresentationController
  3. C#泛型类的简单创建与使用
  4. java.util.concurrent.atomic 类包详解
  5. 异步tcp通信——APM.Server 消息推送服务的实现
  6. Message,MessageQueue,Looper,Handler ——由view.post(runnable想到的)
  7. solr可用于集群的搜索 【转】
  8. Rechability的简单使用
  9. oracle查询表信息(索引,外键,列等)
  10. 从头开始学c++,补基础,补踏实