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

rank solved A B C D E F G H I J
102 7 O Ø . . Ø O . Ø Ø O

A

Solved by XLor (01:39:24, +2).

注意到字符集只有 $2$。

考虑重载两个后缀的比较函数。显然每个后缀必然以 aa...abbb...ba 开头,如果开头重复的字符数量不同,那么必然有一个出现了 $0$ 可以直接比较;否则,对两个的剩余后缀进行比较,此时两个后缀的同构串就是原串的同构串,因此只需要对原串的同构串后缀排序即可。

B

UpSolved by ytriayggg and XLor.

定义一棵无穷的树,点 $x$ 的父亲为 $x \over \text{mindivsor}(x)$。

给定 $1!, 2!, \dots, n!$ 这些关键点,求一个点使得它关键点的带权距离和最小。

注意到目标点应该在关键点的虚树上,建出这棵虚树后,求一下带权重心。

可以观察到根 $1$ 到每个点的路径上途径乘的质数是不断减小的,树上两个点的 LCA 就是两个点很多公共的最大质因子,从某个位置开始质因子出现不同导致结点的分叉。

对 $1!, 2!, \dots, n!$ 这些关键点建立虚树,需要知道 $i!$ 和 $(i-1)!$ 的 LCA(深度),那么必然是从 $i$ 的最大质因子开始变化。维护 $(i-1)!$ 每个质数位置的个数,深度就是 $i$ 的最大质因子到最大值这个区间内的个数和,类似地构建出虚树。

构建出虚树后,求带权重心,可以先计算根结点的答案然后贪心地往下走。

E

UpSolved by miaojie.

F

Solved by XLor (00:23:55, +2).

比较一下长度为 $n+m-\gcd(n,m)$ 的无穷串即可。

H

UpSolved by XLor (-24).

注意到所有边的容量相同,因此在求最大流时,每轮增广必定就是切除掉一些边。

第一次,就是原图的最短路,切除这个最短路后,依此类推。

询问,设置每条边容量为 $u \over v$,跑出流量为 $1$ 的最小费用,那么只需要知道需要增广几次,最后一次增广时,多用了多少流量,容易计算。

注意:计算答案时可能爆整数范围,建议小心谨慎。

I

UpSolved by miaojie (-1).

一般图匹配,带花树算法。

J

Solved by ytriayggg (00:20:55).

OEIS。