电子商务网站建设与维护 教材,北京市城乡建设网站,网络营销的认知,网站的链接结构怎么做一、哈夫曼树
机试考察的最多的就是WPL#xff0c;是围绕其变式展开考察。 哈夫曼树的构建是不断选取集合中最小的两个根节点进行合并#xff0c;而且在合并过程中排序也会发生变化#xff0c;因此最好使用优先队列来维护单调性#xff0c;方便排序和合并。 核心代码如下…一、哈夫曼树
机试考察的最多的就是WPL是围绕其变式展开考察。 哈夫曼树的构建是不断选取集合中最小的两个根节点进行合并而且在合并过程中排序也会发生变化因此最好使用优先队列来维护单调性方便排序和合并。 核心代码如下
//取出两个权最小的
int num1 (q.top()).x;
q.pop();
int num2 (q.top()).x;
q.pop();
//权相加生成新的节点并放入队列
node new_node;
new_node.x num1 num2;
q.push(new_node);
//结果累加。本来树的带权路径计算是所有节点深度*权的和但是这里通过
//几层累加也能实现乘法的效果。在最下面的节点累加次数最多即相当于
//乘的数值最大
ans num1 num2;
//输出的ans即为最终WPL的值二、哈夫曼树北邮机试
Time Limit: 1000 ms Memory Limit: 256 mb 哈夫曼树第一行输入一个数n表示叶结点的个数。需要用这些叶结点生成哈夫曼树根据哈夫曼树的概念这些结点有权值即weight题目需要输出所有结点的值与权值的乘积之和。 输入输出格式 输入格式 输入有多组数据。 每组第一行输入一个数n接着输入n个叶节点叶节点权值不超过1002n1000。 输出格式 输出权值。 输入输出样例 输入样例
5
1 2 2 5 9输出样例
37AC代码如下
#includebits/stdc.h
using namespace std;struct Node {int x;Node(int a) {x a;}//定义一下构造函数
};//重新定义比较运算符
bool operator (const Node a, const Node b) {return a.xb.x;
}//计算WPL
int getWPL(priority_queueNode q) {int sum 0;while(q.size()1) {//只剩下根节点的时候退出 int num1 (q.top()).x;q.pop();int num2 (q.top()).x;q.pop();Node tmp(num1num2);q.push(tmp);sum num1num2; }return sum;
}int main() {int n;while(cinn){int a[n];priority_queueNode q;for(int i0 ; in ; i) {cina[i];Node tmp(a[i]);q.push(tmp);}int sum getWPL(q);coutsumendl; }return 0;
}三、哈夫曼编码
输入输出格式 输入格式 输入文件将包含文本字符串列表每行一个。 文本字符串将仅包含大写字母数字字符和下划线用于代替空格。 输入结束将通过仅包含单词“ END”作为文本字符串的行来表示。 此行不应被处理。 输出格式 对于输入中的每个文本字符串输出8位ASCII编码的位长度最佳无前缀可变长度编码的位长度以及精确到小数点后的压缩率。 输入输出样例 输入样例
AAAAABCD
THE_CAT_IN_THE_HAT
END输出样例
64 13 4.9
144 51 2.8分析这道题目关键在于计算压缩后的长度本质上也是计算WPL这里的权值是每个字母出现的次数路径长度就是编码的长度一个二进制数就是一位。 AC代码如下
#includebits/stdc.h
using namespace std;string str;
int len, num[30];int bfs() {priority_queueint, vectorint, greaterint q; // 创建优先队列从小到大排序for(int i 0; i 30; i) {if(num[i]) q.push(num[i]); // 放入每个字母的个数}int sum 0;if(q.size() 1) sum q.top(); // 如果只有一个字母直接等于该字母的数量while(q.size() 1) { // 得到前两个最小的叶子节点将和放入队列中int a q.top(); q.pop();int b q.top(); q.pop();sum (a b); q.push(a b); // 因为ans累加了之前的值所以传入的是a b而非ans;}return sum;
}int main() {while(cin str) {memset(num, 0, sizeof num);if(str END) break; // 注意为双引号len str.size(); // 得到string类型的长度for(int i 0; i len; i) {if(str[i] _) num[26]; // 应为A - A等于0从下标0开始所以_就在num[26]else num[str[i] - A];} int res bfs();printf(%d %d %.1lf\n, len * 8, res, len * 8.0 / res);}return 0;
}四、合并果子中南大学机试
Time Limit: 1000 ms Memory Limit: 256 mb 在一个果园里多多已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并多多可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过n-1次合并之后就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使多多耗费的体力最少并输出这个最小的体力耗费值。 例如有3种果子数目依次为129。可以先将1、2堆合并新堆数目为3耗费体力为3。接着将新堆与原先的第三堆合并又得到新的堆数目为12耗费体力为12。所以多多总共耗费体力31215。可以证明15为最小的体力耗费值。 输入输出格式 输入格式 输入包括两行第一行是一个整数n(1n10000)表示果子的种类数。第二行包含n个整数用空格分隔第i个整数ai(1ai20000)是第i种果子的数目。 输出格式 输出包括一行这一行只包含一个整数也就是最小的体力耗费值。输入数据保证这个值小于2^31。 输入输出样例 输入样例
3
1 2 9输出样例
15分析这题本质上还是计算WPL只是题面比较明显看出在构造哈夫曼树过程中对权值进行累加。 AC代码直接参考【北邮机试】代码输出ans即可。
