概率与期望 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 ≤......
