Difference between revisions of "HCW 19 Team Round"

From EOJ Wiki
Jump to navigation Jump to search
Line 31: Line 31:
 
== Problem F ==
 
== Problem F ==
  
Unsolved. (-6)
+
Unsolved. (-7)
  
 
== Problem G ==
 
== Problem G ==

Revision as of 08:19, 22 September 2019

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. (-7)

Problem G

Solved by Xiejiadong. 02:54 (+)

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

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

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

Problem H

Solved by Xiejiadong. 00:59 (+)

题意:顺次连接 $n$ 个块,使得连接起来的地方数字相同,给出任意方案。

题解:直接暴力枚举每一块的位置和摆放的方向,从前往后枚举,直接判断是否可行,不可行的直接剪枝。

Problem I

Solved by Kilo_5723. 02:48 (+)

Problem J

Solved by Xiejiadong. 00:28 (+)

题意:允许交换一个数的任意两位,求这些数中没有前导 $0$ ,小于原数,但最大的数。

题解:暴力交换出所有的情况,直接排序,找到答案。

Problem K

Solved by Kilo_5723. 03:50 (+1)

Problem L

Solved by Kilo_5723. 02:27 (+1)