ICPC 2019-2020 North-Western Russia Regional Contest

From EOJ Wiki
Jump to: navigation, search

Problem A

Solved by Xiejiadong. 00:15 (+)

温暖的模拟题。

Problem B

Solved by Kilo_5723. 02:23 (+)

Problem C

Solved by Kilo_5723. 03:32 (+2)

Problem D

Unsolved.

Problem E

Solved by Xiejiadong. 02:39 (+2)

题意:在树上求一个点,使得其到所有特殊点距离相等。

题解:对于所有的特殊点按照顺序,使得相邻的两个距离都相等即可。

对于能使两个点距离相等的,首先求两个点距离的中点(长度为偶数,没有中点,一定无解)。

而所有满足要求的点,一定是中点连出去的所有链,去掉两个点所在的那条链,相当于是一个子树去掉一部分子子树。

按照 dfs 标号以后,子树的问题就可以变成区间问题,用线段树维护标记,每次操作修改一些标记。

最后查询是否存在满足要求的标记就好了。

链的中点,可以通过倍增 lca 来完成。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Solved by Weaver_zhu. 01:07 (+)

Problem I

Solved by Kilo_5723. 01:46 (+)

Problem J

Solved by Weaver_zhu. 02:12 (+)

Problem K

Upsolved by Weaver_zhu. (-2)

Problem L

Unsolved.

Problem M

Solved by Kilo_5723. 01:11 (+3)