2018 Benelux Algorithm Programming Contest

Problem A

Solved by Weaver_zhu. 0:10 (+)

温暖的签到

Problem B

Solved by Kilo_5723. 0:54 (+1)

题意：办公室内有一些人，这些人有生日。现在你想把你的生日安排在距离上一次有人过生日最久的一天，如果多解则尽可能靠近上一个 $10$ 月 $27$ 日，求最终会安排在哪一天。

题解：改掉喜欢找最优解的习惯，暴力一下就过了。

Problem C

Solved by Kilo_5723. 0:18 (+)

题意：构造一个三条边长都是整数的立方体，使得体积等于给定数值且表面积最小。

题解：在根号范围枚举前两条边的长度即可。

Problem D

Upsolved 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

Upsolved by Kilo_5723.

题意：给定一个序列，问其所有不同的排列中有哪些是完全乱序的，完全乱序的定义是每一个位置都是乱序的，一个位置是乱序的被定义为其左边有比他大的点或右边有比它小的点。

题解：二维 dp。

我们先将序列排序，并将其根据元素值分类。设 $cnt_i$ 代表第 $i$ 种元素的数量，$tot_i$ 代表前 $i$ 种元素的数量，$dp[i][j]$ 代表 考虑最小的 $i$ 类元素，前 $j$ 位乱序且 $j+1$ 位不乱序的情况总数。初始时，只有 $dp[0][0]=0$。将 $dp[i+1][j]$ 按照范围分为三类：

第一类 $0 \le j < tot_i$。这种情况下，第 $i+1$ 种元素要插在第 $j$ 个元素后面。

第二类 $j=tot_i$。这种情况下，第 $i+1$ 种元素全部在最后面。

第三类 $tot_i<j \le tot_{i+1}$。这种情况下，第 $i+1$ 种元素第一次出现的位置前面的部分一定是已经乱序的，而且末尾有 $tot_{i+1}-j$ 个连续的第 $i$ 种元素。

设共有 $m$ 种 $n$ 个数字，对每种情况算出 dp 值，$dp[m][n]$ 就是答案。

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)

题意：两个人轮流操作一个棋子在有向图上走，第一个人想让走的路程尽可能长，第二个人想让走的路程尽可能短，求最后走的路程长度，并特判无限长。

题解：我们考虑把每个点拆成两个，第一个点代表棋子在这里时第一个人走，第二个点代表第二个人走。

对于第一类点，只有它能到达的所有第二类点到终点的的路径长度都确定了才能确定它的路径长度。对于第二类点，只要它的最小可能路径长度是当前所有未确定的第二类点中最小的，就能确定它的路径长度。

我们知道终点拆出的两个点的路径长度都是 $0$，因此从终点按照这种规律扩展答案，如果能扩展到起点拆出的第一类点就输出答案，无法确定则这种情况下路程无限长。

Problem I

Solved by Xiejiadong. 3:21 (+1)

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

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

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

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

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

Problem J

Solved by Kilo_5723. 1:24 (+2)

题意：给定四条边长，求能构成的四边形面积的最大值。

题解：在猜结论1一定是梯形失败后，猜结论2：四边形面积和其中一条对角线的长度成单峰函数的关系。

在这种情况下，先枚举四条边的位置，再三分法求凸函数最大值，过了，说明猜对了。

Problem K

Solved by Weaver_zhu. 2:06 (+1)

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

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