docs/misc/space-optimization.md
空间优化相关技巧在算法竞赛中不太常见，但仍有讨论价值．
信息熵描述了存储数据所占用的空间下限，若实际可用的空间低于这个下限则必然损失信息．
???+ note "定义" 对随机变量 $X$，定义信息熵为
$$
H(X)=-\sum_{x}P(X=x)\log_2 P(X=x).
$$
定义中对数底数为 $2$ 是因为计算机中存储的信息每位只有 $2$ 种取值：$0$ 和 $1$．
例如设 $X$ 服从 ${1,2,\dots,n}$ 上的均匀分布，则其信息熵为
$$ H(X)=-\sum_{i=1}^n\frac{1}{n}\log_2\frac{1}{n}=\log_2 n, $$
所以我们至少需要 $\log_2 n$ 位来存储 $1$ 到 $n$ 的整数．
???+ note "[WC2022] 猜词" 交互题，你需要在有限次数内猜一个 5 个字母的单词．每次猜测都需要猜一个词库中存在的单词．如果猜对了，游戏结束；在每次猜错后，交互库会返回哪些字母的位置是正确的，以及哪些字母在待猜单词中出现了但位置是错误的．
??? note "解法"
参见 [用信息论解 Wordle 谜题 - 3Blue1Brown](https://www.bilibili.com/video/BV1zZ4y1k7Jw)．
考虑计算信息熵，显然每次猜词时选择信息熵高的词可使得期望猜词次数尽可能小．
由于本题在猜测之前给出了答案首字母，所以我们可以预处理出每种首字母的最优猜测．
另外若剩余的词很少的话，我们可以考虑优先输出可能是答案的词，从而减小次数．
例如：
bool 数组的每个元素均会占用一个字节的空间，必要时可用每个元素只占用一位的 std::vector<bool> 或 bitset 代替．考虑支持路径压缩和启发式合并的 并查集，传统做法需要两个数组，分别记录父结点编号和子树大小．
注意到：
我们可以利用有符号整数的特性，用负数表示根结点，正数表示非根结点，所以我们只需一个数组即可实现支持路径压缩和启发式合并的并查集．
???+ note "实现"
cpp --8<-- "docs/misc/code/space-optimization/space-optimization_1.cpp"