P6537 [COCI2013-2014#1] RATAR

_xbn · 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]--;
        }
    }