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$ 。我们有

于是就可以推出:

所以可以发现,对于一个确定的 $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)$ 。

文章作者: yijan
文章链接: https://yijan.co/2020/12/28/121-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog