题目背景

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:

#include<iostream>
using namespace std;
int main(){//暴力穷举,规模大会超时
    int n,m,z=0,c=0;
    cin>>n>>m;
	for(int i=0;i<=m;i++)    
	  for(int j=0;j<=n;j++)   
	    for(int k=i+1;k<=m;k++)  
	       for(int l=j+1;l<=n;l++)  
	          if(k-i==l-j)z++;     //是正方形
	          else c++;            //是长方形
	cout<<z<<" "<<c;     
    return 0;
}

题解2:

参考大佬解析:

说说公式是怎么推导的吧

找规律:

正方形:

边长为1的正方形个数为n*m

边长为2的正方形个数为(n-1)*(m-1) （自己动手想想）

边长为3的正方形为个数(n-2)*(m-2)

边长为min(n,m)的正方形为个数s1=(n-min(n,m)+1)*(m-min(n,m)+1)

然后从边长为1到min（m，m）的正方形个数全部加起来；

长方形:(包括正方形，好像正方形属于长方形来着？)

长为1的长方形（包括正方形）有n个

长为2的长方形（包括正方形）有n-1个

长为n的长方形（包括正方形）有1个

长为1到n的长方形1+2+...+n个

同理 宽为1的长方形（包括正方形）有m个

宽为2的长方形（包括正方形）有m-1个

宽为m的长方形（包括正方形）有1个

宽为1-m的长方形1+2+...+m个

然后把它们乘起来，根据乘法原理，总数s2=((1+n)*(1+m)*n*m)/4;

题目要求的是“非正方形的长方形”，因此要减去s1

#include"cstdio"
#include"iostream"
using namespace std;
int main()//推导出数学公式,时间复杂度O(max(m,n)),orz
{
 int n,m,s1=0,s2;
 cin>>n>>m;
 s2=((m+1)*(n+1)*m*n)/4;
 for(;m>=1&&n>=1;m--,n--)
  s1+=m*n;                       
 cout<<s1<<" "<<s2-s1;
return 0;
}

题解3:

参考大佬解析:

首先容易知道如果长方形（包括正方形）的边长为a和b，那么数量为(n−a+1)(m−b+1)

然后对于所有的a和b做就好了

答案为(1+2+3+...+n)(1+2+3+...+m)

就是4nm(n+1)(m+1)​

正方形也很好做啊

枚举所有的i，数量为(n−i+1)(m−i+1)

就是∑i=1min(n,m)​(n−i+1)(m−i+1)=∑i=0min(n,m)−1​(n−i)(m−i)

因为在i=min(n,m)时没有影响

所以为了方便就加上i=min(n,m)

然后变成∑i=0min(n,m)​(n−i)(m−i)

然后拆开变成mn+i×i−(m+n)i

用l代替min(n,m)就是nm(l+1)+l(l+1)(2l+1)/6−l(l+1)(m+n)/2

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int main()//时间复杂度O(1),orrrrrrrrrrz
{
	cin>>n>>m;
	int nn=min(n,m);
	int z=m*n*(nn+1)+nn*(nn+1)*(2*nn+1)/6-(m+n)*nn*(nn+1)/2;
	int c=n*(n+1)/2*m*(m+1)/2-z;
	cout<<z<<" "<<c<<endl;
}