2019-2020 ACM-ICPC Brazil Subregional Programming Contest

From EOJ Wiki
Jump to: navigation, search

Problem A

Solved by Xiejiadong. 01:05 (+)

题意:要从 $(0,0)$ 走到 $(n,m)$ ,沿路有一些监视器,每个监视器有一定的监视范围,求能不能逃脱监控,走到终点。

题解:显然,监控能够阻断道路,当且仅当地图的左上边界和右下边界通过监视器联通了起来。

于是通过 $O(n^2)$ 枚举建边,直接 BFS 就好了。

Problem B

Solved by Xiejiadong. 00:10 (+)

温暖的签到。

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 00:38 (+)

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 04:48 (+3)

题意:通过给 $n$ 条线段扩充成矩形,使得这 $n$ 个矩形覆盖区域的并与给定矩阵的交的面积能够达到给定矩形的 $p\%$ 。

题解:二分答案确定扩充的边长,考虑验证答案。

验证答案的时候,显然是利用扫描线法对扩充以后的 $n$ 个矩形覆盖区域维护,然后求在给定矩形区域内的面积即可。

利用线段树维护最小值的数量就能计算。

Problem G

Solved by Xiejiadong && Kilo_5723. 02:27 (+)

题意:工作分配问题,使得分配以后价值的乘积最大。

题解:乘积最大可以通过取 log 转换为和的形式。

考虑网络流建图。对于每一行和每一列分别建立一个点,在行和列所表示的点之间连流量为 $1$ ,价值为 $-log(a_{i,j})$ 的边。

在源点向行连边,列向汇点连边,均为流量 $1$ 、价值 $0$ 。

然后跑最小费用最大流即可得到最大的价值。

需要输出方案,所以在参与网络中把所有流量为 $0$ 的边取出来就是答案。

Problem H

Solved by Kilo_5723. 00:05 (+)

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 02:37 (+)

Problem K

Solved by Weaver_zhu. 04:01 (+)

Problem L

Solved by Kilo_5723. 00:49 (+)

Problem M

Solved by Xiejiadong. 00:23 (+)

题意:每个人可以吃连续的一些东西,每个人每秒吃的东西有上限,求最小的时间吃完所有东西。

题解:二分答案。然后贪心地给每个人尽量多的靠前的东西吃。判断能不能吃完即可。