2018 Multi-University, HDU Day 10

Problem C

Unsolved. (-32)

做自闭了。

Problem E

Solved by zerol. 01:18 (+2)

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

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

另解：线段树合并 / set 启发式合并。

Problem G

Solved by OEIS. 00:42 (+)

Problem H

Solved by ultmaster. 00:08 (+)

题意：求 $2^n$。

题解：高精度。或

printf("%.0f\n", pow(2, n));

Problem I

Solved by kblack. 00:51 (+)

Problem J

Solved by zerol. 02:19 (+4)

题意：对于两个点集 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 by kblack. 01:21 (+)