A2. 数方格 题解 (C++)

---

题目分析

题目要求计算在一个 n × m 的矩形网格中，能够画出的所有不同大小和位置的正方形的数量。

例如在 4×6 的网格中，可以画出边长为 1、2、3、4 的正方形，每种边长又因摆放位置不同而有多种方案。

核心思路

这个问题有一个简洁的数学解法。对于一个 n × m 的网格（假设 n ≤ m）：

• 边长为 k 的正方形，在水平方向上可以有 (n - k + 1) 种不同的摆放位置
• 在垂直方向上可以有 (m - k + 1) 种不同的摆放位置
• 所以边长为 k 的正方形总数为 (n - k + 1) × (m - k + 1)

因为正方形边长 k 最大不能超过 min(n, m)，所以总方案数为：

[
\text{总方案数} = \sum_{k=1}^ { \min(n, m) } (n - k + 1) \times (m - k + 1)
] ^[1]

时间复杂度

直接按照公式计算，时间复杂度为 O(min(n, m))，对于 n, m ≤ 1000 的数据范围完全足够。

---

代码实现（all AC，可放心食用）

#include <cstdio>
#include <algorithm>

int main() {
    int n, m;
    scanf("%d%d",&n,&m);
    
    long long ans = 0;  // 使用 long long 防止整数溢出
    int minSide = std::min(n, m);//上面懒得打std了...
    
    for (int k = 1; k <= minSide; k++) {
        ans += (long long)(n - k + 1) * (m - k + 1);
    }
    
    printf("%lld",ans);
    return 0;//不忘好习惯，歇菜
}

代码解释

1. 输入处理：读取矩形的长 n 和宽 m
2. 确定循环范围：正方形边长 k 从 1 到 min(n, m)
3. 累加计算：对于每个边长 k，计算可能的摆放位置数并累加
4. 输出结果：输出总方案数

示例验证

以题目中的例子 1 5 为例：

• n = 1, m = 5, minSide = 1
• 只有边长 k = 1 的正方形
• 方案数 = (1-1+1) × (5-1+1) = 1 × 5 = 5
• 输出 5，与题目示例一致

优化思考

如果需要进一步优化（虽然本题不需要），公式可以转化为：
[
\text{总方案数} = \sum_{k=1}^{\min(n, m)} (n-k+1)(m-k+1) = \frac{\min(n,m)[\min(n,m)+1][2\min(n,m)+1]}{6} + \cdots
]^[1:1]
但直接循环计算更直观易懂。

---

总结

这道题的关键是发现正方形数量与边长和位置的关系，通过简单的数学推导即可得到高效的解决方案。

蒜鸟蒜鸟，睡了

---

1. 因为markdown原因我的公式不知道为什么被吃了... ↩︎ ↩︎