多省省选联考全真模拟考试5

http://csp.ac/contest/13

这次T3确实写炸了怪我,要不然就和ljh差不了几分了QAQ

首先简化题意,变成有向图动态加单向边,然后询问第一次出现环的时候qwq

然后做法就是首先考虑这个问题可以二分答案,就是使用小于mid的所有边能构成一个环,那么大于mid的也可以

然后再去考虑怎么快速判断这个环啊?就直接O(n)拓扑排序一下啊,然而这样好像t掉了?

所以我们要建一下虚图,虚图是啥子?就是我们倍增一个长度然后考虑这个状态下能不能有环,可以O(n)

如果有环就可以直接二分一下,然后找到一个合法答案,最后再去清空

因为这样我们可以满足每次进行拓扑排序的点数不会很大,所以均摊复杂度是 $O(mlogm)$

这个期望题就直接弃了真的好

首先我们要考虑下k小的那部分点

可以设计 $f_i$ 表示从品质i到品质n的期望, $P_i$ 表示到i个品质概率

那么转移就是 $f_i=c_i+\sum_i^n{P_if_j}$

然后我们可以发现后面那个东西没有用 $S=\sum_i^n{p_jf_j}$

$f_i=c_i+S$

$S=\sum_j^n{p_j(c_j+S)}$

然后 $S=\frac{\sum_j^n{p_jc_j}}{1-\sum_j^{n-1}p_j}$

最后这样就有30了

再想想k=2 ?算了吧,虽然有但是细节不完美

把这个品质先按照 $C_i$ 排序

考虑正解,我们想,首先第一步情况下给定品质1( $C_i$ 最下)去重铸一定很优,然后如果重铸到了n就直接结束啦

然后我们重铸1的同时会产生一些随机品质,随机品质随到2~n-1,这个随机品质随到n是第二歩

设 $f_i$ 表示以第一步gg的概率,然后 $g_i$ 表示总的期望次数

然后求这个 $f_i$ , $g_i$ ?

你会发现仔细观察后是这个式子

f_1=\frac_{p_n}{1-P_1}{g_1}

然后这个式子的意思就是一枪打中概率为p,f为打中的总概率,g为打中期望几发,p, $f=p*g$

所以最后我们就可算出ans1,然后递推到ansn的每个系数了

正解是数据结构优化合并操作

合并操作就是{(x and u)xor v}

然后这个x是运算后面的数,u是进行操作的那个前面的数,v是为了达到某个and或者or而要调整的参数

所以这样所有的位运算都能处理出并合并了

然后我们发现一条链是可以通过线段树满足一个区间的信息支持一个点

最后树上可以树剖,然后一条重链直接跳改向祖先信息,其他的轻儿子可以线段树维护

最后全局平衡二叉树可以维护mlogn

夏晓光(loveJY)的博客