概率与期望 DP 总结
2016-12-01
概述 只用到概率的题并不是很多,从现有的 OI 比赛中来看,大多数题目需要概率与期望结合起来(期望就是用概率定义的),所以本文主要讲述期望 DP。
期望 DP 有一些固定的方法,我会分多种方法来讲述。
讲解 例一 我们首先看 BZOJ 3036 这样一个题。
题意: 给定一个起点为 1 1 1 ,终点为 n......
BZOJ 1426 - 收集邮票
2016-11-28
题目地址
描述 有 n ( n ≤ 1 0 0 0 0 ) n(n\le 10000) n ( n ≤ 1 0 0 0 0 ) 种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是 n n n 种邮票......
BZOJ 3566 - [SHOI2014]概率充电器
2016-11-28
题目地址
描述 著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!” SHOI 概率充电器由 n − 1 n - 1 n − 1 条导线连通了 ......
BZOJ 3450 - Tyvj1952 Easy
2016-11-28
题目地址
描述 某一天 WJMZBMR 在打 osu~~~ 但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则: 有 n ( n ≤ 3 0 0 0 0 0 ) n(n\le 300000) n ( n ≤ 3 0 0 0 0 0 ) 次点击要做,成功了就是 o ,失败了就是 ......
BZOJ 4008 - [HNOI2015]亚瑟王
2016-11-27
题目地址
描述 小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly 都敲不对了,因此,希望你能帮帮小 ......
BZOJ 3143 - [Hnoi2013]游走
2016-11-26
题目地址
描述 一个无向连通图,顶点从 1 1 1 编号到 n ( n ≤ 5 0 0 ) n(n\le 500) n ( n ≤ 5 0 0 ) ,边从 1 1 1 编号到 m m m ......
NOIP 2016 Day 2 题解
2016-11-23
组合数问题 problem 知识点 杨辉三角,模运算,前缀和
分析 n ≤ 2 0 0 0 n \le 2000 n ≤ 2 0 0 0 ,显然直接 O ( n 2 ) O(n^2) O ( n 2 ) ......
NOIP 2016 Day 1 题解
2016-11-23
先声明一下,如果你是初学者,你可能会看不懂其中的一些东西,原因是你的知识点以及技巧没有跟上,我会尽量写得详细一点,如果还有不懂,欢迎留言。
玩具谜题 toy 知识点 模拟
分析 可以发现,本题就是根据要求在环上顺时针或者逆时针走动,那么假设当前的位置是 p p p ,那么逆时针走 x x x ......
百练 3468 - 电池的寿命
2016-11-18
题目地址
描述 小 S 新买了一个掌上游戏机,这个游戏机由两节 5 号电池供电。为了保证能够长时间玩游戏,他买了很多 5 号电池,这些电池的生产商不同,质量也有差异,因而使用寿命也有所不同,有的能使用 5 个小时,有的可能就只能使用 3 个小时。显然如果他只有两个电池一个能用 5 小时一个能用 3 小时,那么他只能玩 3 个小时的游戏,有一个电池剩下的电量无法使用,但是如果他有更多......
Codeforces 723E - One Way Reform
2016-11-15
题目地址
描述 给定一个 n ( n ≤ 2 0 0 ) n(n\le 200) n ( n ≤ 2 0 0 ) 个点 m ( m ≤ n ( n − 1 ) 2 ) m(m\le \frac{n(n - 1)}{2}) m ( m ≤......