2018 Benelux Algorithm Programming Contest (BAPC 18)

Problem A

Solved by ultmaster. 00:17 (+)

在 $n$ 个数里选尽可能多的数，使得没有两个数加起来超过 $x$。

Problem B

Solved by zerol. 01:57 (+)

蛋疼模拟题意。毫无技巧。

Problem C

Solved by ultmaster. 01:08 (+)

题意：$\min (ab + ac + bc)$ subject to $abc = n$.

题解：预处理 $n$ 的所有因子，然后三方枚举一下。

Problem F

Solved by ultmaster. 00:42 (+)

题意：有 $n$ 个东西，选第 $i$ 个意味着 第一天赔本 $c_i$，后面每天有 $p_i$ 的利润。可以多选。求最少几天能赚到 $k$ 元跑路。本金无限。

题解：二分答案，然后赚的要，不赚的不要，加起来判一判就好。

Problem G

Solved by ultmaster. 01:20 (+)

题意：一个由 ABC 构成的环，问最少要让几个人离席才能让所有同一队的都坐在一起。

题解：枚举最终状态（A 开始的位置，后面是 B 还是 C），然后用前缀和快速算出要改的个数。

Problem I

Solved by ultmaster. 03:20 (+)

题意：无向图，有 10 个避难所，每个避难所有容量限制；每个点有一些人口。求最优方案下最晚到达避难所的人的到达时间。

题解：二分答案。然后对于每个避难所有一个它能接收的人口的点的集合。注意到对于每个避难所去或不去只有 1024 种不同的状态。把能去的避难所的集合相同的点合并一下，丢进去跑最大流。板子量有点大。

Problem J

Solved by kblack. 01:00 (+)

温暖的签到。

Problem K

Solved by kblack. 01:44 (+)

题意：给一张图添加一些边，使得图中不存在桥。

题解：首先所有叶子节点数量 $x$，每个叶子节点肯定要至少连一条边，这给出了加边量的一个下界。挑选一个节点，使得以这个节点为根后，叶子节点数最大的子树叶子节点数最小，一定不超过一半的数量，把所有的叶子节点按 dfs 序排列，按平移 $\lfloor\frac{x}{2}\rfloor$ 连边，这样需要的数量为下界 $\lceil\frac{x}{2}\rceil$。