Difference between revisions of "2019 Multi-University,HDU Day 3"

From EOJ Wiki
Jump to navigation Jump to search
Line 34: Line 34:
  
 
Solved by Xiejiadong. 00:41:23 (+1)
 
Solved by Xiejiadong. 00:41:23 (+1)
 +
 +
题意:求 $1\cdots (k-1)$ 里面需要把多少个数变成 $0$ ,可以使得 $\sum_{i=1}^k a_k\le m$ 。
 +
 +
题解:问题转变成,在 $1\cdots k$ 中,第 $k$ 个数必须取,也就是在 $1\cdots (k-1)$ 中选取尽量多的数,使得和 $\le (m-a_k)$ 。
 +
 +
权值线段树维护一下,然后直接在线段树上二分就是了。
  
 
== Problem H ==
 
== Problem H ==

Revision as of 08:57, 29 July 2019

Problem A

Unsolved.

Problem B

Solved by Xiejiadong && Wwaver_zhu. 01:59:02 (+1)

题意:给出一个 DAG ,每次询问两个点,求有多少方案通过删除一个点,使得其中一个点无法到达所有他所在的联通块出度为 $0$ 的点。

题解:把所有出度为 $0$ 的点连向一个超级汇点,显然,询问就变成了任意一个点无法到达超级汇点的方案。

以超级汇点作为起点,建反图,那么,可以删除的点就一定是从超级汇点出发到询问点的必经点。

在支配树上,方案树就是询问的两个点的祖先的并,求个 lca 就好了。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Solved by Kilo_5723 && Weaver_zhu. 00:33:20 (+1)

Problem G

Solved by Xiejiadong. 00:41:23 (+1)

题意:求 $1\cdots (k-1)$ 里面需要把多少个数变成 $0$ ,可以使得 $\sum_{i=1}^k a_k\le m$ 。

题解:问题转变成,在 $1\cdots k$ 中,第 $k$ 个数必须取,也就是在 $1\cdots (k-1)$ 中选取尽量多的数,使得和 $\le (m-a_k)$ 。

权值线段树维护一下,然后直接在线段树上二分就是了。

Problem H

Unsolved.

Problem I

Solved by Xiejiadong && Wwaver_zhu. 04:33:20 (+4)

Problem J

Unsolved.

Problem K

Unsolved.