原题链接:https://www.luogu.com.cn/problem/P2241
题意解读:要在整个n*m区域计算正方形和长方形的个数,枚举法即可。
解题思路:
此题枚举的对象是矩形的高i和宽j,高的范围[1, n],宽的范围[1, m],然后计算在n * m区域内有多少个i * j,i==j即属于正方形,i!=j属于长方形。
那么,问题就集中在了如何计算n * m的区域内有多少个i * j的矩形:
如上图,要在n * m范围内计算有多少个i * j的矩形,只需要看该矩形在水平、垂直方向各能移动多少步,
水平方向:可以移动m - j步,即水平方向可容纳m - j + 1个矩形,
垂直方向:可以移动n - i步,即垂直方向可容纳n - i + 1个矩形,
则整个n * m区域可容纳的i * j矩形数为(m - j + 1) * (n - i + 1)。
需要注意结果可能爆int!
100分代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
long long area = 0, rect = 0;
for(int i = 1; i <= n; i++) //枚举矩形的高
{
for(int j = 1; j <= m; j++) //枚举矩形的宽
{
//对于一个i * j的矩形, 计算在n * m范围内有几个
if(i == j) area += (n - i + 1) * (m - j + 1); //正方形
else rect += (n - i + 1) * (m - j + 1); //长方形
}
}
cout << area << " " << rect;
return 0;
}
标签:加强版,int,洛谷题,P2241,枚举,方向,容纳,矩形 From: https://www.cnblogs.com/jcwy/p/17997459