本文主要是介绍【NOIP 1997 普及组】统计方形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 题目描述
- 思路分析
- 评价
题目描述
有一个 n × m n×m n×m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。
时间限制：1 s
内存限制：128 MB
- 输入
一行，两个正整数 n n n 和 m m m。原题数据范围较小，这里假设 n n n 和 m m m 均小于 50000 50000 50000。 - 输出
一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。 - 样例输入
2 3 - 样例输出
8 10
思路分析
此题可以用双层循环来解决。分别枚举两条邻边的长度，假设水平方向的边长为 e d g e a edge_a edgea，总长度为 n n n，那么水平方向有 n − e d g e a + 1 n - edge_a + 1 n−edgea+1 种不同的情况。同理可得竖直方向有 m − e d g e b + 1 m - edge_b + 1 m−edgeb+1 种不同的情况。因此在枚举过程中若 e d g e a = e d g e b edge_a = edge_b edgea=edgeb，将 ( n − e d g e a + 1 ) × ( m − e d g e b + 1 ) (n - edge_a + 1) \times (m - edge_b + 1) (n−edgea+1)×(m−edgeb+1) 累加到正方形数量中，否则将 ( n − e d g e a + 1 ) × ( m − e d g e b + 1 ) (n - edge_a + 1) \times (m - edge_b + 1) (n−edgea+1)×(m−edgeb+1) 累加到长方形数量中即可。该算法的时间复杂度为 O ( n m ) O(nm) O(nm)。
/** Name: count1.cpp* Problem: 统计方形* Author: Teacher Gao.* Date&Time: 2024/03/07 23:52*/#include <iostream>using namespace std;int main()
{long long n, m, square = 0, rectangle = 0;cin >> n >> m;for (int edge_a = 1; edge_a <= n; edge_a++) {for (int edge_b = 1; edge_b <= m; edge_b++) {if (edge_a == edge_b) {square += (n - edge_a + 1) * (m - edge_a + 1);}else {rectangle += (n - edge_a + 1) * (m - edge_b + 1);}}} cout << square << ' ' << rectangle;return 0;
}
考虑上述双重循环，在计算长方形数量时若不区分正方形和长方形，直接累加到长方形数量中，最终减去正方形的数量亦可。注意到长方形的边长 e d g e a edge_a edgea 和 e d g e b edge_b edgeb 分别会取遍 1 ∼ n 1 \sim n 1∼n 和 1 ∼ m 1 \sim m 1∼m，因此我们对上述公式稍作变形可以得到 e d g e a × e d g e b edge_a \times edge_b edgea×edgeb。于是，在此种情况下，长方形数量满足公式
∑ i ∈ [ 1 , n ] , j ∈ [ 1 , m ] i j = ( ∑ i = 1 n i ) ( ∑ j = 1 m j ) = n ( n + 1 ) 2 × m ( m + 1 ) 2 \sum_{i \in [1, n], j \in [1, m]}i j = \bigg(\sum_{i = 1}^{n}i\bigg) \bigg(\sum_{j = 1}^{m}j\bigg) = \frac{n (n + 1)}{2} \times \frac{m (m + 1)}{2} i∈[1,n],j∈[1,m]∑ij=(i=1∑ni)(j=1∑mj)=2n(n+1)×2m(m+1)
事实上，正方形的边长最长为 min { n , m } \min\{n, m\} min{n,m}。因此，可以用单层循环枚举正方形的边长 e d g e edge edge，将 ( n − e d g e + 1 ) × ( m − e d g e + 1 ) (n - edge + 1) \times (m - edge + 1) (n−edge+1)×(m−edge+1) 累加到正方形数量中即可。该算法的时间复杂度为 O ( min { n , m } ) O(\min\{n, m\}) O(min{n,m})。
/** Name: count2.cpp* Problem: 统计方形* Author: Teacher Gao.* Date&Time: 2024/03/08 00:00*/#include <iostream>using namespace std;int main()
{long long n, m, square = 0, rectangle = 0;cin >> n >> m;if (n > m) swap(n, m);for (int edge = 1; edge <= n; edge++) {square += (n - edge + 1) * (m - edge + 1);}rectangle = m * (m + 1) / 2 * (n * (n + 1) / 2);cout << square << ' ' << rectangle - square;return 0;
}
接下来，我们对正方形的数量也进行公式化分析。不失一般性地，我们假设 n < m n < m n<m。对正方形的计算式稍作变形后，可以得到正方形数量的计算公式
∑ i ∈ [ 1 , n ] i ( m − n + i ) = ( m − n ) ∑ i ∈ [ 1 , n ] i + ∑ i ∈ [ 1 , n ] i 2 = ( m − n ) × n ( n + 1 ) 2 + n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{i \in [1, n]}i (m - n + i) = (m - n) \sum_{i \in [1, n]}i + \sum_{i \in [1, n]}i^2 = (m - n) \times \frac{n (n + 1)}{2} + \frac{n (n + 1) (2n + 1)}{6} i∈[1,n]∑i(m−n+i)=(m−n)i∈[1,n]∑i+i∈[1,n]∑i2=(m−n)×2n(n+1)+6n(n+1)(2n+1)
至此，我们得到了此题 O ( 1 ) O(1) O(1) 时间复杂度的解法。
/** Name: count3.cpp* Problem: 统计方形* Author: Teacher Gao.* Date&Time: 2024/03/08 00:10*/#include <iostream>using namespace std;int main()
{long long n, m, square = 0, rectangle = 0;cin >> n >> m;if (n > m) swap(n, m);square = n * (n + 1) / 2 * (2 * n + 1) / 3 + n * (n + 1) / 2 * (m - n);rectangle = m * (m + 1) / 2 * (n * (n + 1) / 2);cout << square << ' ' << rectangle - square;return 0;
}
评价
此题的难度并不算大，但是对程序效率的优化并不容易想得到。博主在教学过程中发现，几乎所有学生都只会用循环嵌套的方式求解，极少有学生对公式求出闭式解。类似这种具有明显规律的循环求和问题，求出闭式解是优化程序效率的一种行之有效的方法。
这篇关于【NOIP 1997 普及组】统计方形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
