12.1 模拟赛

A 小鸣的疑惑

曾经做过。

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

如果合并的两个数不包含 A1,A2A_1,A_2 ,那么就得到了一个子问题,答案是 A1A2A_1 - A_2

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

因此最后答案就是 A1A2A_1 - A_2

B 红蔷薇白玫瑰

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

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

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

C 山遥路远

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

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

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

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

看起来很慢,但是会发现实际上 m2m^214\frac 1 4 的常数。所以实际上可以跑过 8080 分。

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

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

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

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

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

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

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

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

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

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

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

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

首先,如果 xx 的子树大小大于 33 ,那么有所有的合法的 yy 一定在一条链上。

考虑反证。假设有两个点 u,vu,v 都满足了这个条件。我们知道 fxfyAxf_x - f_y - A_x 本质上就是 xx 子树中除开 yy 子树中的点再除开 AxA_x 后的东西。由于子树大小大于 33 ,考虑 vv 满足条件, Au<fxfvAxAvA_u < f_x - f_v - A_x \leq A_v ,再考虑 uu 满足条件,又可以推出 Av<AuA_v < A_u ,互相矛盾。

因此,子树大小大于 33 的子树中这个必要条件成立的 yy 一定处于一条链上。

考虑一条链上的所有 yy 。我们设当前考虑的祖先是 xx ,向下依次有三个点 y1,y2,y3y_1,y_2,y_3 。我们有

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

于是就可以推出:

Ay3fxfy3AxAy2+fxAxfy2Ay2+Ay1A_{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}

所以可以发现,对于一个确定的 xx ,满足这个必要条件的 yy 仅有 O(logn)O(\log n) 个。子树大小小于等于 33 时这个条件显然成立。

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

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

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

\