2020 牛客暑期多校训练营第 5 场

rank solved A B C D E F G H I J K
27 10 Ø O O O O O Ø Ø O . Ø

B

Solved by ytriayggg and XLor (01:57:13, +1).

由于每次操作后,图联通,因此如果把图补成完全图,那么每条边的权值都固定,因此问题转化为异或最小生成树。

C

Solved by ytriayggg (04:05:06).

二维生成函数。

D

Solved by miaojie (02:16:38, +1).

枚举原排列的循环移位,对每个求 LIS。

E

Solved by XLor (01:01:54, +1).

答案是环长的 $lcm$,且答案远小于取模的模数。

F

Solved by miaojie (00:11:39).

签到。

G

UpSolved by XLor.

问题是要求 $\text{mex}$,考虑二分答案后,使用二分图匹配判断是否流满。

但是,我们不能暴力的去建出二分图,对建图进行优化。

首先,我们考虑对每种颜色建出虚树,那么一条边就对应原树的一条垂直树链,这条链上任取一个点都会产生颜色树乘子树关键点数的值,因此需要将这条路径的所有点连向某个值。

然后,这里给一个 $O(n)$ 个点,$O(n\log n)$ 条边的建图方式。第一部分,考虑对树轻重链剖分,每个点拆分为本来的点,连向它在重链上的副本,并将这个点连向重儿子在重链上对应的点,第二部分,对剖分后的 dfs 序使用线段树优化建图。因此,每条垂直树链就可以分为一系列重链(到链顶端),加上一段 dfs 序连续区间。

第一部分的建图,如下所示。可以注意到,若一个点往外有流量时,这个点所属重链的所有祖先结点也可以通过这条流量。

image.png

因为,一条垂直树链至多有 $\log n$ 条重链,因此这部分至多会创建 $O(\log n)$ 条边,而线段树一次区间询问至多由 $O(\log n)$ 个区间组成,因此总边数为 $O(n\log n)$ 的。

将图建出来后,二分答案时,不需要每次重新跑一边最大流,如果 $mid$ 成立,那么可以继续在它的残量网络上继续跑,否则撤销本次操作。

H

UpSolved by XLor (-9).

类似于 $\gcd$ 的结论,每个左端点开始至多只有 $30$ 个不同的值,抠出每种值的区间,不妨记为 $(l_1,r_1),(l_2,r_2),\dots$,询问区间包含任意一个答案 $+1$,如果包含了两个,例如 $(l_1,r_2)$ 答案需要 $-1$,以此类推,整理出贡献的点,直接二维数点即可。

I

Solved by miaojie (00:31:52, +1).

K

UpSolved by XLor (-1).

首先,预处理出两个串分别是什么,考虑 $dp(i,j)$ 表示用了第一个串的前 $i$ 行,第二个串的前 $j$ 行,转移有 $4$ 种,正好匹配,选择两个后缀使用 $if-else$,选择一个后缀使用 $if$。

朴素的 DP 是 $O(n^4)$ 的,但是我们实际上并不需要枚举最后一个的情况,只需要开 $4$ 种状态分别记录即可 $O(1)$ 转移。

注意,初始化的细节和 $if-else$ 的两个串长度不一定相同。