2017 Benelux Algorithm Programming Contest (BAPC 17)

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

Upsolved by ultmaster.

题意：有若干青蛙，可以在直线上跳舞，第一次跳 $1$ 步，第二次跳 $2$ 步……最后要全部汇集到一个点。求所需要的最少步数和。有若干次询问：增加青蛙，减少青蛙，改变汇集点。

题解：先求出从 $0$ 到右边 $10^6$ 个点的最少步数（找规律）。然后维护两个线段树，每个点上记录的值是所有青蛙都汇集到这个点的代价。然后函数分奇偶单调。就可以转换成区间操作，点查询。用树状数组也可以。

Problem K

Solved by zreol. 03:17 (+)

Problem L

Solved by kblack. 02:01 (+2)

题意：给出一系列有顺序的果汁间单向兑换的比例，求从 1L 粉色果汁兑换到的最多的蓝色果汁。

题解：显然一定有一个比例最大的兑换路径，直接记录当前某种果汁的最大拥有量即可。因为乘法数量巨大，需要使用自然对数来保证精度。

Problem M

Solved by zerol. 01:14 (+1)