[笔记] 倍增相关

[笔记] 概率和数学期望初步

RXDoi posted @ 2014年7月18日 22:24 in 笔记 , 303 阅读

昨天做CF #146(Div.2) vp的时候被D题数学期望虐残了,于是今天自学了一下数学期望相关的基础知识。题目没做多少,主要是在思考概念。

ps:感谢叶队Blog里的笔记!

叶队Blog里的东西实在太神我看不懂2333,所以我就写一下一个蒟蒻的理解吧~~

所谓数学期望,就是说,平均情况下的状况。用公式表示就是。其中xi为其对答案的贡献,pi为其概率。

然后我们来看几道题目。


BZOJ 2134 单选错位

这题虽说很简单,但由于我做期望题经验不多,还是没很快想出来。


BZOJ 3036 绿豆蛙的归宿

这题就简单了~一路写下去顺风顺水,加了读入优化后还刷到了#4.真是愉快极了~~

考虑到图是拓扑图,可以记忆化搜索,把每个点到终点的期望路径长度都求出来。然后搞搞即可。


UVaOJ 11021 麻球繁衍

这是白书上面的题目,比较适合初学者。


Codeforces 236D Let's Play Osu!

这道题的题解详见我的另一篇文章


(未完待续)


登录 *


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