Difference between revisions of "2020 China Collegiate Programming Contest Qinhuangdao Site"
Jump to navigation
Jump to search
(Created page with "== Problem A == Unsolved. == Problem B == Solved by yanghong. 04:34 (+) == Problem C == Solved by bingoier. 00:35 (+) 质因数分解后发现答案为每一个质数的...") |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Problem A == | == Problem A == | ||
| − | + | Solved by . 00:18 (+1) | |
== Problem B == | == Problem B == | ||
| − | + | Unsolved. | |
== Problem C == | == Problem C == | ||
| − | + | Unsolved. | |
| − | |||
| − | |||
== Problem D == | == Problem D == | ||
| Line 19: | Line 17: | ||
== Problem E == | == Problem E == | ||
| − | Solved by | + | Solved by . 02:09 (+2) |
| − | |||
== Problem F == | == Problem F == | ||
| − | Solved by yanghong. | + | Solved by yanghong. 00:38 (+) |
| + | |||
| + | 先考虑一个小组： 如果向一个小组中加入一个有至少一个朋友在小组中的人， 则小组的贡献不会减小； 反过来把一个小组拆成两部分贡献一定减小。 那么把关系看成一张图， 每个小组的最优情况肯定是取最大联通块。 | ||
| + | |||
| + | 那么用并查集计算每个连通块的贡献，把贡献为正的加入答案。 | ||
== Problem G == | == Problem G == | ||
| − | + | Solved by yanghong. 00:23 (+3) | |
| + | |||
| + | 枚举 $\lfloor ^k\sqrt{x} \rfloor$ 的值即可。 注意溢出的情况 | ||
== Problem H == | == Problem H == | ||
| − | |||
| − | + | Unsolved. | |
| − | |||
| − | |||
| − | |||
== Problem I == | == Problem I == | ||
| Line 47: | Line 46: | ||
== Problem J == | == 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. | ||
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.