2020 China Collegiate Programming Contest Qinhuangdao Site

From EOJ Wiki
Revision as of 12:21, 3 November 2020 by Once (talk | contribs) (→‎Problem K)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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.