题解 P2241 【统计方形（数据加强版）】

· · 题解

对于这道题，我们先考虑第一个问题

一、算正方形的个数

1.如果我们固定了正方形的右下角(i,j),你能不能算出此时可能的正方形的个数？

2.显然，此时答案为Min(i,j).

3.所以可以枚举右下角，计算此时答案，求和即可。

二、算长方形个数

1.其实算长方形并不常见，但算矩形大家应该经常遇到，所以如果你会算矩形，再联系第一个问题，那答案就转化为 矩形个数-正方形个数.

2.像求解正方形个数一样，固定矩形右下角(i,j),显然此时矩形个数为i*j.

3.同理，求和即可.

时间复杂度：O(n*m)，是挺慢的，其实可以写成一个式子

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main()
{
    ll n,m,i,j,sum=0,sum1=0;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
      for(j=1;j<=m;j++)
      {
        sum+=min(i,j);
        sum1+=i*j;
      }
    }

    cout<<sum<<" "<<sum1-sum<<endl;
    return 0;
}