如此竞赛，令人汗颜！（【2024 年慈溪市小学生计算机程序设计竞赛复赛】口胡题解）

【2024 年慈溪市小学生计算机程序设计竞赛复赛】口胡题解。

排序然后做完了。

模拟做完了，码量小得不行。

注意到题目给出的东西很想单调栈，于是直接模版上去，做完了。

给定一个 $n \times n$ 的矩阵，每个格子上为 $a_{i, j}$，求一个连通块，最小化连通块内最大值和最小值的差值。

$1 \le n \le 100$，$1 \le a_{i, j} \le 10^3$。

先考虑 $O(n^4)$ 做法，枚举每个 $a_{i, j}$ 作为最小值，将 $\ge a_{i, j}$ 的数通过 BFS 得到连通性，然后 $a_{i, j}$ 所到达的最大的数即为可能的结果，这样就做完了。难度上位橙。

考虑 $O(n^2 \times a_{i, j})$，发现枚举时只需枚举 $a_{i, j}$ 的值即可。难度上位橙。

但是这个时间复杂度是达不到我们对【小学生】的要求的    ，考虑优化。

我们注意到，如果从大到小枚举 $a_{i, j}$ 的值，连通块是每次合并的，并且总共合并次数不超过 $4n^2$。

于是，考虑预处理所有值为 $k(1 \le k \le 10^3)$ 的位置，然后 $i$ 从大到小枚举 $k$，合并值为 $i$ 的四周。然后，枚举所有值为 $i$ 的位置，求最大即可。

这样的时间复杂度为 $O(m + 4n^2 \log_2 n^2)$ 的，$\log$ 来自于我们的并查集。难度下位绿。