华中地区 19th 做题笔记

A

难度：medium easy

区间 dp+期望板子。

最开始看错数据范围，以为平方复杂度过不去，然后思考了半小时未果，发现看错数据范围了。

期望题目倒过来做，如果正着做还要同时算概率很麻烦。设 $f_{l,r}$ 为区间 $[l,r]$ 向外扩展之后发生共鸣的期望次数。转移显然有：

$$f_{l,r}=\frac{w_{l-1}}{w_{l-1}+w_r}\cdot(f_{l-1,r}+[p_{l-1}\gt\max_{i\in[l,r]}p_i])+\frac{w_{r+1}}{w_l+w_{r+1}}\cdot(f_{l,r+1}+[p_{r+1}\gt\max_{i\in[l,r]}p_i])$$

。注意 $[s,s]$ 的贡献也是 $1$。

B

难度：medium

注意到路径可以重边，所以在非二分图中可以通过不断绕奇环去改变原有路径长度的奇偶性，也就是非二分图中任意两个不同节点都同时存在长度为奇和偶的路径。相反地，在二分图中任意两个不同节点只存在长度为奇或长度为偶的路径。

如果当前节点 $a_p$ 所在联通块为非二分图，那么只要满足 $a_i$ 在当前联通块内的 $a_i$ 都能够到达。相反地地，如果当前节点 $a_p$ 所在联通块为二分图，满足 $a_i$ 在当前联通块内的同时，满足下列两个条件之一：

• $a_i$ 和 $a_p$ 路径长度为偶数，$i$ 和 $p$ 奇偶性一致；
• $a_i$ 和 $a_p$ 路径长度为奇数，$i$ 和 $p$ 奇偶性相反。

不难发现，无论是二分图还是非二分图，$a_i$ 的连通都具有传递性，即：

传递性：若 $a_i,a_j$ 能够互相到达，且 $a_j,a_k$ 能够互相到达，那么 $a_i,a_k$ 也能够互相到达。

那么我们发现实际上由 $a$ 序列建出的图是若干的完全子图。由于题目中的询问带有下标严格递增的限制，所以子完全图有了方向，变成了传递竞赛图。作为先手只有开局无路可走才会输，否则只要一步跨到最远点就必赢。即只要查询 $a[l+1\dots r]$ 中是否存在与 $a_l$ 在新图中同一完全子图就可以了。离线不难处理。