自动搬运

查看原文

来自洛谷，原作者为

	_xbn 今天这个地区是晴天，昨天我一整天都很享受

搬运于2025-08-24 22:21:42，当前版本为作者最后更新于2021-05-06 21:05:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于矩阵问题，我们先对其做一遍二维前缀和。

  for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]+=f[i][j-1];
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            f[i][j]+=f[i-1][j];

接下来考虑和相等的矩阵，由于数的值域较小，所以我们可以用一个桶来记录每一种和出现的次数。

接着我们考虑怎么找到两个满足条件的矩形。

我们可以枚举其中一个较为靠左的矩形的右下角坐标，因为另一个只和他有一个公共点，所以可以直接找到。然后在桶中检查一下值出现的次数，记录到答案中。

最后提醒大家两个易错点：每一次枚举完一定要把桶清空。由于数组下标可能为负数，所以要加上一个数组边界数。

核心代码：

  for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=n;j++)
		{
            for(int a=1;a<i;a++)
                for(int b=1;b<j;b++)
                    cnt[cal(a,b,i-1,j-1)+c]++;
            for(int a=i;a<=n;a++)
                for(int b=j;b<=n;b++)
                    ans+=cnt[cal(i,j,a,b)+c];
            for(int a=1;a<i;a++)
                for(int b=1;b<j;b++)
                    cnt[cal(a,b,i-1,j-1)+c]--;
            for(int a=i;a<=n;a++)
                for(int b=1;b<j;b++)
                    cnt[cal(i,b,a,j-1)+c]++;
            for(int a=1;a<i;a++)
                for(int b=j;b<=n;b++)
                    ans+=cnt[cal(a,j,i-1,b)+c];
            for(int a=i;a<=n;a++)
                for(int b=1;b<j;b++)
                    cnt[cal(i,b,a,j-1)+c]--;
        }
    }