期望与概率题目积累

就是从最简单的开始积累期望和概率题目

1 SPOJ Favorite Dice

一个 $N$ 面 骰子 问每一面都被甩到的 次数期望是多少。

考虑拥有一个包含i面集合时甩出来有以下的答案贡献,移项逆推 。

2 SGU 495 Kids and Prizes

$M$个人排队来取$N$个礼物 每个人打开的盒子 可能有礼物 也可能空 有礼物的话拿走礼物并放回盒子 没有礼物 直接放回盒子 问$M$个人取走礼物的期望个数

考虑前i个人 能够取到的礼物期望个数 显然第一个人为1

3 ZOJ 3640 Help Me Escape

现在有n个OI考场 每个考场有固定的水平 $C[i]$ 你是个喜欢炸鱼但是水平不怎么样的OI选手

你拥有初始战斗力 $F$ ,每天你会随机选一个考场炸鱼 如果你的 当前水平$F > C[i]$ 那么就会炸鱼成功

在炸鱼成功之后 你会装b $t [ i ]$ 天之后再回家

如果没有成功 你就会去OJ上刷题 将自己的水平提升到 $F + C[i]$ 然后次日继续随机挑考场炸鱼

问回家的期望天数

可以考虑战斗力是 $f$ 时回家的期望天数 于是得到公式

dp直接做不太容易啊….记忆化搜索一发就好了….

4 HDU4035 Maze

现在有一棵树 第一天在1号节点 对于每一个节点$i$有三种可能

$1. GG,回到点1 \space 对应概率为 K[i]$

$2.被救,\space 对应概率为 E[i]$

$3.等概率地走到相邻节点$

问被救走的天数期望 不能则printf $impossible$

这个题存在后效性

如果求$dp[S]​$ 那么$dp[S]​$ 和 $S​$ 的子节点以及父节点都有直接关系 去求子节点时又和$S​$ 本身有关系…

一开始以为要高斯消元 发现自己tooyoungtooNaive… N^3用个毛…

然后发现了厉害的方法….

找办法排除后效性 大概就是找个公式 然后公式本身和后效性有关 然后公式之间的后效性可以相互抵消…

然后就引用一发_kuangbin爷的….

设$E[i]$表示在点i处, 要逃出的边数期望。 那么$ans = dp[1]$

对于叶子结点来说

对于非叶子结点

然后再设对于每个节点来说

对于非叶子结点$i$ 设$j$为$i$的孩子,于是有

把上面的式子带进去 就可以得到

由此可得

然后用dfs做。

再来看个休闲题…..

5 CF 280C

给出一棵点均为白色的树 每次随机等概率选择一未染黑的点 将他及其子树染黑 问染黑整个树的期望操作次数

直接做不太好下手

所以考虑期望的线性性,$E(ax + by) = a \times E(x) + b \times E(y)$

所以问题就转化成求$\sum{ENode[i]}$

每次操作的权值都是1 所以就变成了求删除点$i$时恰好选中$i$的概率 , 也就是$\frac{1}{dep_i}$

dfs的时候一路加起来 就是ans了。

插曲 NOIP 2016 换教室

其实是突然想到这个noip题的….

屑题….

就是给你个v个点e条边的无向图 有n - 1条移动路线, 你可以使其中m个中间点$c[i]$ 变成相应的$d[i]$ 有成功概率$K[i]$

然后让你自己选m个中间点改动 使得期望路径长度最小…. n和m是2e3 v是2e2的

很显然要先跑一个Floyd

然后设状态 $f[i][j][0/1]$ 表示前i个要移动的目标点里要求了j个改动 0/1表示i申请或者没申请

分类讨论 ….

$f[i][j][0]$的话很明显就是从$f[i - 1][j][0]$ 和 $f[i - 1][j][1]$ 转移过来对吧 乘上相应的概率..

第一个就表示前一个也没申请 第二个表示前一个申请了

$f[i][j][1]$ 的话 要从$f[i - 1][j - 1][0]$和$f[i - 1][j - 1][1]$转移过来

