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

· · 题解

啦啦啦，经过在谷一年的潜伏，我终于想开始发题解啦！（各位管理员大大一定要对我这个蒟蒻宽容点呀！）

言归正传，对于一道水题，N和M很小，我们完全可以不计后果的枚举（这是假的），但我们还是要努力去找正解。再看下题呗

1.题意分析

这道题的题意很简单，就是给你一个长方形，求出长方形里有多少个小长方形和正方形（长方形中不包括正方形）。就是这么简单，我也不啰嗦了。下面给出图（几何画板做的）。

2.解法

解法也不难，运用小学时代的公式（设长为n，宽为m）：

(1+2+3+...+n)(1+2+3+...+m)

或

即可算出长方形个数。下面给出证明（请看上图）： 在$AD$中，单位长度为$1$的有两个，$AJ,JD$。单位长度为$2$的有一个，$AD$。同理,$AB$中单位长度为$1$的有三个，单位长度为$2$的有两个，单位长度为$3$的有一个。（或者用一点到其它点有几个也是一样的，不阐述） 可能一些初学公式的小学生要问了（没得罪人吧），这些求出来有何用呢？答案显而易见，没一种情况对应着邻边的所有情况。比如$AJ$对应$AE,EF,FB,AF,EB,AB$就是$AB$中的所有情况呀！这样就可以推导出上方的两个公式。 那正方形怎么求呢？其实，正方形就是上方公式的特殊情况，即单位长度相等的情况。可以有公式 $nm+(n-1)(m-1)+...min(n,m)

仔细品一下，好像没错吧？（应该还能推，但太麻烦了，实际应用不大）所以开始愉快地打代码吧！

代码区（勿抄）

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans=0,bns=0,l[10005],r[10005],k=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) l[n-i+1]=i，ans+=i;//计算长方形和边个数。
    for(int i=1;i<=m;i++) r[m-i+1]=i，bns+=i;
    for(int i=1;i<=min(n,m);i++) k+=l[i]*r[i];
    cout<<k<<" "<<ans*bns-k<<endl;
}

本来还有更好的打法，可以将时间复杂度降到O(min(n,m))，但不知为何爆40，下面贴上代码。（已修复）

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,bns,k=0,r,l;
int main(){
    cin>>n>>m;
    ans=n*(n+1)/2,bns=m*(m+1)/2;
    r=min(n,m),l=max(n,m);
    for(int i=1;i<=r;i++) k=k+i*(i-r+l);
    cout<<k<<" "<<ans*bns-k<<endl;
}

如果有公式改良版也可以私信我（放评论区），我会把您们的想法放到题解或我的博客中（如果此题无法改题解了）。

声明：这是本蒟蒻自己推的公式，如有雷同，纯属巧合，管理员大大们不要以为我作弊哟。

再说一遍：管理员大大们最好了！希望我可以看到我的题解在洛谷中公开。（一个小蒟蒻的小小小愿望）