[NOIP 1997 普及组] 棋盘问题

题意

给定一个 n × m 的棋盘。

要求统计两类图形的个数：

所有正方形的个数；
所有长方形的个数，但这里不包括正方形。

思路

先看一个最直接的暴力想法：枚举一个子矩形的左上角和右下角。

这样就能得到这个子矩形的高和宽，再判断它是正方形还是普通长方形：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解。
// 直接枚举子矩形的左上角和右下角，再判断它是正方形还是普通长方形。
int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    long long square_cnt = 0;
    long long rect_cnt = 0;

    for (int x1 = 1; x1 <= n; x1++) {
        for (int y1 = 1; y1 <= m; y1++) {
            for (int x2 = x1; x2 <= n; x2++) {
                for (int y2 = y1; y2 <= m; y2++) {
                    int height = x2 - x1 + 1;
                    int width = y2 - y1 + 1;
                    if (height == width) {
                        square_cnt++;
                    } else {
                        rect_cnt++;
                    }
                }
            }
        }
    }

    cout << square_cnt << ' ' << rect_cnt << '\n';
    return 0;
}

这个做法会枚举所有边界，复杂度是 $O(n^2m^2)$ 。

其实没必要真的把每个子矩形都一个个找出来，我们只需要按“尺寸”统计。

如果一个子矩形的高是 h，宽是 w，那么它在棋盘中的出现次数就是：

(n - h + 1) * (m - w + 1)

原因很直接：

上边界可以放在 1 到 n-h+1 这些位置；
左边界可以放在 1 到 m-w+1 这些位置。

于是我们只要枚举所有可能的 (h, w)：

如果 h == w，这是一种正方形，把出现次数加到正方形答案里；
否则这是一种普通长方形，把出现次数加到长方形答案里。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    long long square_cnt = 0;
    long long rect_cnt = 0;

    // 枚举子矩形的高和宽，统计这种尺寸一共能出现多少次。
    for (int h = 1; h <= n; h++) {
        for (int w = 1; w <= m; w++) {
            long long ways = 1LL * (n - h + 1) * (m - w + 1);
            if (h == w) {
                square_cnt += ways;
            } else {
                rect_cnt += ways;
            }
        }
    }

    cout << square_cnt << ' ' << rect_cnt << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(1)$

总结

这题的关键不是去找每一个具体图形，而是先按“高和宽”分类，再统计每种尺寸能放多少次。

从“枚举具体位置”转成“枚举尺寸”后，计数就会清楚很多。

[NOIP 1997 普及组] 棋盘问题

目录

题意

思路

代码

复杂度

总结