2018 Benelux Algorithm Programming Contest (BAPC 18)

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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$。