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)