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 by Weaver_zhu.

题意：在一个无向图中，两个人开车玩。一个人假定目前在A,一个假定在B。有一个人是对的，告诉你每个点是否能看到塔，每个点出度为2，求最少走多少步能判断哪个人对（如果一个和事实不符就说明另一个对了），或者无解。

题解：思维好题。bfs有$n^2$个状态,end up in TLE。最骚的是正解就是bfs优化。如果(a,b)在队列中，(b,c)在队列中，那么(a,c)也不需要搜认定它无解。为什么呢，如果(a,b)无解，(b,c)无解那么显然(a,c)无解，因为都是相同的，那么将无解看作等价关系。如果(a,c)有解，说明(a,b)(b,c)至少有一个也有解，那么也能找到解。为什么会比(a,c)优呢，因为假设(a,c)有一段怎么走都会有的公共前缀，那么如果(a,b)的前缀短，显然(a,b)更优。如果(a,b)的前缀长，那么(a,c)答案会和(b,c)一样（其实这里也是用到有限步数下无解是等价关系的原理）。用上并查集之后我们发现状态变成$O(n)$。

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不是根节点。如果隔着一半连能两两匹配，而且一定能覆盖连完所有的子树，因为不可能两个子树的和加起来超过总叶子节点数，它们两个必定会相连。