Prozor-题解

原题链接:Link

题面描述

基本思路

不考虑实现,地球人都可以想到最朴素的暴力:

  1. 枚举每一个 \(K \times K\) 的矩形;
  2. 数出每个矩形中苍蝇的数量;
  3. 找到数量最多的那个矩形。把它画出来。

貌似我不是地球人
从友善的数据范围可以看到,我们应该把时间复杂度控制在 \(O(S^3)\) 以下。接下来让我们分析一下每一步分别怎么实现。

枚举每一个 \(K \times K\) 的矩形

确定一个矩形本来需要确定两个点(一条对角线上的),但是题目已经规定好了边长,所以只要确定一个点就可以确定矩形。这里我们统一用矩形右下角的顶点来表示矩形(其实那个点都可以),这样的话,我们只要枚举总共 \(S^2\) 个点,就可以确定 \(S^2\) 个矩形。时间复杂度 \(O(S^2)\) 。这样的话,数每一个矩形的数量的时候就只有 \(O(S)\) 的时间给我们用了。

数出每个矩形中苍蝇的数量

直接数显然是不理智的。每个矩形内有 \(K^2\) 个点,又有 \(S^2\) 个矩形,总共的时间复杂度会达到 \(O(K^2S^2)\) ,说不定能过呢肯定是会 \(T\) 的。有什么替代方法吗?

回想一下,如果是一个一维的问题,让你统计区间 \([l, r]\) 中所有数的和,你一定会喊出来“前缀和”这个答案。记 \(S[i]\) 表示 \([1, i]\) 中数的和, 那么可以在 \(O(n)\) 的时间预处理:

\[ S[i] = S[i - 1] + a[i] \]

然后在 \(O(1)\) 的时间求出答案:

\[ \sum_{i = l}^{r}{a[i]} = S[r] - S[l - 1] \]

现在,问题变成了二维的,照葫芦画瓢:记 \(S[i][j]\) 表示矩阵 \((1,1),(i,j)\) 中数的和,也就是 \(\sum_{x = 1}^{i}{\sum_{y = 1}^{j}{a[x][y]}}\) , 那么可以在 \(O(n^2)\) 的时间预处理:

\[ S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j] \]

这是个小小的容斥,可以自己画一个图。

那怎么计算呢?矩阵 \((i_1,j_1),(i_2,j_2)\) 的和可以计算为:

\[ S[i_2][j_2] - S[i_1 - 1][j_2] - S[i_2][j_1 - 1] + S[i_1 - 1][j_1 - 1] \]

这个容斥是二维前缀和的精髓,它在 \(O(1)\) 的时间求出答案,用 \(O(S^2)\) 的时间预处理。现在,总时间复杂度为 \(O(S^2) + O(S^2) * O(1) = O(S^2)\) 。显然不会 \(\text{T}\)

找到数量最多的那个矩形。把它画出来。

看上去挺烦,其实很简单。记录一下最优矩形的右下角的坐标,然后往上找 \(K\) 个,标为|,往左找 \(K\) 个,标为-,最后把四个角标为+

AC代码

AC居然只有80分。