概率与期望DP
绿豆蛙的归宿
DAG上求起点到重点的期望路径长度
设 \(F[i]\) 表示从\(i\)到\(n\)的期望步数
显然\(F[n]\)为零,转移则为
\(F[i]=\sum_{son(j)}{(F[j]+dis_{i,j})/DEG[i]}\)
在DAG上做拓扑排序进行转移即可
较为水
聪聪和可可
老鼠的走法就是随机走一个点或者停留
考虑猫的走法,当鼠猫距离大于二时,猫这一轮一定会走两步,否则这一轮就结束了,猫的走法比较梦幻,所以考虑\(N\)次\(dij\),再\(n^2\)预处理出来当猫在\(A\)老鼠在\(B\)时猫的下一步去哪,时间可以承受
设\(F[i][j]\)表示当猫在\(i\)老鼠在\(j\)时的期望值,因为终止状态有很多,而起点只有一个,发现并不好转移,直接记忆化搜索一发
注意判断特判已经在同一个点的情况
Easy || OSU!
题意基本相同
记录到\(i\)次点击连续o的长度期望,分类讨论本次是否comb转移即可
OSU中则是需要分别考虑二次和三次的贡献,分别拿两个数组记录,同样讨论本次是否comb转移
Red is good
设\(F[i][j]\)为当前有\(i\)张红牌\(j\)张黑牌的期望
当前轮怎么拿牌
显然对于状态\(F[i][0]\),我一路拿下去肯定最优,直接就是\(F[i][0]=i\)
同样的状态\(F[0][j]=0\),怎么拿都亏就一张都不拿
对于F[i][j],我们考虑这一轮拿到了什么牌
若拿到红牌,则转移到\(F[i-1][j]\),转移到这一状态的概率为\(\frac{i}{i+j}\)
若拿到黑牌,则转移到\(F[i][j-1]\),转移到这一状态的概率为\(\frac{j}{i+j}\)
那么就有
但是题目要求最大值,那么在拿牌过程中,如果我发现我会亏,那我就索性前边的都不要了,从头拿起.即认为前面的牌期望值为0,就相当于F[0][0]
然后我们快乐的发现可以DP了
快乐的发现A了
守卫者的挑战
设\(F[i][j][k]\)为当前进行到的场数,之前赢的场数,和当前背包剩余容量分别为\(i,j,k\)的成功概率
我觉得并不好转移就记搜了
当当前场数为\(n+1\)时判一下赢场数和剩余容量是否符合要求即可
单选错位
我们发现第\(i\)道题有没有贡献只和它与第\(i-1\)道题的答案是否相同有关,我们只需要相同发生的概率并求和即可,假期望,需要特殊处理一下\(1\)和\(n\)
列队春游
我们单独考虑每个人的贡献,设当前考虑的人为\(A\)
对于除他以外的人,发现所有不比他低的人一定不能对他作出贡献(我们认为一定有的贡献1是他自己对自己作出的)
那么\(A\)产生的贡献实际上就是 \(A前面连续的比A低的人数*发生的概率\)
设队列中一共有\(m\)个人的身高 ≥ \(A\) 的身高(包括\(A\))
那么这\(m\)个人无论如何排列都不会对\(A\)产生贡献
我们再去考虑剩下的\(n-m\)个人对\(A\)的贡献,设人数为\(s\)
若单独考虑每个人的贡献,因为实际上每个人只能对\(A\)贡献一个单位长度,当这个能对\(A\)产生贡献时,无论其他的人如何排列,都不会影响他对\(A\)产生的贡献,那么我们就考虑这个人什么时候对\(A\)产生贡献
先排那\(m\)个人,共有\(m!\)种方案,这时我们先将\(s\)中的一个人与\(A\)绑定,视为一个人,参与这\(m\)个人的排列,此时我们保证了这个人一定对\(A\)造成贡献,其他情况一定不会造成贡献
再考虑剩下的\(s-1\)个人,他们此时不管如何站,都不会再对刚才绑定的那个人的贡献造成任何影响,有\(A_n^{s-1}\)种站法
至此我们找出了这个人所有可能对\(A\)作出贡献的方案,实际上所有比\(A\)低的人贡献都是如此
那么\(A\)的贡献就是
扫一遍求和即可
矩形粉刷
我们发现\(K\)次粉刷间是有前后影响的,即同一个点可能被粉刷多次但是只贡献一次(虽然我开始并没有考虑这个,然后就发现没法处理了)
那么我们单独考虑每个格子的贡献,某个格子有贡献,即其至少被粉刷到了一次,我们发现这玩意并不好算,实际上格子是否被刷是对立事件,那么有
那么我们求出\(K\)次都不被粉刷的概率就好了,这个显然更好求,即为
再考虑这个格子怎么样不会被粉刷到
某次粉刷到的两个格子都在 上上/下下/左左/右右
但是我们发现 \(上左/上右/下左/下右\) 的概率被算了两次,那么简单容斥一下,减去重复的即可,格子间是没有相互影响的.
最后用1减去求出的概率即为该格子的贡献,概率值即为期望
卡牌游戏
留坑以后写
换教室
实际上就是大分类讨论,我们首先需要预处理出来教室两两间的最短距离,跑一遍\(Floyd\)哦了
发现前面申请成功的概率会对后面算期望造成影响,且需要限制申请次数
那么设\(F[i][j][0/1]\)表示当前到第几节课,之前已经申请了多少次,本节课是否申请了的期望值
分类讨论当前是否申请,上一次是否申请了(注意\(j\))
同时需要讨论这次申请是不是成功了,以及上一次是否成功了(如果申请),因为成功与不成功的距离是不同的,而且申请是有成功概率的,我们不能默认某一次申请成功
可能说不太明白,可以举例说明但是分类讨论过程太ex了,下次吧(bushi
奖励关
状压一下
设\(f[i][j]\)为在第\(i\)回合达到拥有的宝物状态为\(j\)的期望分值
我们考虑当前状态中每一位\(1\)是第一次出现,还是已经出现过(需要注意回合数的限制)
分类讨论即可
好的我们发现这个做法是假的
惊不惊喜,意不意外
这样的转移可能会出现,我们需要的上一阶段的状态可能根本是不可达的,因为有宝物先后关系,那么我们考虑逆推,即从一定可达的状态推到之前的状态
设\(F[i][j]\)表示当前\(i-1\)轮所拿到的宝物状态为\(j\)时,第\(i\)轮到第\(k\)轮能获得的最大期望值
那么我们分别考虑第\(i\)轮会抛出哪个物品,即每次转移都遍历所有物品,若其满足要求,那么有转移式
即表示当前 \(选/不选\)
若不满足要求则直接继承\(f[i+1][j]\)即可,当前阶段选不到,下一个阶段也一定选不到
最后答案即为\(F[1][0]\)
概率充电器
一开始没看数据范围以为高消一发就能过,这不嘎嘎切么
既然高斯消元不行,那么我们就树形DP(题目都明示了)
考虑每个原件是如何来电的
他自己来电了 / 他儿子来电了并且通过来了 / 他爹来电了并且通过来了
原件通电的概率是三个事件至少发生一个的概率
那么就不能直接相加,虽然我第一遍交就是直接相加的,还对了几个点
有 事件\(A,B\)至少发生一件的概率为
其实就是简单容斥
设\(d[i]\)为只考虑儿子传导即自己来电时的概率
\(f[i]\)为所有情况的概率
第一遍DFS先求出\(d\)数组,把自己的概率以及每个儿子的概率以此用上边的式子算就行
第二遍DFS考虑加上父亲传导后的概率,显然树根的f和d相同
求\(i\)点时,将他父亲的\(f\)除去\(i\)贡献的部分,再将其视为\(i\)的儿子贡献给\(i\)即可
注意判断某个原件的概率是不是超过$1$了,当然如果某个点的$d$已经是$1$了,那么就没必要算了,直接赋$1$接着向下搜即可
硬币游戏
自己想不出来系列
我们发现这个游戏可能是无穷无尽的,所以状态设定中一定不能包含他在什么位置赢的
那么我们某个人在什么情况下会赢.
假设当前的一个未终止局面为\(S\),显然\(S\)不完全包含任何一个人的序列.
我们考虑两个人的情况,假设有\(A=101\),\(B=110\)
如果局面进行成\(S+A\)那么此时A一定胜出了,但是可能存在一种情况,也就是局面朝\(S+A\)方向进行时,中间出现了形如\(S'+B\)的情况(我们定义S类都是未终止局面),也就是说,在\(A\)胜出之前,已经有\(B\)胜出,提前终止了.
设出现未终止局面的概率为\(P_0\),如果不考虑提前终止的情况,那么\(P_A = \frac{1}{2^m}*P_0\),实际上这样的话,每个人胜出的概率都如此.
那么现在考虑如何把提前终止的概率删去,我们发现两两终止状态之间无包含关系,或者可以理解为对立事件,那么说我们在总概率中减去提前终止的那部分概率,就是我们希望的终止局面的概率.
就考虑提前终止的情况,显然是\(A\)的前一部分和另外某个人的串恰好接上了,字符串意义上就是\(A\)的一段前缀与某个人的一段后缀相匹配,若有长度为\(k\)的串满足,那么提前结束的概率就是\(那个人胜出的概率*序列末尾出现那个人的前(m-k)个字符的概率\)
这样我们就有\(n\)个方程组,\(n+1\)个为止数,what hell?
然后我们就死在了寻找最后一个方程的路上
实际上,当这个游戏无穷尽的进行下去后,一定会有一个人胜出,或者说所有人的胜率和无限趋近于\(1\)
那么我们就得到最后一个方程了,\(\sum_{i=1}^{n} {P_i} =1\)
快乐敲一个高消板子欧了
码完之前不看
如果你码完又交了一发发现只有40分
而且后面的点全是零
~~去把这句话注释掉~~
`if(fabs[i][i]<eps)continue`
然后你就A了
为什么?
布吉岛(bushi
我们发现某些系数可能很\(小_{小_{小_{小}}}\),
小到\(\frac{1}{2^{300}}\),
好了你把所有的都\(continue\)了,
所以不能特判
那真的有0怎么办