2022/04/06 做题记录

CF494C

因为线段不相交于是可以建出一颗树，设 dp[i][j] 为 i 子树内最大值小于等于 j 的概率，发现 j 一定在 $\text{Max}_{i=l}^r a_i$ 到 $q+\text{Max}_{i=l}^r a_i$ 直接，于是可以平移一下 dp 数组，转移直接枚举这个区间加不加 1 就行，在这个区间内但没有被任何子区间覆盖的树可以暴力找，时间复杂度 $\text{O}(q^2)$。

code: /code/2022.4.6/CF494C.cpp

CF587C

因为 a 只有 10 暴力树上倍增维护前 10 小，归并排序合并。

code: /code/2022.4.6/CF587C.cpp

CF597C

因为 k 也只有 10 （？

所以维护 10 个树状数组就行。

code: /code/2022.4.6/CF597C.cpp

POJ3744

从后往前 dp，发现没有障碍的转移就是乘上一个矩形 $\begin{bmatrix} p & 1\\1-p&0 \end{bmatrix}$，而有障碍的转移实际上就是把这一位的 dp 值设为 0 ，于是可以在障碍间用矩阵快速幂转移。

code: /code/2022.4.6/POJ3744.cpp

方便的矩阵结构体：