[CF1236F]Alice and the Cactus

这个题做到心态爆炸了,一道div2的F做了一天,说明我太菜了。
一开始没想清楚,代码写了很长,根本调不出来,然后我只好把代码全部删掉重新开始写。
然后又写了一遍就过了。
首先方差等于平方的期望减去期望的平方,那么我们只需要维护期望和平方的期望即可。
看见仙人掌就先敲棵圆方树上去。
然后我们不妨定义一个操作结构体$Key$,这个表示一些元素的代价,假设有n个元素,第i个元素的概率是$p_i$,联通块个数为$x_i$,成员
$x0=\displaystyle\sum_{i=1}^n p_i$
$x1=\displaystyle\sum_{i=1}^n p_ix_i$
$x2=\displaystyle\sum_{i=1}^n p_ix_i^2$
然后用这个操作结构体定义数组$f(x,i)$(i只能是0,1,2),表示圆方树上以x为根的子树中向上有i个可链接联通块的剩余联通块的代价。
然后所有的转移都可以通过这个结构体的一些组合操作来完成。
具体看代码吧,真的烦。

Tagged with:

发表评论