LOJ targeted training: DP & Probability & Expectation

Posted on Edited on

LOJ定向练习(DP & Probability & Expectation)

#2112. 「HNOI2015」亚瑟王

如果直接对这个游戏过程DP, 是非常困难的, 我们可以直接考虑终局时选择到每一张牌的概率.

需要考虑两种情况: 1. 某一回合选的牌在他之前(不考虑他). 直接放到状态里 2. 这张牌在前面和回合中已经用过了. 补集转化即可.

#2136. 「ZJOI2015」地震后的幻想乡

利用第k大数的期望公式(题目中给出), 枚举MST中瓶颈的大小, 乘上概率即可. 容易求出MST\(\le k\)的概率(子集DP), 考虑差分转化.

#3312. 「ZJOI2020」传统艺能

考虑分别考虑每一个线段树上节点有标记的概率. 利用线段树上定位区间的性质, 利用人类智慧+矩阵快速幂过题.

#6495. 「雅礼集训 2018 Day1」树

数据范围诈骗! 直接递推!

#6406. 「ICPC World Finals 2018」绿宝石之岛

行列转置, 降低复杂度.

#2542. 「PKUWC2018」随机游走

关于树上随机游走问题:

法一: 计算边权. 期望距离依然具有可加性(考虑按照第一次经过中间点的时间划分) 于是可以使用up and down trick算出每条有向边的期望长度. 这样可求任意路径的长度.

法二: 树形消元解方程 考虑从终点出发倒着进行, 这样就可以列方程解出到每个点的期望. 树形消元的trick: 把起点当成根, 把儿子设成父亲的线性函数, 这样就可以dfs求出每个点的系数, 由于根没有父亲, 根的常数项就是答案.

#2145. 「SHOI2017」分手是祝愿

利用算术基本定理, 把因数关系看成高维前缀和, 剩下的部分就是一个一维的随机游走, 差分法解方程即可.

#3043. 「ZJOI2019」线段树

把操作1看成: 以\(\frac12\)的概率决定是否进行操作, 就可以利用 #3312 的方法做了.

#6509. 「雅礼集训 2018 Day7」C

TODO 解方程!

#6118. 「2017 山东二轮集训 Day7」鬼牌

推式子练习.