PKUWC2018题解

按照\(\texttt{loj}\)的顺序写的

「PKUWC2018」Minimax

比较神仙的线段树合并,可能是我对于线段树合并还了解的不够透彻吧.

很显然可以对于每一个点的取值离散化后\(dp\)概率对吧.

\[ \begin{align} dp_{u,i}&=dp_{l,i}\times(\sum_{j=1}^{i-1}dp_{r,j}*p+\sum_{j=i+1}^{tot}dp_{r,j}*(1-p))\&+dp_{r,i}\times(\sum_{j=1}^{i-1}dp_{l,j}*p+\sum_{j=i+1}^{tot}dp_{l,j}*(1-p)) \end{align} \]

这个东西的转移需要一个前缀和一个后缀和.

然后线段树合并的套路就是对于这个东西在合并左右子树线段树的时候记录一个和.如果要返回直接打乘法标记上去.

很清奇

代码

「PKUWC2018」随机算法

比较容易的状压题.

考虑一个独立集的大小可以\(dp\),那么我们边\(dp\)独立集大小边\(dp\)概率.

考虑将一个点插入最后一个位置(即排列的最后一位),这样子的概率是\(|S|\)的,可能性是\(\sum_{S'}f_{S'}\)

那么如果最大独立集大小更新了,\(f\)数组也要清零.

代码

PKUWC2018题解

原文：https://www.cnblogs.com/fexuile/p/11965452.html