3 条题解
-
1
这里主要介绍一下哈夫曼树。
话说为什么都复习初赛了却不知道哈夫曼树?本质上就是一颗 叉树,每个节点连向下一层的边权从 到 ,而每个叶子节点为一个词,这样就能保证不会有词是其他词的前缀(因为它的前缀不是叶子节点)。
而一个词所对应的编码则由从根节点到这个叶子结点的路径边权拼接而成。
--------------------------我是分隔线--------------------------
对于最后一层可能不放满的情况,只需要加几个出现次数为 0 的点,使它最后一层能凑齐 个点即可。
而对与合并过程中出现两个相同权值的情况,只需要先合并深度小的即可。
code:
#include<bits/stdc++.h> using namespace std; #define int long long int n,k,a[100005]; struct node{ int x,depth; }; bool operator < (node a,node b){ if(a.x!=b.x) return a.x>b.x; return a.depth>b.depth; } node makenode(int x,int y){ node aa; aa.x=x; aa.depth=y; return aa; } priority_queue<node> pq; signed main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; pq.push(makenode(a[i],0)); } if(k!=2){ for(int i=n%(k-1);i!=1;i=((i+1)%(k-1))){ pq.push(makenode(0,0)); } } int ans=0; while(pq.size()>1){ int max_dep=0,sum=0; for(int i=1;i<=k;i++){ node x=pq.top(); pq.pop(); max_dep=max(max_dep,x.depth); sum+=x.x; } pq.push(makenode(sum,max_dep+1)); ans+=sum; } cout<<ans<<'\n'<<pq.top().depth; return 0; } -
1
闲言
这不是[模板]哈夫曼树吗,放在这是什么意思?
我写个堆不就完了?
不对,样例二挂了。
是什么??
原来是 叉的哈夫曼树。
前文
以防你不知道什么是哈夫曼树 哈夫曼编码,先来介绍一下。
哈夫曼编码是一种压缩信息量的方法,著名的摩尔斯电码就是采用的这样的编码。
哈夫曼编码的最大特点是编码的长度不等,如摩尔斯电码里的 是一短(要么就是一长,反正他是最短的)。
为什么要这么编码呢?
可以发现 是英语里面最常出现的字母,把他编的短一点应该可以很大降低电报长度,毕竟电报是按字数收钱的。
又比如 等,打几百个字母也就出现几次,编的长一点在整体上更优。
但是我们遇到了一个问题:如何确保信息的准确传递呢?也就是说,怎么才能避免把长编码的一部分错认为短编码呢?
要想保证正确性,必须保证每个编码不是某个编码的前缀。
我们回到 的方向,把每个串插入字典树,可以发现,每个叶子节点到根构成的字符串对应且仅对应一个编码,而非叶子节点不代表任何编码。
我们设编码 的出现概率为 ,长度为 ,则我们希望,编码的期望长度 最小。
由期望的线性性,可以知道 。
贪心地想, 越小的编码长度应该越大,于是我们可以得出 哈夫曼编码的经典构造方法:初始时每个编码对应一个叶子节点,每次取概率最小的两个叶子,将其合并得到一个新叶子,新叶子的概率就是原概率之和。
此处读者感性理解即可,证明详见
OI-wiki。好像一般翻译为霍夫曼树,但是我习惯叫哈夫曼,可能因为我当时这么学的吧。总之到网上搜要搜霍夫曼树。
于是我们得到了经典的二进制哈夫曼算法,这样构造出来的树就是哈夫曼树。
正文
没错,写了这么多,我们终于要开始看这个题了。
我们沿用二进制的算法来做,每次拿出最小的 个点来合并,你会发现这样假了。
原因很简单:如果最后一次合并没有凑齐 个点,我们完全可以从最深的一层拿一个点上来安到根上,这样一定是更优的。
简单归纳一下,可得: 进制哈夫曼算法最开始合并的一个点有小于等于 个儿子,而其他所有非叶子节点都恰好有 个儿子。
于是我们把每种单词扔进堆里,按次数为第一关键字升序,高度为第二关键字升序,特判第一次合并,其他正常做就完事了。
因为要保证长度和最小,所以这样一定能得到正确答案。
细节上,第一次特判要选总点数取模 的结果个点来合并,当 时进入死循环,要特判一下。
代码
非常好写。
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int T,n,k; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>k; for(int i=1;i<=n;i++){ int x; cin>>x; pq.push({x,0}); } int ans=0; if(k==2){ while(pq.size()>1){ int s=pq.top().fi,d=pq.top().se; pq.pop(); s+=pq.top().fi,d=max(d,pq.top().se); pq.pop(); ans+=s; pq.push({s,d+1}); } cout<<ans<<'\n'<<pq.top().se<<'\n'; return 0; } while(pq.size()>1){ int c; if(pq.size()%(k-1)==1) c=k; else c=pq.size()%(k-1); if(c==0) c=k-1; int s=0,d=0; while(c--){ s+=pq.top().fi,d=max(d,pq.top().se+1),pq.pop(); } ans+=s; pq.push({s,d}); } cout<<ans<<'\n'<<pq.top().se<<'\n'; return 0; }
- 1
信息
- ID
- 939
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 123
- 已通过
- 11
- 上传者