2020 China Collegiate Programming Contest Qinhuangdao Site

Problem A

Solved by . 00:18 (+1)

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by . 02:09 (+2)

Problem F

Solved by yanghong. 00:38 (+)

先考虑一个小组： 如果向一个小组中加入一个有至少一个朋友在小组中的人， 则小组的贡献不会减小； 反过来把一个小组拆成两部分贡献一定减小。 那么把关系看成一张图， 每个小组的最优情况肯定是取最大联通块。

那么用并查集计算每个连通块的贡献，把贡献为正的加入答案。

Problem G

Solved by yanghong. 00:23 (+3)

枚举 $\lfloor ^k\sqrt{x} \rfloor$ 的值即可。 注意溢出的情况

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by yanghong. 01:36 (+3)

到达每个叶子节点即可。

考虑先从根到叶子 a， 再从 a 到叶子 b 。 消耗时间 : $dep_a + dep_a - dep_{LCA(a, b)} + dep_b - dep_{LCA(a, b)}= dep_a + (dep_a - 2 \times dep_{LCA(a, b)}) + dep_b$

$dep_a, dep_b$ 都是一定会计入答案的， 那么想办法最小化 $(dep_a - 2 \times dep_{LCA(a, b})$ 即可。

Problem L

Unsolved.