Difference between revisions of "2020 China Collegiate Programming Contest Qinhuangdao Site"
Jump to navigation
Jump to search
| (2 intermediate revisions by the same user not shown) | |||
| Line 24: | Line 24: | ||
Solved by yanghong. 00:38 (+) | Solved by yanghong. 00:38 (+) | ||
| + | 先考虑一个小组： 如果向一个小组中加入一个有至少一个朋友在小组中的人， 则小组的贡献不会减小； 反过来把一个小组拆成两部分贡献一定减小。 那么把关系看成一张图， 每个小组的最优情况肯定是取最大联通块。 | ||
| + | |||
| + | 那么用并查集计算每个连通块的贡献，把贡献为正的加入答案。 | ||
== Problem G == | == Problem G == | ||
Solved by yanghong. 00:23 (+3) | Solved by yanghong. 00:23 (+3) | ||
| + | |||
| + | 枚举 $\lfloor ^k\sqrt{x} \rfloor$ 的值即可。 注意溢出的情况 | ||
== Problem H == | == Problem H == | ||
| Line 47: | Line 52: | ||
Solved by yanghong. 01:36 (+3) | 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 == | == Problem L == | ||
Unsolved. | Unsolved. | ||
Latest revision as of 12:21, 3 November 2020
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.