CF1392H 题解

First Post:

Last Update:

计数能力退化力,以前最拿手的 min-max 也不大会用了。

可能跟做题欲望有些消退有关。

调整状态,抓紧时间奋斗 /fendou

表示第 张牌被加入集合是在第几轮。因为每一轮的期望时间是确定的(也就是第一次抽出 Joker 的时间),我们设其为 ,答案即为

min-max 容斥:

考虑 怎么求,显然这只与 有关。设 ,我们每次抽牌的时候,可以忽略既不在 ,也不是 JOKER 的牌,因为它们不会对答案有任何影响。所以此时,抽出一张在 中的牌的概率就是 ,反之则有 的概率让轮数 。所以所求期望就是

所以

接下来考虑 怎么算,设 表示恰好在第 张牌时抽出 Joker 的概率,那么 ,且 。综上,我们可以在 的时间里解决本题。

一开始做的时候,就没把它当个概率题在做,设了一堆状态在那乱想。事实证明,研究概率问题时,要想放设法利用概率模型之间的独立性和概率的等价性,拆分和简化问题