统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

有一个 \(n \times m\) 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 \(n,m\)（\(n \leq 5000,m \leq 5000\)）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

2 3

样例输出 #1

8 10

2. 题解

2.1 两点定方形

思路

取范围中两点（非同行或同列）即可确定一个方形，由于每个点存在两个坐标（x,y）,所以嵌套了四层循环。
这里我是按行枚举各点的，所以避免了点上下颠倒的重复（比如像开始我是左上，你是右下；后面你是左上，我是右下）
但还是面临着一种重复情况：左上和右下，左下和右上实际上指的是同一个方形的重复，所以在最后的结果里面要 ÷2！！！

代码

// 两点定方形法 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin >> n >> m;
	int square = 0, rectangle = 0;
	// 注意虽然棋盘是n*m，其实有(n+1)*(m+1)个点，这个就是点 = 边数 + 1的问题 
	for(int i = 0; i <= n - 1; i++){
		for(int j = 0; j <= m; j++){ //确定当前点的行和列 
			for(int k = i + 1; k <= n; k++){ //这里是i+1，因为我是一行一行遍历的，上面各行已遍历完相应顶点，这里不可重复选取 
				for(int l= 0; l <= m; l++){ //确定另一个和当前点构成方形的点位置 
					if(i != k && j != l){
						if(abs(k - i) == abs(l-j)) square++;
						else rectangle++;
					}
				}
			}
		}
	} 
	cout << square / 2 << ' ' << rectangle / 2; // 方形存在着：1.左上方和右下方顶点 2.左下方和右上方顶点 两种情况，所以要除2 
}

复杂度

时间复杂度 \(O(n^2 m^2)\) 过大，不适合

2.2 一点定方形法（中心点法）

思路

这里可以结合下图中的对角线来理解，确定一个中心点之后，沿其四周对角线展开的点都能构成正方形，而剩余的点（非同行同列）构成的都是长方形即可
同时要注意去重！！！

代码

// 一点定方形法（中心点法） 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin >> n >> m;
	long long squ = 0, rec = 0; // 注意这里（n≤5000,m≤5000），可能生成的实际方形数量个数超出int范围！！！ 
	
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++){
			// 分别向左下方，左上方，右下方，右上方画对角线； x,y同时均匀减1，直到有一方到达边界线，同时也说明对角线到达了便捷 
			int tmp = min(i, j) + min(i, m - j) + min(n - i, j) + min(n - i, m - j);
			squ += tmp;
			rec += m * n - tmp; // 虽然有 (m+1)行， (n+1)列，但是该点和同行或同列的点无法构成方形！！！ 所以只算m行，n列 
		}
	} 
	cout << squ / 4 << ' ' << rec / 4; // 一个方形有四个顶点：1.正方形是以我们的顶点为中心扩散的，四个顶点重复四次 2.长方形同理 
}

复杂度

时间复杂度 O(mn), 大幅减少了枚举数量。

2.3 一点定方形法（边界点法）

思路

上述方法在最后还需要进行去重操作，说明进行了过多无用的重复计算，能否继续简化呢？可以的。
我们之前由于枚举的是中心点向四周扩散，那么我们现在是否能枚举一个边界点，只向一个区域扩散呢？

代码

// 一点定方形法（边界点法） 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin >> n >> m;
	long long squ = 0, rec = 0; // 注意这里（n≤5000,m≤5000），可能生成的实际方形数量个数超出int范围！！！ 
	
	for(int x = 0; x <= n; x++){
		for(int y = 0; y <= m; y++){
			int tmp = min(x, y); // 这里假设枚举的点只为方形的右上方点，避免重复计算,对角线朝左下方进行 
			squ += tmp;
			rec += x * y - tmp; //只考虑该点左下方的情况，同样的同行同列无法构成方形，但是其实点从0开始，多一个，所以还是x*y; 
		}
	} 
	cout << squ << ' ' << rec; // 一个方形有四个顶点：1.正方形是以我们的顶点为中心扩散的，四个顶点重复四次 2.长方形同理 
}

复杂度

时间复杂度：O(mn),但是简化了计算，减少了计算量

2.4 边定方形法

思路

前面的思路都是枚举点，那么可以枚举边吗？

代码

// 边定方形法
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin >> n >> m;
	long long squ = 0, rec = 0; // 注意这里（n≤5000,m≤5000），可能生成的实际方形数量个数超出int范围！！！ 
	
	// 边和点不同，范围是[1, n] 和 [1, m], 而不是从0开始 
	for(int a = 1; a <= n; a++){
		for(int b = 1; b <= m; b++){
			if(a == b){
				squ += (n - a + 1) * (m - b + 1); 
			}
			else rec += (n - a + 1) * (m - b + 1);
		}
	} 
	cout << squ << ' ' << rec; 
}

复杂度

时间复杂度：O(mn),但是枚举的是边

2.5

思路

总思路就是正方形数量求解起来远远比长方形简单，所以先求正方形数量，再用总数量减去正方形数量即可
这里有个小问题：矩形总数量咋求？
观察2.4中无论是正方形还是长方形，每次计算数量都是(n - a + 1) * (m - b + 1)
外层循环：for(int a = 1; a <= n; a++){
for(int b = 1; b <= m; b++){
最后计算时其实是:
a = 1: 1 * (m + m - 1 + m - 2 + .... + 1) = 1 * m(m+1)/2
a = 2: 2 * (m + m - 1 + m - 2 + .... + 1) = 2 * m(m+1)/2
....
a = n: n * (m + m - 1 + m - 2 + .... + 1) = n * m(m+1)/2
加起来就是 (1 + 2 + ... + n) * m(m+1)/2 = n(n+1)/2 * m(m+1)/2

这里我找到了一种更好理解的方式：
以点的方式来确定边（都是两个点确定一条边）：横边 \(C_(N+1)^2\) ------竖边 \(C_(M+1)^2\)
这里n是确定哪一列，m是确定哪一行，互不影响，可以任意组合，所以总和结果直接将二者相乘即可

代码

// 公式法 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin >> n >> m;
	long long squ = 0, rec = 0; // 注意这里（n≤5000,m≤5000），可能生成的实际方形数量个数超出int范围！！！ 
	
	// 若只是枚举正方形，那么只需要枚举一边即可 
	for(int a = 1; a <= min(m , n); a++){ //这里要注意，我们求的是正方形，由于木桶效应，短板决定范围！！！ 
		squ += (n - a + 1) * (m - a + 1); 
	} 
	rec = (long long)n * (n + 1) * m * (m + 1) / 4 - squ; // 这里减号前面的部分都是int类型，直接计算会发生溢出，需要进行强制类型转换 
	cout << squ << ' ' << rec;
}

复杂度

时间复杂度：简化到了 O(min(m,n))