10.21 模拟赛

T1 食堂计划

最短路图是一张拓扑图,并且只要再这个图上走出的路径就一定是最短路。

于是考虑一个 $dp$ :设 $dp[u][v]$ 表示当前一个路径结尾在 $u$ 另一个在 $v$ 的方案数量。但是直接转移会出现重点。

我们考虑转移的时候限制如果从 $(u,v) \to (x,v)$ ,必须要有 $dis_u < dis_v \or (dis_u = dis_v \and i < j)$ 才行。唯一可能走出重点的情况就是其中一个点走到了一个根到 $v$ 路径上的点,但是如果这种情况真的出现了,那么之前在 $(x,u)$ 的时候就已经该由 $u$ 去转移,就不会通过这个状态转移到 $(u,v)$ ,也就是说 $x$ 并不在根到 $v$ 路径上。

但是有一种非常套路的解法,考虑设 $dp[u]$ 表示所有到达 $u$ 的路径带上容斥系数的和。具体地说,对于两条到达 $u$ 的路径,如果我们钦定了 $k$ 个点这两个人走到了一起,那么这对路径的系数就是 $(-1)^k$ ,其他位置可以到一起也可以不。

转移就是枚举一个之前的点,然后考虑多钦定一个点,中间随意选择两条路径就好,只需要对于任意两点处理出这两点间的路径条数。

两个做法都写了代码。

T2 笛卡尔树

考虑对于一个长度为 $n$ 的排列,我们钦定最大值位置在 $j$ 后,就确定了其左右两个区间的长度。于是把权值拆开,考虑左右区间长度分别为 $a,b$ ,那么我们考虑怎么合并成对整个区间的贡献。

首先,子树内部的贡献。由于贡献的形式是差值,所以不存在位置带来的影响,所以子树自己的贡献就是

然后考虑如果 $a,b > 0$ 我们需要计算出两个儿子自己的贡献。

考虑所有长度一定的排列中最大值出现位置的和。我们知道

于是分别考虑所有可能的左右排列的贡献。左边的贡献显然是 $-B_a b!$ 但是右边,由于位置有一个便宜量 $j$ ,所以实际上是

但是分配编号还有一个组合数 $\binom{a+b}{a}$ ,于是总的来说,贡献是

然后就可以愉快地 $O(n^2)$ 辣!

假装 $i$ 为我们要算的长度,我们把 $a = j-1 , b = i - j$ 代入 $a,b$ 化下式子

设 $H_i = \frac{A_i}{i!}$ 即可递推。

T3 序列翻转

不是很想改,强行拼题

T4 路径大小差

我们设 $F(l,r)$ 表示边权在 $[l,r]$ 内的路径条数,而设 $G(l,r)$ 表示最小权为 $l$ 最大权为 $r$ 的路径条数的话,可以发现这两个之间是可以容斥得到的。

我们把 $G(l,r)$ 放在二维平面的 $(l,r)$ 上,然后 $F(l,r)$ 就是一块三角形的总和,然后可以容斥一下,发现:

然后就只需要统计 $F$ 了!

首先可以对于 $k,k-1,k-2$ 长度的所有区间分别求,这个东西可以直接拿 LCT 维护,复杂度 $O(n\log n)$ 。

离线下来后可以线段树分治,可撤销并查集即可。复杂度 $O(n\log^2 n)$ 。

由点分 + 二维数点的做法,无限期咕咕咕,可以看翠老师提交。

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