MOCK NOIP 20221020 日志

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

一句话题解

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$ 处取最小值。

引理的证明：将 $n-a$ 记作 $c$。原式 $=\frac{1}{b!}(a^{\underline{b}}+c^{\underline{b}})$。考虑当 $a’=a-1,c’=c+1$ 时该式如何变化。有 $$\begin{aligned} &(a^{\underline{b}}+c^{\underline{b}})-(a’^{\underline{b}}+c’^{\underline{b}})\\ =&a(a-1)\cdots(a-b+1)-(a-1)(a-2)\cdots(a-b)+c(c-1)\cdots(c-b+1)-(c+1)c\cdots(c-b+2)\\ =&(a-1)(a-2)\cdots(a-b+1)[a-(a-b)]+c(c-1)\cdots(c-b+2)[(c+1)-(c-b+1)]\\ =&b\left((a-1)^{\underline{b-1}}-c^{\underline{b-1}}\right) \end{aligned}$$

该式在 $a>c$ 时恒非负，反之恒非正。故取到 $a=c$ 或者 $a=c-1$ 时最优。$\blacksquare$

我们很容易将引理推广到不止一个变元的情况。由于 $\sum_{p=1}^{2n}\cnt(p)=n(n+1)$，故上式结果最小，各元素出现次数必尽量均摊。得到有 $n$ 个 $\cnt(p)=\frac{n}{2}$，另 $n$ 个 $\cnt(p)=\frac{n+2}{2}$。则 $$\left(\sum_{p=1}^{2n}\binom{\cnt(p)}{2}\right)_{\min}=n\left(\binom{n/2}{2}+\binom{n/2+1}{2}\right)=\frac{n^3}{4}$$

假设所有交集大小均不足 $n/2$。则其大小之和最多为 $(\frac{n}{2}-1)\binom{n+1}{2}=\frac{n^3-n^2-2n}{4}$。我们将空缺的部分用全等的集合填满，则至少有 $\frac{n^2+2n}{4}/(\frac{n}{2}+1)=\frac{n}{2}$ 个交集大小满足题意。$\square$

于是乎每一次随机都将有 $\frac{n/2}{n(n+1)/2}=\frac{1}{n+1}$ 的概率成功。故将在期望 $n+1$ 次随机后成功，复杂度得到保证。

C – 构型

我当然知道这是 DP，同时状态是由每一段 $0$ 和 $1$，以及由 $2$ 构成的间隔划分的。不过场上没弄明白到底应该怎么不遗漏地计算一个方案的代价。

实际上，由于本题的操作之后是“取出元素后插入任意位置”，我们并不关心该元素去往何处。故而一旦我们取出“不应该存在于本段”中的元素，只要能够插入任意合法位置，它的代价便是恒定的（取出的元素个数）。

设 $f(i,j,0/1/2)$ 表示“考虑第 $i$ 个元素恰划分为第 $j$ 段的末尾（最终序列中该位置为 $2$），且前序段落中只有含 $0/1$ 或二者兼有的段落”的最小代价。朴素的转移需要枚举段落开头位置 $k+1$，不过其代价只和 $i,k$ 线性相关，我们可以用前缀和优化。时间复杂度 $\bigO(n^2)$。

D – 散乱

你发现若设 DP 状态，则转移他一定需要考虑连通块形态和最大深度一类信息，复杂度是绝对不可接受的。 所以你要往贪心考虑。            ——mzx学长

若一个矿工处在节点 $x$（深度 $d_1$），他挖掘的所有宝藏的最大深度为 $d_2$，且 $d_2+1<d_1+k$，则我们把该矿工放到 $x$ 的父亲，效果是等价的。

矿工越少越好。故而我们检查一个节点是否需要指派新的矿工，是在该节点的 $k$ 级祖先处进行的。

假设我们从子树遍历到节点 $x$，存在若干矿工现在能挖掘的最大深度为 $\text{mxd}$，当前统共剩余 $r$ 个可挖掘的宝藏。则我们贪心地使其挖掘 $x$ 子树内深度为 $\text{mxd},\text{mxd}-1$ 的所有剩余宝藏，若他们的额度仍有剩余，则由上文提到的等价关系可知，把他们转移到 $x$ 的父亲，就可以挖掘 $\text{mxd}-2,\text{mxd}-3$ 的宝藏，以此类推。若某个宝藏与 $x$ 的深度差恰为 $k$ 且额度不足以挖掘，则我们被迫添置新矿工。

时间复杂度 $\bigO(nk)$。