高手算法专项训练-期望问题
T1 猫抓老鼠
我们可以设猫在 点 \(u\) 老鼠在 \(v\) 点时猫抓到老鼠的期望时间为 \(f_{u,v}\) ，设此时猫的目标点为 \(next_{u,v}\) ，而这个 \(next_{u,v}\) 很显然可以在跑 \(n\) 便 BFS 。注意 \(f\) 的转移顺序显然由 \(u, v\) 的距离来决定。所以我们将 \(u,v\)之间的距离从小到大转移 \(f\) 。
那本题的时间复杂度就为： \(\Theta(n^2)\)。
T2 圆桌游戏
求：不经过 \(n\) 且标记了 \(1\sim n-1\) 的一个概率。那这样子我们设 \(f_{l,r,0/1}\) 来表示已经标记了 \([l,r]\) 且最后一次标记的点在区间的最左边 或 最右边的概率。在转移之前需要先计算出来 \(g0_{i,j}(i\le j)\) 表示 \(j\) 最终走到 \(j +1\) 且在过程中不能走到 \(i\) 的左侧的概率，设 \(g1_{i,j}(i \ge j)\) 表示 \(j\) 最终走到 \(j - 1\) 且在过程中不能走到 \(i\) 右侧的概率。时间复杂度：\(\Theta(n^2\log P)\) , AC不了。
考虑 \(1\) 和 \(n-1\) 这两个特殊的位置，最后一个被标记的点一定是其中之一。也就是说，我们并不关心 \((1,K)\) 和 \((K,n-1)\) 的这些点是什么时候被标记的。考虑三个相邻点 \(a,b,c\) ，我们可以快速计算出标记在 \(a\) 手上时不走到 \(a\) 的左侧且通过 \(b\) 走到 \(c\) 的概率 以及 标记在 \(c\) 手上时不走到 \(c\) 的右侧且通过 \(b\) 走到 \(a\) 的概率 ，计算方法同上。
之后我们令 \(p_a = x,1-p_c=y\) ，相当于删去了点 \(b\) ，和原问题等价。
我们把 \(1\sim n-1\) 中除 \(1,K,n-1\) 以外的点全部删去，分几种情况讨论：
1. 若 $K = 1$ ，则答案为 $p_K$ ；
2. 若 $K = n - 1$ ，则答案为 $1 - p_K$ ；
3. 若 $1 < K < n-1$ 且 $1$ 先被标记，把 $K$ 删去后答案为 $(1-p_K)p1$ ;
4. 若 $1<K<n-1$ 且 $n -1$ 先被标记，被 $K$ 删去后答案就为 $p_K(1-p_{n-1})$ 。
这样正解时间复杂度就为 \(\Theta(n \log P)\) 。
T3 取数方案
记区间 \([l_i,r_i]\) 中大于等于 \(f_i\) 的数的个数为 \(cnt\) ,区间长度为 \(len\) 。
\[\begin{array}{l} \frac{1}{l e n} \sum_{i=1}^{c n t} \frac{\left(\begin{array}{c} c n t \\ i \end{array}\right)}{\left(\begin{array}{c} \text { len } \\ i \end{array}\right)}&=\frac{1}{l e n} \sum_{i=1}^{cnt} \frac{\frac{c n t !}{i !(c n t-i) !}}{\frac{l e n !}{i !(l e n-i) !}} \\ &=\frac{1}{l e n} \sum_{i=1}^{cnt} \frac{c n t !(l e n-i) !}{(c n t-i) ! l e n !} \\ &=\frac{(\text { len }-c n t) ! c n t !}{\text { len } \cdot \text { len } !} \sum_{i=1}^{cnt} \frac{(\text { len }-i) !}{(c n t-i) !(\text { len }-c n t) !} \\ &=\frac{(\text { len }-c n t) ! c n t !}{l e n \cdot l e n !} \sum_{i=1}^{c n t}\left(\begin{array}{c} \text { len }-i \\ c n t-i \end{array}\right) \\ &=\frac{(\text { len }-c n t) ! c n t !}{l e n \cdot l e n !}\left(\begin{array}{c} \text { len } \\ c n t-1 \end{array}\right) \\ &=\frac{(\text { len }-c n t) ! c n t !}{\text { len } \cdot \text { len } !} \cdot \frac{\text { len } !}{(c n t-1) !(\text { len }-c n t+1) !} \\ &=\frac{c n t}{\text { len }(\text { len }-c n t+1)} \\ \end{array} \]时间复杂度 \(\Theta((n + m)\log n)\) 。
标签：高手,专项,frac,标记,cdot,text,len,算法,array From： https://www.cnblogs.com/messiljk/p/17587321.html