2018 Benelux Algorithm Programming Contest

Problem A

Solved by Weaver_zhu. 0:10 (+)

温暖的签到

Problem B

Solved by Kilo_5723. 0:54 (+1)

Problem C

Solved by Kilo_5723. 0:18 (+)

Problem D

Unsolved. (-4)

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 1:03 (+)

题意；有$n$个物品可供选择，每个物品需要花费$c_i$，之后每天都能获得的$p_i$的价值，求最小的天数获得价值$M$。

题解：二分天数，对于所有能赚的物品都收入囊中，和$M$比较大小即可。

Problem G

Solved by Xiejiadong. 1:36 (+)

题意：环上坐着三个队伍，要求同一个队伍的人都坐在一起，求最小化被交换的人数。

题解：首先如果确定了最终状态，那么被交换的人数最少就是和最终状态位置不一样的人数。

于是就是枚举最终状态，枚举三个队伍的相对关系，用暴力，一$6$种情况；

枚举每种情况下所有的队伍关系按照环移动的情况，用六个指针来表示没一个队伍的开头个结尾，用滑动窗口$O(1)$维护就好了。

Problem H

Solved by kilo_5723. 4:10 (+1)

Problem I

Solved by Xiejiadong. 3:21 (+1)

题意：$n$个点$m$条边的图中有$s$个避难所，要求所有的人进到其中一个避难所，并且花费时间最长的人时间最少。

题解：二分答案，于是可以根据预处理的距离得到$n$个点分别能到达那些避难所，根据能到达的不同避难所进行状压，由于只有$10$个避难所，所以最多只有$1024$种状态。

由于避难所有容量，每一个状态的人有总量，要求所有的人都至少能够到达一个避难所，考虑网络流建图。

对于每一个状态，限制流入的流量表示每一个状态最多的人数，限制每一个避难所流出的流量，表示每个避难所的最大容量。

如果最大流 = 总人数，那么显然这个时间是可行的，我们可以考虑把时间变得更小。

Problem J

Solved by Kilo_5723. 1:24 (+2)

Problem K

Solved by Weaver_zhu. 2:06 (+1)

题意：给一棵树，求加多少边使得整个树变成双连通分量

题解：问加多少边是原题，但是本题要构造解。本着犹豫就会败北冲上去瞎连边吃了一发罚时果断白给了，后来想想好像构造解也是多校里有过的结论。度数为1的点按dfs序排序，保证间隔n/2个点，奇数中间的连两边就行了。因为连边无效是因为两个点连在同一个子树下，且lca不是根节点。如果隔着一半连能两两匹配，而且一定能覆盖连完所有的子树，因为不可能两个子树的和加起来超过总叶子节点数，它们两个必定会相连。