ZROI普及五连测 10.11

涨了好多分,舒适.(但只有 $250pts$ 很不开心,没写出来 $D$.)

A.旋风回旋曲

要么直接走过去,要么走到一端再坐缆车去另一端.取$min$即可.
但我不是这么写的,我用了$Floyd.$
从 $0$ 到 $100$ 相邻的两个数字都建一条长度为 $1$ 的边.
然后缆车的两端建一条长度为 $0$ 的边.
跑 $Floyd$ 输出 $e_{x,y}$ 即可.

一开始一眼看完,以为是个 $SB$ 的枚举子集.

然后发现,直接枚举行不通…还要全排列,会 $TLE$.

于是考虑枚举题目要求的平方式中的平方根,这是 $10^6$ 左右级别的.
然后再把这个平方根的平方拆位用桶记录,查询能否用原数的数字集合拼出即可.

复杂度的话 $\Theta(T\times \sqrt{n} \times log_{10}{n})$

咕咕咕…

第一眼看过去就觉得这题十分归程 $(NOI2018\: D1\: T1)$.
不过更简单一些.
把所有的询问和矩阵元素降序排序.
从大到小加入连通块并统计个数即可.
每新加入一个点就 $++$ 连通块个数,扫描它的上下左右四连通方向,如果有一个连通块就 $–$ 连通块个数,按照顺序输出即可.