2018 Multi-University Training Contest 10

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Unsolved.

Problem C

Unsolved.

Problem E

Solved.

题意:对于树上的每个点,求 lca 恰好是这个点的点对中点权 gcd 的最大值。

题解:对于树上每个点,求出一个 bitset 记录了子树中所有数的因数并,然后依次合并儿子以及自己本身,合并前取位与检查最高位的 1。(bitset._Find_first() 可以求出第一个 1 的位置。)

另解:线段树合并 / set 启发式合并。枚举 gcd 在更新在虚树上结点的答案(相邻两项 LCA)(由 CSL 友情提供)。

Problem G

Solved by OEIS.

Problem H

Solved.

Problem I

Solved.

Problem J

Solved.

题意:对于两个点集 S_1, S_2,求 $\max\{dist(x,y)+w_x+w_y | x\in S_1,y\in S_2\}$,距离为曼哈顿距离,最多五维。

题解:K-D Tree 暴力,要多加一些剪枝才能过。

正解:枚举每一维绝对值的正负,记录 $2^5$ 种可能的最大值,将另一个点集带入,取最大值即可。

Problem L

Solved.

题意:最多 $K$ 个人看电影,每个电影能拿钱,连续看相同类型的电影要罚钱,求最大获益。

题解:两排点表示在看那种电影,对于每个电影在两边对应时间连边,再连上发钱切换的边,费用流一下就好了。