2017 Benelux Algorithm Programming Contest (BAPC 17)

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by kblack. 00:14 (+)

签到。

Problem B

Unsolved.

Problem C

Solved by zerol. 00:25 (+)

Problem D

Solved by ultmaster. 01:46 (+)

题意:在每个点不能走最短路的方向,求从起点到终点的路径。

题解:反向跑最短路,删(标记)不能走的边,然后正向走一遍 BFS 即可。

Problem E

Solved by ultmaster. 03:36 (+)

题意:有 $R$ 个红点,$B$ 个蓝点,要求选 $N$ 个点,使得红点和蓝点的最短距离最大。

题解:二分答案,然后在小于答案的之间连边,最后求最大独立集即可 check。注意答案可行的条件是最大独立集大于等于 $N$。

Problem F

Solved by ultmaster. 00:17 (+)

签到。

Problem G

Upsolved by ultmaster.

题意:有很多交易记录,现在任意两人之间都可以交易。求使得 balance 为 0 的最小交易次数。

题解:先求好每一个人的 balance,记为 $a_1,a_2,\ldots,a_n$ 且 $\sum_{i=1}^n a_i = 0$。问题转化为将整个集合拆分为若干个和为 $0$ 的子集,为最多有多少个。然后可以进一步转换为求最长的和为 $0$ 的子集链 $S_1 \subset S_2 \subset \cdots All$。注意求这个东西并不需要枚举所有和为 0 的子集,也不需要什么高维前缀和。我们需要利用那些「没用」的状态。即和不为 $0$ 的子集的状态。在考虑一个子集的时候,只需要尝试拿掉子集中的每一个元素,然后答案便是拿掉元素后产生的新子集的答案的最大值;如果本身子集和为 $0$,那么就给答案加 $1$。

其实答案中的每一个部分都在比赛中想到了,但是没有成功地组合起来。

Problem H

Upsolved by kblack.

题意:已知若干线段,求将平面划分的区域个数

题解:对每个联通部分,计算所有交点的数量以及线段的数量,通过欧拉公式获得每个联通部分内区域的个数,再加上无限的区域即可。

Problem I

Solved by ultmaster. 02:26 (+)

题意:有一个棋盘巧克力,拿到黑巧克力给愉悦度加 1,拿到白巧克力则减 1。一个人从左边拿若干列,另外一个人从下面拿若干行。求最优策略下的结果。

题解:$dp(h,w,black,turn)$ 表示 $h$ 行,$w$ 列,左下角是黑是白,是谁要操作了的状态的答案。转移是显然的。记忆化即可。

Problem J

Unsolved.

Problem K

Solved by zreol. 03:17 (+)

Problem L

Solved by kblack. 02:01 (+2)

Problem M

Solved by zerol. 01:14 (+1)