A2.数方格 AC题解

🧠 一、题目理解回顾
题目要求：在一个 n × m 的矩形区域内，统计所有可能的正方形广场方案数。每个广场必须是边长为整数的正方形，且其边必须与单位格子对齐（不能斜放或跨格）。

✅ 正确的解题思路：
在一个 n × m 的网格中，可以放置的边长为 k 的正方形数量为：

(n - k + 1) × (m - k + 1)
因为正方形的左上角可以在 ( 的位置，只要 i + k - 1 ≤ n且j + k - 1 ≤ m`。

所以我们需要对所有可能的正方形边长 k（从 1 到 min(n, m)）进行求和：

\text{总方案数} = \sum_{k=1}^{\min(n, m)} (n - k + 1) \times (m - k + 🧮 二、你的代码逻辑分析 你的代码如下： cpp #include<iostream> using namespace std; int main(){ long long n, m; cin >> n >> m; long long sum = 0; if(n <= m){ for(int i = n, j = m; i > 0; i--, j--){ sum += i * j; } } else { for(int i = n, j = m; j > 0; i--, j--){ sum += i * j; } } cout << sum; return 0; } ### ✅ 代码逻辑说明： 你通过一个循环，从最大边长开始递减，依次计算每个可能的正方形边长对应的数量： - 当 n <= m 时，循环从 i = n 到 i = 1，同时 j = m 到 j = m - n + 1 - 每次计算的是 (n - k + 1) * (m - k + 1)，其中 k 从 1 到 min(n, m) 所以，你的代码实际上等价于： cpp for(int k = 1; k <= min(n, m); ++k){ sum += (n - k + 1) * (m - k + 1); } 只是你用了倒序的 i-- 和 j-- 的方式，来等价实现这个逻辑。 --- ## ⏱️ 三、时间复杂度分析 ### ✅ 循环次数： 你只进行了一次循环，循环次数为：
\min(n, m)

因为每次循环中执行的都是基本操作（乘法、加法），所以每次循环的时间复杂度是 $ O(1) $。 因此，总的时间复杂度为：
\boxed{O(\min(n, m))}

比如 n = m = 1000），循环执行 1000 次，属于非常高效的算法！ --- ## 📈 四、空间复杂度分析 - 只使用了几个变量（n, m, sum, i, j），没有使用任何数组或递归。 - 所以空间复杂度为：\boxed{O(1)}。

代码：

#include<iostream>
using namespace std;

int main(){
    long long n, m;
    cin >> n >> m;
    long long sum = 0;

    if(n <= m){
        for(int i = n, j = m; i > 0; i--, j--){
            sum += i * j;
        }
    } else {
        for(int i = n, j = m; j > 0; i--, j--){
            sum += i * j;
        }
    }

    cout << sum;
    return 0;
}