2019-2020 ACM-ICPC Brazil Subregional Programming Contest

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

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

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