MOCK NOIP 20221006 日志

策略和思维活跃度都极其糟糕的一个上午。

那么“在能力不足以保证完成更多正解”的情况下获取尽可能多的暴力分从而提高总分下限，又被重新提上议程。切记切记。

思维广度待进一步提升。

一句话题解

A – 道路

发现了是平面图，想到了数据结构与区间可达性，就是没把俩概念结合起来。

由题目保证的“两边不交”性质，可以发现，若不考虑无法从任何一个左侧点到达的右侧点，如有 $(A,y_1),(A,y_2),y_1<y_2$ 均可从 $(0,y_0)$ 达，则若有 $(A,y_3),y_3\in [y_1,y_2]$，则其必然亦可达。

缩点后拓扑排序求出每个连通块能到达的右侧点 $y$ 坐标区间即可。复杂度 $\operatorname(O)(n\log n+m)$。

B – 地震后的H市

联想到了 HDU “杭电杯”超级联赛（3) Spanning Tree Game 钦定最小生成树，按边权从小到大依次加边的动规方法。

可惜这是最小瓶颈生成树。

解一（刘晟林）

设 $P(x)$ 表示答案不大于 $x$ 的概率。则它等价于，将所有边权 $\leq x$ 的边全部激活，整张图联通的概率。

设 $f(i,S)$ 表示“只考虑了（输入编号）前 $i$ 的边，钦定了其中的一些边，这些边能构成 $S$ 的连通块，且该连通块内部所有边均”的概率权值。由于这是瓶颈生成树，只要边权不超过 $x$ 均能激活，则对于一个确定的方案，我们总是按照边的编号从小到大的顺序依次两两合并连通块。

转移似乎应当分为“第 $i+1$ 条边是/不是桥接两连通块的最小编号边”处理。

然后发现 $P(x)$ 是一个 $m$ 次多项式函数。将它通过 DP 暴力求出后按照期望定义作积分转化。

概率分布函数（Probability Distribution Function）描述了在样本空间 $\Omega$ 中随机变量 $X$ 在各取值的分布。

• • 它是一个可测函数。
  • （对于实数随机变量 $X$）有 $\int_{-\infty}^{x}f_X(y)\mathrm{d}y=F_X(x)$，$F_X(x)$ 称为 $X$ 的累积分布函数。

我们欲求取 $E(X)=\int_{0}^{1}xf_X(x)$，但现在仅知道 $F_X(x)$。但容易发现有 $$\begin{aligned} F_X(x)&=\int_{0}^{x}f_X(y)\mathrm{d}y\\ \int_0^xF_X(y)\mathrm{d}y&=\int_{0}^{x}\left(\int_0^y f_X(z)\mathrm{d}z\right)\mathrm{d}y\\ &=\int_{0}^{x}(x-y)f_X(y)\mathrm{d}y\\ E(X)&=1-\int_0^1F_X(x)\mathrm{d}x \end{aligned}$$

多项式积分计算即可。被 std 反向卡了精度

解二

在随机变量取实数的题目中，常只考虑每个变量之间的相对大小关系作为突破口。——毛周祥，李枨夏

我们希望计算出“恰选取边权最小的 $k$ 条边，使得全图连通，且第 $k$ 小的边合并了两不相连连通块”的概率。辅以题目中所述

$n$ 个 $[0, 1]$ 中均匀分布的随即变量，第 $k$ 小的期望值是 $\dfrac{k}{n+1}$

的性质，即可计算总期望。设 $f(S, k)$ 表示“选取 $k$ 条边使得 $S$ 连通的方案数”，转移时容斥（用“任选”的总方案减去不连通的方案，枚举某个固定点所在连通块）即可。最后钦定边 $(x_i,y_i)$ 是第 $k$ 小，枚举合并即可。

C – 求和

解一

赛时解法。经典“单调栈更新权值作区间加”。

读错题后发现仍然可以做，只不过变成了维护差分的区间和而已。

解二

ST 表。将询问转化为若干个“区间 $[l,r]$ 的所有子区间的 $\max\{a_i\}-\min\{a_i\}$ 之和”容斥，利用“区间最值”和函数的前缀和巧妙处理单个区间的上述询问。

具体实现可以阅读徐哲晨的代码。

D – 最短路

内向树森林。可以发现每棵树的叶子节点必连边。拓扑排序时贪心地从 $1$ 号点向每个“不得不连边”的节点连边，正确性显然。

难点在于环上如何处理。可以通过子树内最短路处理出环上哪些点已经合法，哪些点非法，然后用“长为 $k$ 的纸带” 覆盖环上每个非法点。（赛时在这里卡住。考虑了“断环成链”DP，但没法快速处理跨立断裂处的纸带的情况。）

如果用刷表法处理出“点 $x$ 以后最近的非法点位置”，钦定一个起点，可以在 $\operatorname{O}(\frac{n}{k})$ 的时间内完成一次模拟。则任取一个非法点 $x$，必然有 $x,x-1,\cdots,x-k+1$ 中的某一个为最优解中纸带期间。暴力模拟 $k$ 次，复杂度 $\operatorname{O}(n)$。

（额外的无用性质：任何一点开始作一次模拟，得到的结果至多为 最优解个数 $+1$。）