12.1 模拟赛

A 小鸣的疑惑

曾经做过。

考虑归纳证明。假设我们已经得到了前 $n-1$ 个数得到的答案是 $A_1 - A_2$ 。现在考虑 $n$ 个数的情况。

如果合并的两个数不包含 $A_1,A_2$ ，那么就得到了一个子问题，答案是 $A_1 - A_2$ 。

如果合并的两个数包含 $A_1,A_2$ ，有两种情况，要么一步变成了 $A_1 - A_2 , A_3$ ，要么变成了 $A_1,A_2 - A_3$ 。出现这两种情况的概率是一样的，于是这两种情况的期望值就是 $\frac 1 2(A_1 - A_2 - A_3 + A_1 - A_2 + A_3)$ ，也是 $A_1 - A_2$ 。

因此最后答案就是 $A_1 - A_2$ 。

B 红蔷薇白玫瑰

这相当于是把某个 01 串拿到树上匹配的问题，我们考虑 Hash ，给每个点按照二叉树的二进制重新标号，也就是 $3$ 的两个儿子分别是 $6,7$ 。然后考虑如果 $u$ 进行匹配后，就会变成 $2^mu + x$ ，其中 $x$ 是读入的长度为 $m$ 的 01 串。直接堆每个位置算出它的 Hash 并且匹配回去即可。

复杂度，如果用 map 是 $O(n\log n)$ 的。可以用 unordered_map 优化但是没必要。

然后场上某个模数整反了。。就炸了。

C 山遥路远

我们考虑如何算出 $(u \to v)$ 的合法最短路。由于边权是非负的，可以用类 dijkstra 求解。

具体来说，考虑 $(u \to v,w)$ 在堆里面，表示 $u \to v$ 有合法路径长为 $w$ 。然后更新有几种：

• 可以通过往 $u \to v$ 后面拼一条路径更新。也就是 $u \to v, v \to k$ 两个合法路径合并，仍然是合法的路径，或者可以往前面拼一个路径更新，也就是 $k \to u , u \to v$ 这样。这两种分别只需要枚举一下 $k$ 更新即可。这是一个类似 Floyd 的转移方法，由于 dijkstra 取出的一定是当前的最短路，所以这样转移是对的。
• 可以通过 $p \to u \to v \to q$ 转移，其中 $p \to u$ 有一个 ( 的边，$v \to q$ 有一个 ) 的边。也就是往当前的合法括号序两侧加上一对括号。转移就是枚举一下这两个边即可。

场上就写的这个东西。考虑复杂度分析。点的个数是 $O(n^2)$ 的，但是边的个数很多。边的个数大概是 $O(m^2 + n^3)$ 的，第一种情况对于每个路径都有 $O(n)$ 个转移，第二种情况，考虑每一对 ( ， ) 边，不难发现它们一定能且仅能被转移一次，所以复杂度是 $O((m^2 +n^3) \log (m^2 + n^3))$ 的。

看起来很慢，但是会发现实际上 $m^2$ 有 $\frac 1 4$ 的常数。所以实际上可以跑过 $80$ 分。

考虑如何去优化这个东西。

首先，第二种情况中同时枚举 $p,q$ 非常不优秀。可以发现这个东西可以类似很多状压题的优化。也就是设一个 $g(u,v)$ 表示 $u \to v$ 的最短路径，满足整个路径开头是左括号，且匹配完后剩下的一定是开头的左括号。

发现转移就稍微有所改变，对于每个 $(u\to v,w)$ 我们枚举一个 $p \to u$ 满足这条边上是一个左括号，然后转移到 $g(p,v)$ ，并且把 $g$ 同样加入优先队列中。如果队首是 $g$ ，再用 $g(u,v)$ 转移到 $(u\to q)$ 。两次转移都只需要枚举一次出边即可。于是边的个数被优化到了 $O(nm + n^3)$ ，因为对于一个 $u$ 枚举所有的 $v$ 都需要考虑一次所有的 $u$ 的入边。

但是这样的复杂度仍然是 $O((nm + n^3)\log(nm + n^3))$ ，还是不太能过。

考虑一个经典的 dijkstra 优化。可以通过斐波那契堆来优化。斐波那契堆是一种支持 $O(1)$ 进行插入，查最大值，更改某个东西的值，合并，且 $O(\log n)$ 删除最大值的数据结构。

如果我们提前把 $O(n^2)$ 个点给插入好，然后每次 push 操作都直接用修改来实现。不难发现这样队列里的元素不会超过开始的点数 ，于是删除最大值只需要进行 $O(n^2)$ 次。换句话说，如果图的点数是 $O(n)$ 边数 $O(m)$ ，那么斐波那契堆来优化 dijkstra 后复杂度就是 $O(n\log n + m)$ 。

于是最后复杂度就变成了 $O(nm + n^3 + n^2\log(n^2))$ 。可以通过。

考虑一种更阳间的优化方法（虽然貌似有点卡常）。我们可以做值域分块。这样就可以做到每次修改最小值 $O(1)$ ，删除一个值 $O(\sqrt{n^2})$ 。

这样做复杂度是 $O(nm + n^3)$ ，常数很大。 萃老师卡了很久才整过去（1978ms）。

联赛组 T4 可持久化仙人掌树

这个题类似于之前某个 2E 。感觉很优秀的一个题。

考虑 $a \oplus b \leq a + b$ ，所以我们有一个必要条件 $A_x + A_y \geq f_x - f_y$ ，化简一下就是 $f_x - f_y - A_x \leq A_y$ 。感觉上这个东西能取到的位置就很少。我们对每个 $x$ 考虑成立的 $y$ 。

首先，如果 $x$ 的子树大小大于 $3$ ，那么有所有的合法的 $y$ 一定在一条链上。

考虑反证。假设有两个点 $u,v$ 都满足了这个条件。我们知道 $f_x - f_y - A_x$ 本质上就是 $x$ 子树中除开 $y$ 子树中的点再除开 $A_x$ 后的东西。由于子树大小大于 $3$ ，考虑 $v$ 满足条件， $A_u < f_x - f_v - A_x \leq A_v$ ，再考虑 $u$ 满足条件，又可以推出 $A_v < A_u$ ，互相矛盾。

因此，子树大小大于 $3$ 的子树中这个必要条件成立的 $y$ 一定处于一条链上。

考虑一条链上的所有 $y$ 。我们设当前考虑的祖先是 $x$ ，向下依次有三个点 $y_1,y_2,y_3$ 。我们有

$f_{y_2} - A_{y_2} \ge f_{y_3}$

于是就可以推出：

$A_{y_3} \geq f_x - f_{y_3} - A_{x} \geq A_{y_2} + f_x - A_x - f_{y_2} \geq A_{y_2} + A_{y_1}$

所以可以发现，对于一个确定的 $x$ ，满足这个必要条件的 $y$ 仅有 $O(\log n)$ 个。子树大小小于等于 $3$ 时这个条件显然成立。

这就说明了，这个题的答案是 $O(n\log n)$ 的。

但是如果确定 $x$ ，不太好枚举 $y$ 。可以考虑枚举一下 $y$ ，因为这样后可能满足必要条件的 $x$ 一定是 $y$ 到根路径上的一段前缀。因为我们相当于固定了 $A_y + f_y$ ，而 $f_x - A_x$ 显然在不断变大。

然后每次就 check 一下原条件是否满足即可。复杂度 $O(n\log n)$ 。