2017 Benelux Algorithm Programming Contest (BAPC 17)

Foreigners

Problem A

Solved by kblack. 00:14 (+)

签到。

Problem B

Upsolved by ultmaster.

吐血。

题意 & 题解：先求圆圆交点，然后两两连线，要求连边一定在圆的并内。然后求最短路。

• 不好写：花了 1 小时不到差不多写完。
• 错误 1：计算几何板子有点假。圆圆求交，同心圆的情况会炸。CF 居然给报 MLE？（一脸懵逼）最后拿 EOJ 上来调了。此处花费约 1.5 小时。
  • 一开始试图二分 assert，无果，不明白。
  • 无奈开始找数据，在 Clion 里一下子就炸了。网传 bad_alloc 是因为没有合理定义偏序关系。（一脸懵逼：我的偏序关系明明很好，难道是 EPS 的问题？）
  • 最后发现有几个点报了 NaN，再次调试之后发现模板里就炸了。
• 错误 2：求线段覆盖的那块好像出了点小 bug。调了一会儿。
• 错误 3：经过上面的折腾之后，最后大概有 3 个点一直 WA。可怜的我已经连调 EPS 都不会了，一直在肉眼调试。最后看了一眼 EPS=1e-12（什么鬼，题目数据范围 $10^{6}$。。。）。然后改了一下过了。2, 3 加起来花费约半小时。

最后写了三个小时？好像也不到点吧，两个半小时肯定有的。

总之不好写。EOJ 上又多了道千古无人题。

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

Solved by zerol. 01:14 (+1)

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

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

oxx1108

Problem A

签到

Problem C

题意：求1~n一共有多少种不同的区间gcd。

题解：用一个set维护以ai为左端点的区间的gcd，然后转移到ai+1

Problem D

题目比较难读懂

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

题解：反向跑最短路，记录不能走的边，然后跑一遍DFS。