Uyhip2016 July

r_64 posted @ 2016年8月01日 05:38 in 未分类 with tags uyhip , 921 阅读

这么难的题目窝根本不会做。。part1的思路就很逆天了。。这里做个搬运工

题目

part1:

令$l(i)$为第$i$个人最底下的白帽子的层数。设一个数$k$,我们考虑这样的策略:只考虑每个人头上的前$k$顶帽子,我们假设所有$l(i)\le k$且所有$l(i)$之和是$k$的倍数。每个人都可以根据这样的策略猜出一个位置。。如果他看到别人的$l(i)>k$那就乱猜(我们甚至可以把此时的成功概率计算成$0$)。现在算成功概率。

所有$l(i)\le k$:$(1-(\frac{1}{2})^k)^n$

所有$l(i)$之和是$k$的倍数:$\frac{1}{k}$

所以概率是$\frac{(1-(\frac{1}{2})^k)^n}{k}$

取$k=\log_2 n$,这个柿子变成$\frac{(1-\frac{1}{n})^n}{\log_2 n}$,当$n\to+\infty$时就是$\frac{1}{\text{e}\log_2 n}$了。符合条件。

part2还没看→_→


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter