【NOIP1997】【Luogu1548】棋盘问题（枚举正方形个数）

problem

• 给定一个N*M的棋盘
• 求子正方形和长方形个数
• n,m<100

solution

乍一看毫无思路
看了题解基本都是找规律推公式（不过如果是考场的话我觉得我应该做不到吧QwQ，平时嘛，，就更做不到了。。
数据范围才100，一副爱咋搞咋搞的样子（暴力枚举）
——
怎样确定一个长方形？两个顶点呗。。。
那就枚举两个顶点，四场循环，复杂度 O(n2m2) O ( n 2 m 2 ) 。

codes

#include<iostream>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    int zheng = 0, chang = 0;
    //两个顶点确定一个长(正)方形,坐标从0开始枚举啊
    for(int i = 0; i <= n; i++){//左上角(i,j)
        for(int j = 0; j <= m; j++){
            for(int k = i+1; k <= n; k++){//右下角(k,l)
                for(int l = j+1; l <= m; l++){
                    if(k-i == l-j)zheng++;
                    else chang++;
                }
            }
        }
    }
    cout<<zheng<<' '<<chang<<'\n';
    return 0;
}

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81175550