Difference between revisions of "HCW 19 Team Round"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== 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...")
 
Line 18: Line 18:
  
 
Solved by Xiejiadong. 04:02 (+)
 
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 ==
 
== Problem F ==

Revision as of 08:09, 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.

Problem G

Solved by Xiejiadong. 02:54 (+)

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)