题目背景
NOIP1997 普及组第一题
题目描述
设有一个N×M 方格的棋盘 (1≤N≤100,1≤M≤100)
求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。
例如：当 N=2,M=3时：
正方形的个数有 8 个：即边长为 1 的正方形有 6 个；边长为 2 的正方形有 2 个。
长方形的个数有 10 个：
即
- 2×1的长方形有 4 个：
- 1×2 的长方形有 3 个：
- 3×1的长方形有 2 个：
- 3×2 的长方形有 1 个：
输入格式
一行两个整数 N,M。
输出格式
一行两个整数，表示正方形的个数与长方形的个数。
输入输出样例
输入 #1
2 3
输出 #1
8 10
思路：
1. 首先，我们可以知道，棋盘中的正方形的个数与长方形的个数是可以通过计算边长为1的正方形和长方形的个数来计算得到的。
2. 遍历棋盘中的每一个格子，计算以该格子为左上角的正方形和长方形的个数。具体步骤如下：
a. 第一个循环遍历每一行，i表示行号。
b. 在每一行中，第二个循环遍历每一列，i1表示列号。
c. 在该行的第i1列，以该格子为左上角的正方形和长方形的个数可以通过计算以不同边长的正方形和长方形的个数来计算得到。具体步骤如下：
i) 第三个循环遍历从第i行到最后一行，j表示行号。
ii) 在每一行中，第四个循环遍历从第i1列到最后一列，j1表示列号。
iii) 根据当前格子与左上角格子的行列差是否相等，来判断是正方形还是长方形。如果相等，则为正方形，否则为长方形。
iv) 根据判断结果，分别更新正方形和长方形的个数。
3. 最后输出正方形和长方形的个数。
C++ 代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
int square = 0; // 正方形个数
int rectangle = 0; // 长方形个数
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
for (int k = i; k <= N; k++) {
for (int l = j; l <= M; l++) {
if (k-i == l-j) {
square++;
} else {
rectangle++;
}
}
}
}
}
cout << square << " " << rectangle << endl;
return 0;
}
时间复杂度分析：
1. 外层两个循环分别遍历N和M次，内层两个循环分别遍历从当前行列到最后一行列的次数。
2. 因此，总的时间复杂度为O(N*M*(N-i)*(M-j))。
3. 综上所述，该算法的时间复杂度为O(N^2 * M^2)。对于最大的N和M为100，可以忽略这个时间复杂度，算法是可以接受的。