牛客练习赛131题解

A 小H学语文

将木板长度降序排序，遍历枚举 $h_{min}$ 计算即可。时间复杂度： $O(n\ \mathrm{log}(n))$

B 小H学数学

记 $f_{i,j}$ 为前 $i$ 个人凑成数字 $j$ 的方案数，枚举每个人可能表示的数然后线性DP即可。
时间复杂度： $O((20\ y)^2)=O(400\ y^2)$

C 小H学生物

记 $d_i$ 为从根节点到 $i$ 节点路径上的变异信息异或和，由与异或运算的性质可知 $d_i \oplus d_j$ 得到的结果就是节点 $i$ 到节点 $j$ 简单路径上的变异信息异或和，因为根节点到 $k=\mathrm{lca}(i,j)$ 节点上的变异信息异或两次抵消了。先进行一遍DFS计算出 $d_i$ 。
由异或的性质，有任意的 $D_{a_i,a_j} = d_{a_i}\oplus d_{a_j}$ , 同时 $D_{a_i,a_j} \oplus D_{a_i,a_k} = D_{a_j,a_k}$ ，
根据奇偶分类讨论观察规律，故结果可表示为：
$\bigoplus\limits_{i=1}^{m-2}\bigoplus\limits_{j=i+2}^{m} D_{a_i,a_j}=\begin{cases}D_{a_1,a_m}, & m\text{为奇数}\\ \bigoplus\limits_{i=2}^{m-2}D_{a_i,a_{i+1}}, & m\text{为偶数} \end{cases}$
时间复杂度： $O(n)$

D 小H学物理

可以发现发射的 $x$ 会修改设备上 $y$ 位置上的能量，当且仅当 $x \equiv y \pmod{\lambda}$ 。
因此考虑将模 $\lambda$ 的剩余类构建 $\lambda$ 个新的数组。每次区间修改，则在其中一个数组上进行区间修改；区间查询，则遍历所有数组计算对应的区间查询累加即可。
问题中区间修改为区间加上一等差数列，等差数列做一次差分可以发现是一个全 1 数列，因此可以考虑使用三阶差分-前缀和解决该问题。
考虑原数组为 $a$ ，三阶前缀和分别为 $b,c,d$ 。
$b_i=\sum_{j=1}^{i}a_j， c_i=\sum_{j=1}^{i}b_j，d_i=\sum_{j=1}^{i}c_j$
在数组 $d$ 区间 $[l,r]$ 上增加一个首项为1，公差为1的等差数列等价于修改:
$a_l = a_l + 1，a_{r+1}=a_{r+1}-(r-l+2),a_{r+2}=a_{r+2}+(r-l+1)$
题目中是在区间 $[l,r]$ 上增加递减等差数列，只需要将 $l,r$ 在查询和修改时都对称翻转即可。
考虑三阶前缀和计算：
$\begin{aligned} d_{k} & =\frac{k(1+k)}{2} a_{1}+\frac{(k-1) k}{2} a_{2}+\ldots+\frac{(2+k-i) *(1+k-i)}{2} a_{i}+\ldots+\frac{3}{2} a_{k-1}+a_{k} \\ & =\frac{(k+1)(k+2)}{2}\left(a_{1}+\ldots +a_{k}\right)-\frac{2 k+3}{2}\left(a_{1}+2 a_{2}+\ldots+k a_{k}\right)+\frac{1}{2}\left(a_{1}+4 a_{2}+\ldots+k^{2} a_{k}\right)\\ & =\frac{(k+1)(k+2)}{2}\sum_1^k a_i - \frac{2k+3}{2}\sum_1^k i * a_i + \frac{1}{2}\sum_1^k i^2 * a_i \end{aligned}$
因此对每个数组都维护三个树状数组即可。
时间复杂度： $O(K\lambda \ \mathrm{log}\frac{L}{\lambda})$

E 小H学历史

