Baltic Olympiad in Informatics 2016
| Bosses | Park | Spiral | Cities | Maze | Swap |
|---|---|---|---|---|---|
| $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{red}{\texttt{-}}$ | $\color{red}{\texttt{-}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ |
链接 题面链接 中文题面
A. Bosses
可以发现一个方案的总代价是所有点的深度之和。考虑枚举根，贪心的选一定让每个点往深度最小的点上挂。
所以连反边 bfs 一遍即可。复杂度 $O(n+m)$。
代码
1 |
|
B. Park
定义两个圆之间的边为它们的距离（圆心距离减去半径之和）认为四个边界是四个特殊的圆。那么要使 $1,2$ 不连通，需要存在从 $1,2$ 的边界到其他边界只通过 $\leq 2r$ 的边的路径。换句话说就是把 $1,2$ 割开了。
其他同理。可以发现这就是最小瓶颈路，直接暴力枚举每对边界，暴力求瓶颈路，就可以做到 $O(1)$ 查询。
复杂度 $O(16n^2+n^2\log n+q)$。
代码
1 |
|
D. Cities
最小斯坦纳树板子题。
用 dijkstra 增广，复杂度 $O(n2^k\log n+n3^k)$。
代码
1 |
|
F. Swap
题目给的序列可以看成一棵完全二叉树，其中一个节点可以依次和左右儿子交换。
不妨假设根，左儿子，右儿子分别是 $a,b,c$。
- $a < \min(b,c)$，显然什么都不干。
- $b< a$，必然只能交换 $a,b$。
- $c< \min(a,b)$，根必然是 $c$，左右儿子可以是 $a,b$ 也可以是 $b,a$。
问题在于 $a,b$ 优还是 $b,a$ 更优不能直接判断。
不妨假设 $a< b$，如果 $a$ 放到左子树后最后的位置是 $p$，那么 $b$ 放到左子树后 $p$ 位置的值一定会变大。右子树同理。所以只需要看 $a$ 放到左子树后的位置与放到右子树的位置哪一个靠前即可。
所以假设 $a$ 被放入左子树，利用类似的策略可以确定 $a$ 最终位置。于是就可以推出 $a$ 被放入左子树优还是右子树优。
考虑分析时间复杂度：注意到一个事情，就是假设 $v$ 放入 $u$ 时，必然有 $v$ 是 $u$ 的祖先或者祖先的兄弟，换句话说合法 $v$ 取值只有 $2\log n$ 个。直接用 map 记忆化搜索，这样一个点只会被访问 $O(\log n)$ 次。
总复杂度 $O(n\log^2 n)$，并且跑不太满。
代码
1 |
|