曾彪彪的个人博客 -- P2241 统计方形（数据加强版）

## 题目背景

1997年普及组第一题

## 题目描述

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

## 输入格式

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

## 输出格式

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

## 输入输出样例 #1

### 输入 #1

```
2 3
```

### 输出 #1

```
8 10
```

这道题先前用爆搜写了一个算法，但是会超时。时间复杂度是o(n^4)代码如下：

```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
-
brute force,
loop
-
-
test case:
-
2 3
-
2 2
-
3 3
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

int main()
{

// freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    int n, m;
    cin >> n >> m;
    long squ = 0, rec = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int k = i + 1; k <= n; k++)
            {
                for (int l = j + 1; l <= m; l++)
                {
                    if (k - i == l - j)
                    {
                        squ++;
                    }
                    else
                    {
                        rec++;
                    }
                }
            }
        }
    }

cout << squ << " " << rec;
    return 0;
}

```

后面看别人的算法，原来这是一道数学题。分析如下：

1. 先计算矩形的个数，矩形包括长方形和正方形。这应该是小学奥数题，我们已3*2放歌为例，那么整个矩形的个数是(1+2+3)*(1+2)=18个。
这里其实用到了分布思想，分布用乘法。要构建一个矩形，先横着数，总共矩形个数是3个。以下面数字举例：
123
456
假设每个数字代表一个方格，那么横着数，矩形的个数是：1，12，123，2，23，3.
竖着数，矩形的个数是1，14，4.  总数量是(1+2+3)*(1+2)=18.
2. 再计算正方形的个数。
正方形的个数要用到分类的思想，我们以4*3个放个数为例子。
1234
5678
9ABC
分情况讨论：
- 边长是1的正方形个数：1~C共12个。相当于n*m。
- 边长是2的正方形个数：我们来数一下，分别是：
12 23 34
45 67 78
56 67 78
9A AB BC
总共8个，这里的计算，也是用到分布思想：横着数边长为2的正方形个数为(m-1)=4-1=3个，竖着数边长为2的正方型个数为(n-1)=3-1=2个。
那么(m-1)*(n-1)=3*2=6个。
后面就不一一列举了，边长为x的正方形个数为 （m-x+1)*(n-x+1)。这里假设n>m，那么最大的正方形，边长为m。

有了这个公式，我们就可以计算了。
先回忆下等差数列求和公式
sn=1+2+3...+n=n*(n+1)/2.

代码如下：

```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
-
brute force,
loop
-
-
test case:
-
2 3
-
2 2
-
3 3
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    long long n, m;
    cin >> n >> m;
    long long squ = 0,
              rec = 0, total = 0;
    total = (n * (n + 1) / 2) * (m * (m + 1) / 2);

for (int i = 1; i <= min(n, m); i++)
    {
        squ += (n - i + 1) * (m - i + 1);
    }

rec = total - squ;

cout << squ << " " << rec;
    return 0;
}

```
在上面代码中，数据类型需要选择long long，因为在windows 64位系统中，long类型和int类型长度一样，都是32位，可以用sizeof(int)，sizeof(long)来进行测试。
如果使用long类型，那么输入400 400，数据会越界。

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

评论(0)