DP（动态规划）

感冒咳嗽，头实在是太晕了，打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。

一句话题解

A – 破坏

简单的 $\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k)$ DP。记录每个节点的路径数奇偶性考虑是否翻转即可。

B – 共识

用 std::bitset 写的暴力大家都会。不过如果你胆子大些，不判断是否为部分分数据范围直接提交（加入随机化的）暴力，将喜提 $\text{100 pts}$。

命题：现有一个由 $2n$ 个元素构成的集合，保证 $2\mid n$。有 $n+1$ 个大小恰为 $n$ 的子集 $S_1,\cdots,S_{n+1}$。则至少存在 $n/2$ 对无序对 $(i,j),i\neq j, i,j\in[1,n+1]$，使得 $|S_i\cap S_j|\geq n/2$。

证明（引自宋佳兴学长）：记元素 $p,p\in\{1,\cdots,2n\}$ 在所有子集中出现的次数为 $\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)$。则显然有“所有子集两两之交的大小” $$\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}$$

考虑计算该式最小为何。不妨先考虑 $\binom{a}{b}+\binom{n-a}{b}$ 在何时取最小值。

引理：$\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq n$ 在 $a=\lfloor n/2\rfloor$ 处取最小值。

（更多…）

签到题看了半个小时；T2 没有考虑到只需要包含最优解即可，非要确定另一多余状态，只拿了部分分。

T3 只会考虑 “$x, y$ 的公共祖先中含有 $l$ 的概率”，不会高效计算“当二者的 $\operatorname{lca}$ 恰为 $l$ 时”的期望/概率与总长之和的乘积，仍然只有暴力分。

T4 无思路。

一句话（?）题解

A – 签到题

可以简单用归纳法证明，仅有所有管道中通行时间最大的会阻塞进度，是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。

B – 简单题

第一反应是类似笛卡尔树一样，在区间上依次合并区域最大值并计算贡献。$n \leq 300$ 似乎也在暗示这是一个区间 DP。

$\text{48 pts}$ 做法

设 $f(l,r,\text{mx})$ 表示“考虑完成区间 $[l,r]$ 内所有贡献，且最大值恰好为 $\text{mx}$”的最大权值和。转移时从小到大枚举最大值 $\text{mx}=V_{i,j}$，枚举包含它的区间，尝试转移 $$f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”)$$，其中 $\operatorname{calc}(l,r,i)$ 计算 $\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’}$，可以由二维前缀和实现。稍加演算会发现，这样转移不会重复计算贡献。时间复杂度 $\operatorname{O}(\sum K_{i}N^2)$。 （更多…）