自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:35:45，当前版本为作者最后更新于2025-08-19 12:11:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

:::info[喜提洛谷当前最优解]{open} 信息熵函数不同于所有题解。

https://www.luogu.com.cn/record/231900101 :::

:::warning[Warning]{open} 猜测的单词不一定要属于答案集。 :::

我们需要最大化猜测一个单词带来的价值。设答案集为 $S$，考虑计算猜测一个单词所能缩小 $|S|$ 的比率。设计以下熵函数：

$$E(\text{word})=\sum_{c\in\text{color}(\text{word},S)} P(c)\frac{1}{P(c)}=|\text{color}(\text{word},S)| $$

其中，$\text{color}(\text{word},S)$ 表示猜测 $\text{word}$，且答案集为 $S$ 时的可能颜色集。颜色指交互库返回的数组 $\text{gold}$ 和 $\text{silver}$。

:::success[Tip]{open} 比率基于乘除法意义。故理论上应使用加权几何平均，或取对数后的加权算术平均（也就是分类交叉熵函数）。

但是以上二者分别使用了指数函数和对数函数，计算速度较慢。

采用这里的方法可以避免进行指数，对数和浮点数计算，极大地提高了程序的运行效率。 :::

于是每次猜测只需选择 $E(\text{word})$ 最大的单词即可。

但是，当 $|S|$ 极小时，所有的 $E(\text{word})$ 可能是一样的。为了选择 $S$ 中的单词，我们考虑给 $S$ 中单词的 $E(\text{word})$ 增加额外权值。更改函数为：

$$E(\text{word})=[\text{word}\in S]\cdot \varepsilon+|\text{color}(\text{word},S)| $$

由于第一次猜测前计算 $E(\text{word})$ 太慢了，很难卡过去。

注意到交互库传入了参数 initial_letter。考虑预处理答案的首字母一定时，$E(\text{word})$ 最大的单词，就不会 TLE 了。

本地测试 1000 局，平均分高达 100.350。

:::success[温馨提示]{open} 代码就不放了，自己写可以提高代码能力。 :::