怎么建立一个公司的网站,中铁建设集团门户网app,做网站需要的法律知识,业务宣传网站建设题目背景
1997年普及组第一题
题目描述
有一个 n m n \times m nm 方格的棋盘#xff0c;求其方格包含多少正方形、长方形#xff08;不包含正方形#xff09;。
输入格式
一行#xff0c;两个正整数 n , m n,m n,m#xff08; n ≤ 5000 , m ≤ 5000 n \leq 5000…题目背景
1997年普及组第一题
题目描述
有一个 n × m n \times m n×m 方格的棋盘求其方格包含多少正方形、长方形不包含正方形。
输入格式
一行两个正整数 n , m n,m n,m n ≤ 5000 , m ≤ 5000 n \leq 5000,m \leq 5000 n≤5000,m≤5000。
输出格式
一行两个正整数分别表示方格包含多少正方形、长方形不包含正方形。
样例 #1
样例输入 #1
2 3样例输出 #1
8 101.题目分析
求一个N行M列的棋盘矩形里分别包含了多少长方形和正方形的个数
这里提供两种思路
1.数学规律
长方形的个数长累减到1之和 乘上 宽累减到1。 例如上述案例N 2,M 3: 长方形的个数就为21*321 18.
2.二维矩阵推理
定义一个二维数组每一个元素存储 从当前结点到最后一个结点可构成的长方形个数包括正方形。总个数等于当前点到最后一个元素构成的图形的面积。正方形的个数等于当前点到最后一个元素图形的最小边。长方形的个数等于总个数减去正方形个数。
这里采用的是第二种思路。
2.题目思路
创建一个n行j列的矩阵定义正方形的个数正方形和长方形的总个数值得一提的是总个数采用的数据类型必须是long long防止数据越界。两个for循环计算每一点可构成的长方形个数并累加到总和。计算正方形个数循环结束输出正方形和总和减去正方形个数长方形个数。
3.代码实现
#include iostream
#include math.husing 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;
}
