笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 P6059 【[加油武汉]居家隔离】

posted on 2020-02-11 17:24:20 | under 题解 |

很水的一题…但是感觉既然是这场比赛的A,那可能会比较需要一篇general一点的解释。

这题自己本来想枚举最后选的哪个数来做,但是发现根本不科学,自闭了半天。就是考虑钦定了一个数,如果不是最后一个取他,那么前 $k$ 个一定都放比他小的数,同时可以在他的位置和 $k$ 个之间也放一些比他小的数,但是这些方案对于不同的前 $k$ 个元素的最大值,方案是不同的,所以复杂度很假也很麻烦。

发现似乎直接枚举前 $k$ 个元素的最大值比较容易做。分成两类来讨论,第一类情况是成功取到了某个 $x$,另一类情况是不得不取最后一个,发现当且仅当集合里的最大值在前 $k$ 个才会发生。

1、第一种情况。对于每个最大值 $x$,取到他的概率是 $\frac{\binom{x-1}{k-1}}{\binom{n}{k}}$,在取到最大值为 $x$ 的情况下,期望就再乘上一个 $\frac{\mathrm{S-S_{p_x}}}{n-p_x}$。其中 $\rm S$ 表示集合元素的总和,$\rm S_x$ 表前 $x$ 小的元素的和,$p_x$ 表示 $x$ 是第几小的。不难发现这样是对的。

2、第二种情况。不难发现概率是 $\frac{\binom{n-1}{k-1}}{\binom{n}{k}}=\frac{k}{n}$ 。那么期望的话,发现这种情况下最后一个数是谁情况相同,概率均等。所以乘上一个 $\frac{\mathrm{S}-x_{\max}}{n-1}$ 就完了。

这个故事告诉我们「组合计数全靠编,编错就会傻半天」。

代码就不展示了,整个过程还是很显然的。