2018 Benelux Algorithm Programming Contest

From EOJ Wiki
Jump to navigation Jump to search

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)