模拟赛 26 题解

树形dp+构造+期望+停时定理+cdq分治

A.路哥

首先我们可以求出所有权值为 \(k\) 的方案数总和,再除以 \(2^{n-1}\) 就是总期望。

可以树形dp,设 \(f[i][j]\) 表示当前考虑到 \(i\) 点,所拿的总和为 \(j\) 的方案数。

这样设状态,是按照 \(dfs\) 序进行推进的,所以每次处理儿子的时候要继承父亲的方案数。

每次回溯时,要把贡献统计到父亲上面,同时也要考虑不走这条边的方案数。

B.密电

设给出数组为 \(\{b_n\}\)。

那么排完序后,一定有:\(b_1=a_1+a_2,b_2=a_1+a_3\),不确定的只只有 \(a_2+a_3\) 和后面的关系。

这时候就可以枚举 \(a_2+a_3\) 的位置,这样就求出了 \(a_1,a_2,a_3\),并且剩下的最小的一定是 \(a_1+a_4\)。

那么知道 \(a_4\) 后,就可以删除 \(a_2+a_4,a_3+a_4\),这样剩下的就是 \(a_1+a_5\) 了,归纳就能求出答案。

C.战争

停时定理和鞅,不会。

D.送信

cdq好题。

我们观察到,给定的路径如果想产生贡献,那么询问的两个端点一定在它的子树里。

这里的"子树",是指连接这两个点的极大互斥连通块。

可以通过 \(dfs\) 序对此加以限制,设询问的两个路径为 \(x_i,y_i\),其中路径 \(x_j\rightarrow y_j\) 若能够产生贡献,则需满足:

\[\begin{cases} dfn[x_i]\in[l,r]\\dfn[y_i]\in[L,R]\\t_i>t_j \end{cases} \]

其中 \([l,r],[L,R]\) 的范围可以根据 \(x_j,y_j\) 的形态来讨论,这里可以画图理解。

之后这就是一个典型的三维偏序,直接上 cdq 就好了。

trick:cdq时要查 \(x\in[l,r]\and\ y\in[L,R]\) 的数对 \((x,y)\) 的数量,但因为第二维限制用双指针维护,不好统计。可以差分后统计 \([1,l-1]\) 和 \([1,r]\) 的即可。

另外 \(y\in[L,R]\) 这一限制也可以差分后树状数组,而避免线段树。

上一篇:洛谷 P3384 【模板】轻重链剖分


下一篇:CF487E Tourists(园方树+树链剖分)