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

题意：给一个有向完全图，求一棵以 $n$ 为根的生成树，使得每个结点中至多有一个儿子深度大于 1。

题解：先求出任意一棵生成树，然后进行调整。如果有两个儿子深度大于 1，那么根据者两个儿子在有向完全图中的关系，让一个儿子的父亲改为另一个儿子，并递归下去，每次需要考虑的子树大小至少减 1，调整过程复杂度 $O(n^2)$。

Solved by zerol. 03:17 (+)

Problem L

Solved by kblack. 02:01 (+2)

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

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

Problem M

题意：二维坐标中从某个点到某个点只能水平或垂直移动在不绕远路的情况下最多经过的点数。

题解：考虑起点和终点构成的矩形之中的所有点，按照一维排序就转化成了最长不下降子序列。由于某些原因，写了 cdq 分治，复杂度 $O(n\log ^2n)$ 但还是过了。期间因为没有判边界（0 个点）导致无限递归（MLE）。

Solved by zerol. 01:14 (+1)