HCW 19 Team Round

From EOJ Wiki
Revision as of 08:11, 22 September 2019 by Xiejiadong (talk | contribs) (→‎Problem G)
Jump to navigation Jump to search

Problem A

Solved by Kilo_5723. 00:20 (+)

Problem B

Solved by Kilo_5723. 01:59 (+2)

Problem C

Solved by Kilo_5723. 01:37 (+)

Problem D

Solved by Kilo_5723. 00:36 (+)

Problem E

Solved by Xiejiadong. 04:02 (+)

题意:需要完成 $n$ 系列攻击,每次攻击以后速度会减慢成 $b_i$ ,求最少的时间完成攻击。

题解:因为 $b_n=0$ ,完成攻击显然的策略是以最快的速度完成第 $n$ 次攻击,这样接下来的攻击都不会再花费时间。

我们用 $f[i]$ 表示完成第 $i$ 次攻击所需要花费的最少时间,于是可以很方便的得到 dp 方程 $f[i]=min_{1\le j\le i-1}f[j]+b[j]*a[i]$ 。

我们可以把 $k=b[j],b=f[j]$ 这样相当于每一次都产生一条新的一次函数,询问某一个 $x$ 处的最小值。

可以直接用李超树维护这部分的结果。

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 02:54 (+)

题意:询问第一棵无根树的最大深度是否大于第二棵无根树的最小深度。

题解:最大深度,可以通过先从任意节点作为根节点 dfs 一遍找到一个深度最深的点,然后以这个点为根在进行 dfs 找到最大深度得到。

最小深度,我们可以通过维护任意节点的有根数下每一个节点的最大深度和次大深度,再 dfs 一遍,将父亲方向的信息更新给孩子得到每一个节点作为根节点的时候的深度,取最小的作比较即可。

Problem H

Solved by Xiejiadong. 00:59 (+)

Problem I

Solved by Kilo_5723. 02:48 (+)

Problem J

Solved by Xiejiadong. 00:28 (+)

Problem K

Solved by Kilo_5723. 03:50 (+1)

Problem L

Solved by Kilo_5723. 02:27 (+1)