qwq

qwq

最近发现数位dp其实挺常见的，这里会陆陆续续把自己见到的数位dp放在这里一起总结。

#题目链接

H - RMQ Similar Sequence

#题意简述

定义RMQ(A,l,r)为：序列A中，满足A[i] = max(A[l],A[l+1],…,A[r])的最大的i。如果对于任意(l,r)都满足RMQ(A,l,r)=RMQ(B,l,r)则为A和B是RMQ Similar。现在出A序列，B串中每个元素服从于[0,1]上相互独立的均匀分布。问满足与A是RMQ Similar的所有B序列中所有数之和的期望。(转载)

A、B、C略

D - Choose Me

设$S$为选择的进行演讲的城镇的集合。那么两个人的选票差为
$$
\sum_{i\in S}(2\times a[i]+b[i])-\sum_{i=1}^na[i]
$$
要使T的选票多于A的选票，即找到一个元素最小的集合$S$，使得该式大于0。

单调队列主要用于求连续子区间的最值，可以将大大降低dp中的复杂度。

#题意简述

一个无向图，节点1有一个炸弹，在每个单位时间内，有p/q的概率在这个节点炸掉，有1-p/q的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。

#题意简述

求一棵树上u点到v点路径上所有点权的k次方和。

#题目链接

D - Bouquet

#题意简述

有$n(2≤n≤10^9)$种花，每种花一枝，求可组成除了含有$a、b$枝花外共多少种花束。

找机会填F题的坑w