P2241 统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

有一个 $n\times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 $n,m$（$n\le 5000,m\le 5000$）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

2 3
1

样例输出 #1

8 10
1

1.题目分析

求一个N行M列的棋盘矩形里，分别包含了多少长方形和正方形的个数？

这里提供两种思路：

1.数学规律

长方形的个数：长累减到1之和 乘上 宽累减到1。
例如：上述案例，N = 2,M = 3:
长方形的个数就为：（2+1）*（3+2+1） = 18.

2.二维矩阵推理

• 定义一个二维数组，每一个元素存储： 从当前结点到最后一个结点可构成的长方形个数（包括正方形）。
• 总个数等于：当前点到最后一个元素构成的图形的面积。
• 正方形的个数等于：当前点到最后一个元素构成的图形的最小边。
• 长方形的个数等于：总个数减去正方形个数。

这里采用的是第二种思路。

2.题目思路

1. 创建一个n行j列的矩阵
2. 定义正方形的个数，正方形和长方形的总个数
3. 值得一提的是，总个数采用的数据类型必须是long long，防止数据越界。
4. 两个for循环：计算每一点可构成的长方形个数并累加到总和。
5. 计算正方形个数。
6. 循环结束：输出正方形和（总和减去正方形个数）长方形个数。

3.代码实现

#include 
#include 

using namespace std;

int main() {
    //创建一个n行j列的矩阵，
    // 每一个元素存储： 从当前结点到最后一个结点可构成的长方形个数（包括正方形）
    int n, m;
    cin >> n >> m;
    int arr[n][m];
    //正方形的个数
    int zh = 0;
    //正方形和长方形的总个数
    //这里使用长整型防止数据越界
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            //计算每一点可构成的长方形个数
            arr[i][j] = (m - j) * (n - i);
            //累加
            sum += arr[i][j];
            //计算正方形个数
            zh += min(m - j, n - i);
        }
    }
    //输出正方形和（总和减去正方形个数）长方形个数
    cout << zh << " " << sum - zh;
    return 0;
}

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