暑假集训 Day3 总结

前言：

今天比赛 $485$ 分，依旧开心。

D.池塘

赛场暴力 $24$ 分，RE，因为数据范围比较大，时间复杂度为 $O(n^4)$，一定是不可行的。

正解思路

这道题可以用二维前缀和和二分解决。首先，我们要二分中位数，在 check 函数里面求前缀和。首先，我们可以创建一个新的数组 $s$，如果当前的 $a_{i,j}>x$ 那么令 $s_{i,j}=1$ 否则令 $s_{i,j}=1$。这时，我们就把问题变成了一个经典的前缀和，接下来只要套模板就可以了，$s_{i,j}=s_{i,j}+s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}$。接下来，我们用双重 for 循环，遍历 $k$ 到 $n$，判断当前范围比二分的中位数大的数有几个，可以用到公式 $s_{i,j}-s_{i-k,j}-s_{i,j-k}+s_{i-k,j-k}$。如果比二分的中位数大的数小于等于 $k^2\div 2$ 那么这个中位数就是可以的。如果最后所有区间都枚举完了这个中位数还不合法，就返回 false。

F.恰好一个

这题赛场上拿了 $61$ 分，正解思路应该是并查集或者 DFS。

正解思路：

我们这里用并查集的思路去做这一题。首先，我们先把并查集的模板写出来。特别的，这一题的 merge 函数需要用启发式合并，把节点少的连通分量合并到节点多的连通分量上面去。所以，我们可以多创建两个数组 $v$ 与 $e$ 存储当前连通分量的点与边的个数。合并完之后，我们就遍历所有的点，用 set 存储每一个点的老大，由于 set 有单一性，所以 set 的大小就是连通分量的数量。我们枚举每一个老大代表每一个连通分量，如果有一个连通分量不满足 $v_i=e_i$，那么就输出 $0$，结束运行。为什么 $v_i=e_i$ 才满足条件呢？因为有结果的情况一定是存在环的情况，根据小学数学知识，环形植树问题树的数量等于空格数量，同理，这里应是点的数量等于边的数量。最后输出 $2$ 的连通分量次方。因为它是有环的，所以可以有顺时针转也可以逆时针转两种情况，而且每一个连通分量都是独立的所以根据乘法原理，答案就为 $2$ 的连通分量次方。