P6537 [COCI2013-2014#1] RATAR

· · 题解

这难道不应该是橙题吗？然而我又调了半小时。。

首先想到用二维前缀和维护矩阵的和，那只用枚举矩形的顶点好了。

考虑如果枚举四个顶点（其中两点重合），复杂度至少为 \operatorname{O}(n^6)，基本是过不了。

那可以预处理掉一个顶点，复杂度为 \operatorname{O}(n^4)，是可以通过的。

具体如何预处理呢？

我们枚举第一个顶点后，接着枚举第二个，然后用 map 记录每个矩阵和出现的个数。

然后枚举与他相对的矩形时，直接加上这个矩阵和的次数好了。

为了避免重复，第二个矩阵只用枚举四个方向中的不相对的两个方向即可。

结合代码理解吧，多少有点细节。

#include<bits/stdc++.h>
using namespace std;
const int maxn=52;
int n,ans,qzh[maxn][maxn];
unordered_map<int,int> mp;
inline int sum(int lx,int ly,int rx,int ry){
    return qzh[rx][ry]-qzh[rx][ly-1]-qzh[lx-1][ry]+qzh[lx-1][ly-1];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&qzh[i][j]);
            qzh[i][j]+=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            mp.clear();
            for(int ii=i;ii<=n;ii++)
                for(int jj=j;jj<=n;jj++)
                    mp[sum(i,j,ii,jj)]++;
            for(int ii=1;ii<=i-1;ii++)
                for(int jj=1;jj<=j-1;jj++)
                    ans+=mp[sum(ii,jj,i-1,j-1)];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            mp.clear();
            for(int ii=i;ii<=n;ii++)
                for(int jj=1;jj<=j;jj++)
                    mp[sum(i,jj,ii,j)]++;
            for(int ii=1;ii<=i-1;ii++)
                for(int jj=j+1;jj<=n;jj++)
                    ans+=mp[sum(ii,j+1,i-1,jj)];
        }
    printf("%d",ans);
    return 0;
}