数学知识——正方形、矩形数量的计算

P2241 统计方形（数据加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.矩形、正方形数量公式：

运用小学时代的公式（设长为n，宽为m）：

(1+2+3+...+n)(1+2+3+...+m)

或

nm(n+1)(m+1)/4（等差数列的化简）

即可算出长方形个数。下面给出证明（请看上图）：

在AD中，单位长度为1的有两个，AJ,JD。单位长度为2的有一个，AD。同理,AB中单位长度为1的有三个，单位长度为2的有两个，单位长度为3的有一个。

每一种情况对应着邻边的所有情况。比如AJ对应AE,EF,FB,AF,EB,AB就是AB中的所有情况！这样就可以推导出上方的两个公式。

那正方形怎么求呢？其实，正方形就是上方公式的特殊情况，即单位长度相等的情况。可以有公式 ( n - i + 1 ) * ( m - i + 1) 求和----- i 的范围为[ 1 , min ( n , m ) ]

2.正方形数量计算：

假设图形之前正方形总数为sum1，若图形横向或纵向扩展一格，此时右下角坐标为 [ i , j ]，那么扩展后的图形中正方形最多有sum1+min( i , j )个

3.矩形数量计算：

假设图形之前矩形总数为sum2，若图形横向或纵向扩展一格，此时右下角坐标为 [ i , j ]，那么扩展后的图形中矩形最多有sum2+i * j 个

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n,m;
 7     scanf("%d%d",&n,&m);
 8     long long x=n*(n+1)/2,y=m*(m+1)/2;
 9     
10     int minn=min(n,m),maxx=max(n,m);
11     
12     long long sum1=0;
13     for(int i=1;i<=minn;i++)
14         sum1+=(n-i+1)*(m-i+1);
15     
16     printf("%lld %lld",sum1,x*y-sum1);
17     
18     return 0;
19 }

法一

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n,m;
 7     scanf("%d%d",&n,&m);
 8     
 9     long long ans1=0,ans2=0;
10     for(int i=1;i<=n;i++)
11     {
12         for(int j=1;j<=m;j++)
13         {
14             ans1+=min(i,j);
15             ans2+=i*j;
16         }
17     }
18     
19     printf("%lld %lld",ans1,ans2-ans1);
20     return 0;
21 }

法二

原文链接: https://www.cnblogs.com/wellerency/p/15861792.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