不是那么简单的矩阵树。 题目描述 T 国有 $N$ 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。 在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到...
概率期望
51nod 1943 联通期望 题解【二进制】【枚举】【概率期望】【DP】
集合统计类期望题目。 题目描述 在一片大海上有 $ n$ 个岛屿,规划建设 $ m$ 座桥,第i座桥的成本为 $ z_i$,但由于海怪的存在,第 $ i$ 座桥有 $ p_i$ 的概率不能建造。 求在让岛屿尽量联通的情况...
洛谷 P5249 [LnOI2019]加特林轮盘赌 题解【概率期望】【DP】
很有意思的题目。 题目背景 加特林轮盘赌是一个养生游戏. 题目描述 与俄罗斯轮盘赌等手枪的赌博不同的是,加特林轮盘赌的赌具是加特林。 加特林轮盘赌的规则很简单:在加特林的部分弹夹...
洛谷 P3239 / loj 2112 [HNOI2015] 亚瑟王 题解【期望】【DP】
???看不懂的期望DP 题目描述 小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。 他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周...
hdu 5194 DZY Loves Balls 题解【组合数学】【概率期望】【打表/找规律】【枚举】
这个题的做法实在是太多了,在我打完暴力水过后发现这个题的很多解法都是非常有价值的。 Description There are \(n\) black balls and \(m\) white balls in the big box. Now, DZY st...
Conjugate 题解【概率期望】【期望可加性】
是一道比较有水平的期望题,和AGC028B很像。 题目描述 在不存在的\(\text{noip day3}\) ⾥,小\(\text w\)见到了⼀堆堆的谜题。 比如这题为什么会叫共轭? 他并不知道答案。 有\(n\)...
[2018.10 雅礼] v 题解【概率期望】【DP】【状态压缩】
这个题除了考期望、状压,考察的就是怎么压空间+时间了吧。 题目背景 \(\frac 14\)遇到了一道水题,又完全不会做,于是去请教小\(\text{D}\)。小\(\text{D}\)看了\(0.607\)眼就切掉了这...
AGC028 B – Removing Blocks 题解【概率期望】
一道区间统计问题。 Problem Statement There are \(N\) blocks arranged in a row, numbered \(1\) to \(N\) from left to right. Each block has a weight, and the weight of Blo...
牛客 202H 卡牌游戏 题解【概率期望】【递推】
是一道思路简单的期望题。 题目描述 小贝喜欢玩卡牌游戏。某个游戏体系中共有\(N\)种卡牌,其中\(M\)种是稀有的。小贝每次和电脑对决获胜之后都会有一个抽卡机会,这时系统会随机从\(N...
牛客 180B 烟花 题解【概率期望】【DP】【滚动数组】
式子简单的概率DP(算递推吧) 题目描述 小a有\(n\)个烟花,每个烟花代表着互不相同的颜色,对于第\(i\)个烟花,它有\(p_i\)的概率点燃,现在小a要去点燃它们,他想知道产生颜色的期望个数及...