和前一个状态转移一样 只不过分类讨论比较多 成功的组合上有四种 00 01 10 11 然后对应概率乘起来~

式子太长….

最后跑一下$min_{i = 0}^{m} {(f[n][i][1], f[n][i][0])} $ 就是ans了…

6 BZOJ 4008 亚瑟王

现在游戏有r轮 给你n张有序手牌 第$i$张牌的发动概率为$p_i (p_i∈(0, 1))$伤害为$d_i$ 每张牌整局游戏至多发动一次

每一轮中 都从第1张卡牌开始考虑 按顺序考虑每张牌

1 如果这张卡牌在这局游戏中已经发动过技能 那么

1.1 如果这张卡牌不是最后一张 , 就继续考虑下一张卡牌

2 否则 (在这一局游戏中没有发动过技能)

2.1 将其以$p_i$的概率发动

2.2如果发动成功那么造成$d_i$点伤害 并结束这一轮游戏

2.3如果已经是最后一张 ($i == n$) 就结束这轮游戏 否则考虑下一张手牌

求这套卡牌在这局游戏里造成伤害的期望值。

有T组数据。

$1 <= T <= 444, 1 <= n <= 220, 0 <= r <= 132, 0 < pi < 1, 0 <= di <= 1000$

好难啊…..

但是还是容易往这方面想对不对啊 , 期望的经典套路 还是把整体期望拆成个体期望然后求和…

设第$i$张牌被使用的概率为 $pb[i]$ 答案即为 $\sum_{i = 1}^{n}{pb[i] * d[i]}$ 考虑怎么算$pb[i]$这个玩意

很显然$pb[1] = 1 - (1 - p[i])^r$ $(1 - p[i])^r$就是一直没出过的概率。

后面的pb值显然要用dp求。

设 $f[i][j]$ 表示在$r$轮中前$i$张牌出了$j$张的概率 这个$f[i][j]$在枚举到$i$的时候一定是考虑不到$i + 1$ 的

所以

解释一下。 在考虑$f[i - 1][j]$的时候 只多只考虑到第$i - 1$张卡 从 $i - 1$张卡里 去挑 $j$张

这$j$张一定在i前 所以 在每张发动的牌$j$发动的那一轮 发动 完$j$后立刻结束这轮游戏 也就是说j

之后的卡都考虑不到 发动的几率是 0 ….(后面的卡全都咕掉了凸显了人类本质)

所以就容易想到 在$r$轮里有$j$轮一定考虑不到$i$这张牌 所以 有$r - j$轮考虑到了….

再来想$f[i][j]$咋算….

前$i$张卡 发动了$j$张 所以可以考虑 第i张卡是否成功发动。

没发动的话 有$j$轮没有考虑到$i$这张牌 所以是$r - j$次幂

没发动:

发动的话 需要从$j - 1$转移过来 所以有$r - (j - 1)$轮没有考虑到 用1 减一下就可以了..

发动:

时间复杂度 $\Theta (Tnr)$

一开始我写挂了怎么调都调不出来….后来才发现是快速幂…不过快速幂的确没毛病啊…不知道为啥快速幂就是错的…..果断换成了手动俩for 预处理1 - p[i]的pow…..1发a了…

再来看个简单的…

7 BZOJ 3143 游走

一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

$N <= 500$

嘛 很明显 经过期望次数多的边编号要小 然后就变成了求每条边经过的期望次数

那就先算点吧 两点互相走的概率加起来 也就是一条边两端点进入这条边的概率相加 就是经过这调边的概率

出发点是1 所以$f[1] = 1 + \sum_{to} {\frac {f[to]}{deg[to]}}$

其他点就是$f[i] = \sum_{to}{\frac{f[to]}{deg[to]}}$

哎有后效性啊凉凉…..

n是5e2的 正好跑高斯消元….

快乐……

然后经过每条边的期望次数

就是$ \frac{1}{deg[{e[i].u}]} \times f[e[i].u] + \frac{1}{deg[{e[i].v}]} \times f[e[i].v]$ 排个序就完事了….