高度由习惯堆积

分类 算法:期望dp 下的文章

February 17, 2019

ZOJ3822 Domination

题目Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he bought a large decorative chessboard with N rows and M column...
February 17, 2019

HDU6410 序列期望

题目"看似随机,实则早已注定"——光羽度度熊有$n$个随机变量$x_1,x_2,...,x_n$。给定区间$[l_1, r_1],...,[l_n, r_n]$,变量$x_i$的值会等概率成为区间$[l_i, r_i]$中的任意一个整数。 显然这$n$个随机变量的值会有一共$\prod_{i=1}^{n} (r_i - l_i + 1) $ 种情况,且每种情况出现的概率为$\prod_{i=...
February 17, 2019

HDU5481 Desiderium

题目有一条数轴,还有一个区间的集合,集合大小为n。 现在等概率的从集合中选出集合的一个子集,求取出的子集的区间并集的期望长度。 空集的区间并长度被认为是0。答案乘以2^n后对1e9+7求余思路首先肯定是要离散化,然后单独考虑每一块最终对答案的贡献。那么每一块的贡献是多少呢?我们先算出一共有多少个集合包含了这一块的区间,那么最终的贡献就是$$ \sum_{i=1}^{cnt} 这些线段中有i条...
February 17, 2019

HDU4649 Professor Tian

题目给你一个式子,第i位(符号Oi和数字Ai+1)有pi的概率消失掉,要计算最后值的期望 运算符包括“&”,“|”和“^”思路本题之精髓所在就在于分步处理。我们并不需要整体来看最终的每个数出现的概率是多少,只需要看每一位上的1出现的概率是多少,整题的核心就是这一点。之后就是一波状压了。代码#include<bits/stdc++.h> #define M 205 using na...