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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <cstdio>
#include <algorithm>

const int maxn = 1e2 + 5;

int r, s, k, mi, mj, ans;
char mp[maxn][maxn];
int sum[maxn][maxn];

int main() {
    scanf("%d %d %d", &r, &s, &k);
    for (int i = 1; i <= r; i++) {
        scanf("%s", mp[i] + 1);
        for (int j = 1; j <= s; j++) {
            if (mp[i][j] == '*') sum[i][j]++;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + sum[i][j];
        }
    } 
    for (int i = k; i <= r; i++) {
        for (int j = k; j <= s; j++) {
            int tmp = sum[i - 1][j - 1] - sum[i - k + 1][j - 1] - sum[i - 1][j - k + 1] + sum[i - k + 1][j - k + 1]; //注意边界取不到
            if (tmp > ans) {
                ans = tmp;
                mi = i;
                mj = j;
            }
        }
    }
    printf("%d\n", ans);
    for (int i = mj - k + 1; i <= mj; i++) {
        mp[mi][i] = '-';
        mp[mi - k + 1][i] = '-';
    }
    for (int i = mi - k + 1; i <= mi; i++) {
        mp[i][mj] = '|';
        mp[i][mj - k + 1] = '|';
    }
    mp[mi][mj] = mp[mi][mj - k + 1] = mp[mi - k + 1][mj] = mp[mi - k + 1][mj - k + 1] = '+';
    for (int i = 1; i <= r; i++) {
        printf("%s\n", mp[i] + 1);
    }
    return 0;
}

AC居然只有80分。