题解 P6915 【[ICPC2015 WF]Weather Report】

Starlight237 · 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;
}