menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[哈夫曼树]BZOJ4198(Noi2015)【荷马史诗】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $n$ 个单词,要给每个单词对应一个 $k$ 进制数,使得所有单词变为 $k$ 进制数之后接起来长度最小,并且满足在长度最小的前提下最长 $k$ 进制数最短,且 $k$ 进制之间不能有前缀关系。

解题报告

一看就是哈夫曼编码?但是前缀关系是什么鬼?其实把哈夫曼树建出来之后就是个Trie,所有单词都是叶子节点,显然没有前缀关系……

那么就是做 $k$ 叉哈夫曼树,如果 $n$ 个单词不足够让所有节点都 $k$ 叉怎么办?正确姿势是补零而不是最后做不满 $k$ 叉。至于最长的数最短只需要改变下优先级。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,K,si;pair<LL,int> Heap[maxn+5];LL ans;int MAX;

#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si))
#define Pop() (pop_heap(Heap+1,Heap+1+si--))
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) {LL x;scanf("%lld",&x);Push(mp(-x,0));}
    if ((n-1)%(K-1)) for (int i=1,t=K-1-(n-1)%(K-1);i<=t;i++) Push(mp(0,0));
    while (si>1){
        LL A=0;int B=0;for (int t=1;t<=K;t++) A-=Heap[1].fr,B=max(B,-Heap[1].sc),Pop();
        B++;ans+=A;MAX=max(MAX,B);Push(mp(-A,-B));
    }printf("%lld\n%d\n",ans,MAX);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up