SMU Winter 2024 div2 ptlks的周报Week 7（3.25-3.31）

哈夫曼编码对出现频率大的字符赋予较短的编码，对出现频率小的字符赋予较长的编码。哈夫曼树的建树过程为，每次选取最小和次小的根节点，将它们之和作为它们的根节点，左子节点为小点，右子节点为次小点，直至仅剩一棵树。一棵哈夫曼树，左子树为0，右子树为1，以根节点到叶子结点的路径作为每个叶子结点的编码。

哈夫曼编码

题意：给定字符出现频率，求字符的哈夫曼编码。

代码

#include <bits/stdc++.h>
#define int long long
#define MOD 998244353
#define PII pair<int,int>
#define PIII pair<int,PII>
using namespace std;

PII g[2048];
char no[2048];
map<int,int>a;
char code[2048];
string s;
int pos=0;
vector<string>ans;

void buildhfm(int len){
	for(int i=0;i<len-1;i++){
		int mn=-1,mnn=1e6;
		for(auto[j,v]:a){
			if(a[j]&&mn==-1){
				mn=j;
			}else if(a[j]){
				mnn=j;
				break;
			}
		}
		for(auto[j,v]:a){
			if(a[j]){
				if(a[j]<a[mn]){
					mnn=mn;
					mn=j;
				}else if(a[j]<a[mnn]&&j!=mn){
					mnn=j;
				}
			}
		}
		a[pos]=a[mn]+a[mnn];
		a.erase(mn);
		a.erase(mnn);
		g[pos++]={mn,mnn};
	}
}

void hfmcode(int root,int len,char arr[]){
	if(root!=-1){
		if(g[root].first==-1&&g[root].second==-1){
			string k;
			k+=no[root];
			k+=':';
			for(int i=0;i<len;i++){
				k+=arr[i];
			}
			ans.emplace_back(k);
		}else{
			arr[len]='0';
			hfmcode(g[root].first,len+1,arr);
			arr[len]='1';
			hfmcode(g[root].second,len+1,arr);
		}
	}
}

int32_t main() {
	int T = 1;
	//cin >> T;
	while (T--) {
		while(getline(cin,s)&&s.length()){
			no[pos]=s[0];
			int t=0;
			for(int i=2;i<(int)s.length();i++){
				t*=10;
				t+=s[i]-'0';
			}
			a[pos++]=t;
		}
		int len=pos;
		for(int i=0;i<pos;i++){
			g[i].first=-1;
			g[i].second=-1;
		}
		buildhfm(pos);
		hfmcode(pos-1,0,code);
		for(int i=0;i<len;i++){
			for(int j=0;j<ans.size();j++){
				if(no[i]==ans[j][0]){
					cout<<ans[j]<<endl;
				}
			}
		}
	}
}

求哈夫曼编码的总长度之和也就是求哈夫曼树的WPL。k叉哈夫曼树每次选取前k小的根节点来建树。要注意的是：对于字符数n，\((n-1)\%(k-1)!=0\)时，直接建树无法完全建树，所以需要加入空节点来确保完全建树，以及确保其余节点的编码长度尽可能小。

P2168 [NOI2015] 荷马史诗

题意：给定字符出现频率，求所有字符的k进制哈夫曼编码的总长度之和的最小值，以及字符的k进制哈夫曼编码长度最大值的最小值。

代码

#include <bits/stdc++.h>
#define int long long
#define MOD 998244353
#define PII pair<int,int>
#define PIII pair<int,PII>
using namespace std;

vector<vector<int>> g(200005, vector<int>(9, -1));
int no[100005];
priority_queue<PII, vector<PII>, greater<PII>>a;
int num[100005];
int pos = 0, K;
int ans = 0, lmx = 0;


void buildhfm(int len) {
	for (int i = 0; i < (len - 1) / (K - 1); i++) {
		int sum = 0;
		for (int j = 0; j < K; j++) {
			sum += a.top().first;
			g[pos][j] = a.top().second;
			a.pop();
		}
		a.push({sum, pos++});
	}
}

int getWPL(int root, int len) {
	if (root == -1)
		return 0;
	else {
		int sum=0;
		for(int i=0;i<K;i++){
			sum+=g[root][i];
		}
		if (sum==-K){
			lmx=max(lmx,len);
			return num[root] * len;
		}else {
			int s=0;
			for(int i=0;i<K;i++){
				s+=getWPL(g[root][i],len+1);
			}
			return s;
		}
	}
}

int32_t main() {
	int T = 1;
	//cin >> T;
	while (T--) {
		int n;
		cin >> n >> K;
		pos = n;
		for (int i = 0; i < pos; i++) {
			int x;
			cin >> x;
			num[i] = x;
			a.push({x, i});
		}
		if((n-1)%(K-1)){
			for (int i = 0; i < (K - 1) - (n - 1) % (K - 1); i++) {
				a.push({0, pos++});
			}
		}
		int len=a.size();
		buildhfm(len);
		ans=getWPL(pos-1,0);
		cout<<ans<<endl;
		cout << lmx << endl;
		return 0;
	}
	return 0;
}