Difference between revisions of "2017 Benelux Algorithm Programming Contest (BAPC 17)"
Line 2: | Line 2: | ||
Solved by kblack. 00:14 (+) | Solved by kblack. 00:14 (+) | ||
+ | |||
+ | 签到。 | ||
=== Problem B === | === Problem B === |
Revision as of 06:00, 9 March 2018
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)