如此竞赛，令人汗颜！（【2024 年慈溪市小学生计算机程序设计竞赛复赛】口胡题解）
Bpds1110
·
·
题解
【2024 年慈溪市小学生计算机程序设计竞赛复赛】口胡题解。
如此竞赛，令人汗颜！
T1【group】
排序然后做完了。
T2【promotion】
模拟做完了，码量小得不行。
T3【bottom】
注意到题目给出的东西很想单调栈，于是直接模版上去，做完了。
T4【matrix】
给定一个 n \times n 的矩阵，每个格子上为 a_{i, j}，求一个连通块，最小化连通块内最大值和最小值的差值。
先考虑 $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$ 来自于我们的并查集。难度下位绿。