$A, B$ 之间的边直接断开，因此树上只剩下 $Z,A$ 和 $Z,B$ 之间的边。因此每一个 $Z$ 连通块都是独立的，如果该连通块连接的只有 $A$ ，或只有 $B$ ，那么将完全被 $A$ 或 $B$ 占领，因此只需要考虑连通块的端点上既有 $A$ 也有 $B$ 的情况。
由于每个端点都是 $A$ 或 $B$ , 记此时 $Z$ 节点的数量为 $|Z|$ ，那么 $A,B$ 节点的分配情况取值为连续的 ${(|Z|,0),(|Z|-1,1),\dots (0,|Z|)}$ 。
证明：考虑 $A$ 将所有 $Z$ 节点占领。然后从某个 $B$ 节点开始扩张，如果遇到分叉节点 $Z$ ，可能存在多个分支，而分支端点只有两种情况 $A$ 或 $B$ 。如果某分支的端点是 $A$ 节点，则逐步占领到端点即可；如果某分支端点是 $B$ 节点从分支端点 $B$ 向分叉节点逐步占领即可，这样避免 $A$ 端点分支无法走到情况，因此可以分配到连续的所有情况。
因此，DFS遍历所有 $Z$ 连通块，如果相连只有 $A$ 或 $B$ ，则纳入两国城池总数 $tot_A, tot_B$ 中。如果相连既有 $A$ 也有 $B$ ，则纳入无主城池总数 $tot_Z$ 中。
记 $dif=|tot_A-tot_B|$ ，若 $dif > tot_Z$ ，则答案为 $dif-tot_Z$ 。否则，答案应为 $(dif + tot_Z) \pmod{2}$ 。
因为若 $tot_Z$ 为奇数，对 $dif$ 只能贡献小于等于 $tot_Z$ 的奇数值，反之亦然。
时间复杂度： $O(n)$

F 小H学地理

记 $E(x_i), E(x_i^2)$ 表示从起点走到 $x_i$ 次数的期望和次数平方的期望，显然 $E(x_n)=1,E(x_n^2)=1$ ，为常量因此以下分析不考虑点 $n$ 。考虑走到每个点 $i$ 的次数应该是领域 $N(i)$ 的所有点走到点 $i$ 的次数之后，
因此有, $E(x_i) = \begin{cases}\ \sum_{j\in N(i)} p_{ji} E(x_j)，& 1 < i < n, \\ 1 + \sum_{j\in N(i)} p_{ji} E(x_j), & i=1. \end{cases}$
其中 $p_{ji} = \frac{1}{deg_j}$ ，由于起点首先就访问一次，因此加 1。构建次数期望矩阵 $\mathbf{E}$ ，其中 $\mathbf{E}_{i,j}$ 为从 $i$ 点出发到 $j$ 点的期望次数。概率矩阵 $\mathbf{P}$ ，其中 $\mathbf{P}_{i,j}$ 为从 $i$ 点走向 $j$ 点的概率。因此有：
$\mathbf{E}=\mathbf{E}\mathbf{P}+\mathbf{I} \\ \mathbf{E}(\mathbf{I}-\mathbf{P})=\mathbf{I}\\ \mathbf{E}=(\mathbf{I}-\mathbf{P})^{-1}$ .
考虑平方的期望有公式如下：
$E[(x+1)^2]=E(x^2)+2E(x)+1$ 故有， $E(x_i^2)=\sum_{j\in N(i)}p_{ij}(E(x_j^2)+2E(x_j)+1)$ 。
构建次数平方期望矩阵 $\mathbf{S}$ ，因此有： $\mathbf{S}=\mathbf{P}\mathbf{S}+2\mathbf{P}\mathbf{E}+\mathbf{I}\\ (\mathbf{I}-\mathbf{P})\mathbf{S}=2\mathbf{P}\mathbf{E}+\mathbf{I}\\ \mathbf{S}=(\mathbf{I}-\mathbf{P})^{-1}(2\mathbf{P}\mathbf{E}+\mathbf{I})$ .
然后采用高斯消元进行线性变换或求解期望矩阵逆元即可。
计算出 $n$ 个点的期望次数和平方期望次数，然后和 $n$ 个 $(a,b)$ 对使用 $KM$ 算法进行二分图最大权完美匹配即可。
时间复杂度： $O(n^3)$