P2363题解

· · 题解

二维前缀和板子

首先我们根据题意来判断时间复杂度，先使用 O(n^2) 的时间去枚举两个矩阵的交点 (i,j)，然后使用 O(2 n^2) 的时间分别去枚举两个矩阵的终点（起点就是刚刚枚举的交点），总时间复杂度为 O(2n^4)，对于题目中的数据范围是可以实现的。

然后我们来处理前缀和，先来制作一个二维前缀和，原理如下图所示：

如果我们现在想要求出红色矩阵数字的总和，那么我们可以将大矩阵减去两个绿色矩阵。其中我们发现蓝色矩阵被绿色矩阵覆盖了两次，因此我们要把这个矩阵给补回来，因此我们得到前缀和的式子为：sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}，当然如果我们想要查询起点是 (x,y) 终点是 (i,j) 的矩阵，我们同理可以用 sum_{i,j}-sum_{i,y-1}-sum_{x-1,j}+sum_{x-1,y-1} 来表示它们的和，然后考虑到题目中的答案可能会有负数，因此我们可以使用哈希映射来处理结果，其中哈希在每次操作之后需要清空，否则会有情况重复计算。在此之后我们只需要在枚举交点的基础上，再次计算出 (x1,y1) 到 (i,j) 的矩阵和以及 (x2,y2) 到 (i,j) 的矩阵和，进行比较厚如果结果相同，即可行方案数增加，否则跳过。

Code

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(int i=j;i<=n;i++)
using namespace std;
ll n,ans;
ll a[55][55],sum[55][55];
map<ll,ll> mp;
int main(){
    cin>>n; 
    F(i,1,n) F(j,1,n){
        cin>>a[i][j];
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];//前缀和预处理
    } 
    F(i,1,n){
        F(j,1,n){
            F(x,1,i) F(y,1,j) mp[sum[i][j]-sum[i][y-1]-sum[x-1][j]+sum[x-1][y-1]]++;//查询第一个矩阵的可能情况和（左上角）
            F(x,i+1,n) F(y,j+1,n) ans+=mp[sum[x][y]-sum[x][j]-sum[i][y]+sum[i][j]];//查询第二个矩阵的可能情况和并加上其中的答案（右下角）
            mp.clear();//清空哈希
            F(x,1,i) F(y,j+1,n) mp[sum[i][y]-sum[x-1][y]-sum[i][j]+sum[x-1][j]]++;//查询第一个矩阵的可能情况和（左下角）
            F(x,i+1,n) F(y,1,j) ans+=mp[sum[x][j]-sum[i][j]-sum[x][y-1]+sum[i][y-1]];//查询第二个矩阵的可能情况和并加上其中的答案（右上角）
            mp.clear();//清空哈希
        }
    }
    cout<<ans;
    return 0;
}

End