Difference between revisions of "2018 Benelux Algorithm Programming Contest (BAPC 18)"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 8: Line 8:
  
 
Solved by zerol. 01:57 (+)
 
Solved by zerol. 01:57 (+)
 +
 +
蛋疼模拟题意。毫无技巧。
  
 
== Problem C ==
 
== Problem C ==
Line 44: Line 46:
  
 
Solved by kblack. 01:00 (+)
 
Solved by kblack. 01:00 (+)
 +
 +
温暖的签到。
  
 
== Problem K ==
 
== Problem K ==
  
 
Solved by kblack. 01:44 (+)
 
Solved by kblack. 01:44 (+)
 +
 +
题意:给一张图添加一些边,使得图中不存在桥。
 +
 +
题解:首先所有叶子节点数量 $x$,每个叶子节点肯定要至少连一条边,这给出了加边量的一个下界。挑选一个节点,使得以这个节点为根后,叶子节点数最大的子树叶子节点数最小,一定不超过一半的数量,把所有的叶子节点按 dfs 序排列,按平移 $\lfloor\frac{x}{2}\rfloor$ 连边,这样需要的数量为下界 $\lceil\frac{x}{2}\rceil$。

Latest revision as of 16:14, 2 April 2019

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