Difference between revisions of "2020 China Collegiate Programming Contest Qinhuangdao Site"

From EOJ Wiki
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.