自动搬运

查看原文

来自洛谷，原作者为

	Starlight237 [Drawer/auth]EgcqEzGZV+k435xMKiYIpABsjWY0ln/huv6DW7QW9Qw=

搬运于2025-08-24 22:25:09，当前版本为作者最后更新于2021-10-27 15:37:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Huffman 树

设一棵二叉树的叶节点权值和深度分别为 $\{w_i\},\{d_i\}$，则定义 $\sum w_id_i$ 为这棵树的 WPL（这个名字并不准确，但是既然 OI-wiki 这么写，这里就沿用下来）。

给定所有叶节点和它们的 $w_i$，WPL 最小的二叉树称为这个叶节点权值序列的 Huffman 树。此外，这个二叉树应当满足除了叶节点的度为 0 以外，剩下的节点的度都是 2。

如下算法可以构建一个序列的 Huffman 树。

• 以给定的权值构造 n 棵只含有 1 个节点的二叉树，加入二叉树集合 $S$。
• 从 $S$ 中选取权值最小的两棵二叉树 $T_1,T_2$ 合并成一个大二叉树 $T$，并令 $w(T)=w(T_1)+w(T_2)$。从 $S$ 中删去 $T_1,T_2$，加入 $T$。
• 重复上一个步骤，直到 $S$ 中只剩下一棵二叉树。这棵二叉树就是 Huffman 树。事实上，合并过程中所有的 $w(T)$ 之和就是 Huffman 树的 WPL。

Huffman 编码

• 定义：将 $n$ 个不同的字符映射为互不为前缀的二进制编码，称为这组字符的前缀编码。若这组字符构成一个字符串 $S$，记 $f(S)$ 表示将 $S$ 中每个字符都替换成对应编码后 $S$ 的长度。使 $f(S)$ 最小的前缀编码称为 Huffman 编码。

如下算法可以构造对于一个字符集 $\Sigma$ 和字符串 $S$ 的 Huffman 编码。

设需要编码的字符分别为 $c_1,...,c_n$，它们在 $S$ 中出现的次数分别为 $w_1,...,w_n$，以 $c_i$ 为叶节点，$w_i$ 为它的权值，构建 Huffman 树。规定连接父亲和左儿子的边权为 $0$，连接右儿子则为 $1$，令 $c_i$ 的编码为从根节点走到 $c_i$ 途径的边权构成的 $0-1$ 字符串。容易证明这就是 Huffman 编码。并且 $f(S)$ 为 Huffman 树的 WPL。

回到本题：

(2021 集训队作业 P6915 【[ICPC2015 WF]Weather Report】)给定 $4$ 种字符出现的概率，求所有 $4^n$ 个可能的长度为 $n$ 的字符串构成的集合的前缀编码，使得每个字符串的编码长度的期望值最小。

对于所有可能的字符串对应的概率求其 Huffman 树即可。但是 $4^n$ 太多了，无法接受。注意到一个字符串的权值（概率）仅与其四个字符出现的次数有关，即可以用有序四元组 $(a,b,c,d)(a+b+c+d=n)$ 表达。每个四元组的概率都容易计算，并且该四元组对应的字符串数量为 $\binom{n}{a}\binom{n-a}b\binom{n-a-b}c$。每个四元组作为一个状态 $(p,cnt)$，p 为它出现的概率，cnt 为它出现的次数，考虑对所有这些状态构建 Huffman 编码。

我们并不显式地建树，而只是开一个堆维护所有的 $w(T)$。

设堆顶为 $(p,cnt)$，若 $cnt>1$，对 $cnt$ 的奇偶性进行讨论，若 $cnt$ 为偶数，将 $(2p,cnt/2)$ 插入堆中，否则将 $(p,1)$ 插入堆中，再转化为 $cnt$ 为偶数的情况。

若 $cnt=1$，从堆中再取出一个状态 $(p',cnt')$ 和当前状态合并。若 $cnt'=1$，直接合并并且 continue，否则把状态拆成 $(p',cnt'-1)$ 和 $(p',1)$。后者直接和当前状态合并，前者插入堆中。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<double, ll>
const int N = 21;
int n, C[N][N];
double p[4][N];
priority_queue<pi, vector<pi>, greater<pi> > Q;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < 4; ++i) {
		p[i][0] = 1; double pp; scanf("%lf", &pp);
		for (int j = 1; j <= n; ++j) p[i][j] = p[i][j - 1] * pp;
	}
	for (int i = 0; i <= n; ++i) C[i][0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n - i; ++j)
			for (int k = 0, l; k <= n - i - j; ++k)
				l = n - i - j - k,
				Q.push(make_pair(p[0][i] * p[1][j] * p[2][k] * p[3][l], (ll)C[n][i] * C[n - i][j] * C[n - i - j][k]));
	double ans = 0;
	while (!Q.empty()) {
		pi tp = Q.top(); Q.pop();
		if (Q.empty() && tp.second == 1) break;
		double pp = tp.first; ll cnt = tp.second;
		if (cnt > 1) {
			if (cnt & 1) Q.push(make_pair(pp, 1)), --cnt;
			ans += pp * cnt;
			Q.push(make_pair(pp * 2., cnt >> 1));
			continue;
		}
		tp = Q.top(), Q.pop();
		double qq = tp.first; cnt = tp.second;
		ans += pp + qq;
		Q.push(make_pair(pp + qq, 1));
		if (cnt > 1) Q.push(make_pair(qq, cnt - 1));
	}
	printf("%.6lf", ans);
	return 0;
}