P4705 棋盘问题（普及组）（基础）

解题思路

第一步：看懂题目。 一个 N×M 的棋盘，就像街道网格一样横竖交错。要数一数里面一共有多少个正方形、多少个长方形。注意：题目说的长方形不算正方形，正方形要单独数。

第二步：先数正方形——按边长分类。 边长为 1 的正方形：横着有 N 个位置、竖着有 M 个位置，一共 N×M 个。边长为 2 的正方形：要占 2 行 2 列，横着有 N-1 个位置、竖着有 M-1 个位置，一共 (N-1)×(M-1) 个。依此类推，边长为 s 的正方形有 (N-s+1)×(M-s+1) 个。把所有边长的情况加起来，就是正方形总数。

第三步：再数所有矩形——用“选线”的办法。 一个矩形由“选两条横线、选两条竖线”确定。横线一共有 N+1 条，从中选 2 条有 N×(N+1)/2 种选法；竖线一共有 M+1 条，从中选 2 条有 M×(M+1)/2 种选法。两者相乘，就是所有矩形（包含正方形）的总数。

第四步：长方形数 = 总矩形数 - 正方形数。 题目要的长方形是不含正方形的矩形，所以用总矩形数减去正方形数就可以了。

第五步：举个例子验证。 用 2×3 的棋盘：正方形有 6+2=8 个（边长 1 的有 2×3=6 个，边长 2 的有 1×2=2 个）；总矩形是 (2×3/2)×(3×4/2)=3×6=18 个；长方形是 18-8=10 个，和样例一致。

第六步：注意边界与数据大小。 N=1、M=1 时只有一个正方形、0 个长方形。N、M 最大到 100，N×(N+1)/2 可能达到几千，两个这样的数相乘会超过 int 的范围，所以要用 long long。

参考代码

// 棋盘问题：统计 N*M 棋盘中正方形和长方形(不含正方形)的个数
#include <iostream>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    long long squareCnt = 0;
    long long maxSide = n < m ? n : m; // 最大可能的正方形边长
    for (long long side = 1; side <= maxSide; side++) {
        // 边长为 side 的正方形有 (n-side+1)*(m-side+1) 个
        squareCnt += (n - side + 1) * (m - side + 1);
    }
    // 总矩形数 = 横线选 2 条 * 竖线选 2 条
    long long totalRect = (n * (n + 1) / 2) * (m * (m + 1) / 2);
    cout << squareCnt << " " << totalRect - squareCnt << endl;
    return 0;
}

复杂度分析

循环从边长 1 到 min(N,M)，时间复杂度 O(min(N,M))，对 100×100 的棋盘来说非常快。只用了几个变量，空间 O(1)。