[2020多校A层11.22]party

非常巧妙的一个概率期望问题，其实运用的还是近似的思想
现在有n个物品，每次一个人有pi的概率选中这个物品，然后可以进行猜测，但是无论是否猜中都继续游戏，直到所有人都被猜中，求解最少期望在多少步能够猜出所有人。
n<=100，误差不超过1e-6

然后这个题目和一般的概率期望问题思路不同，这道题没有取模，我们要运用近似来处理，因为不知道每个人的信息，所以答案和猜测顺序无关，所以我们只关注每个人猜测的次数，然后我们只需要让每一步游戏结束的概率尽量大，然后答案就是每一步游戏没有结束的概率之和，因为游戏没有结束才会有这一步。

然后我们可以列出式子
$$\prod 1-(1-pi{)}^{c_i}$$
所以我们每次可以选择让这个结果更大的那个点，让他的次数加一，可以发现这样一定是最优的。

将总共的期望天数，利用线性性可以转化为每一天的期望，但是每一天的贡献就是1，所以转化为每一天的概率，实现从期望到概率的转化。

总结

以上是生活随笔为你收集整理的[2020多校A层11.22]party（概率期望/近似）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。