统计方形(NOIP1997)

给链接：统计方形

这题是棋盘问题的数据加强版。

其实由于洛谷的数据比较水，所以你把我在棋盘问题题解中写的代码提交，也能AC。

但让给我们来看一个更优的解法。

先给代码：

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    long long sum1=0;

    for(int i=1;i<=min(n,m);i++){

        sum1+=(n-i+1)*(m-i+1);

    }

    printf("%lld ",sum1);

    long long sum2=1LL*n*(n+1)/2*1LL*m*(m+1)/2;//1

    printf("%lld",sum2-sum1);

    return 0;

}

其他地方没啥变化，参考我的那篇题解，这里我们只讲讲标1的这个式子，为什么这么写？

我们原来的循环是什么样的？

for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            sum2+=(n-i+1)*(m-j+1);

        }

    }

其实这个式子写出来，也就是sum2=1*1+1*2+……+2*1+2*2+……+n*1+n*2+……+n*m，所以也就是：

sum2=(1+2+3+……+n)*(1+2+3+……+m)

利用等差数列求和公式就可得到：

sum2=(1+n)*n/2*(1+m)*m/2

注意最后还要乘1LL，防止爆int。

巴特西

统计方形(NOIP1997)

最新文章

热门文章