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

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

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

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 }

法二