题解 P2363 【马农】

zengxr · 2019-02-18 15:13:31 · 题解

二维矩阵和

题目无非两种情况，一种就是一块地在右上，一块地在左下。或者是一种在左上，一种在右下。

思路：

用暴力去枚举相交的点，设为A，在枚举上面格子的顶点B 枚举下面格子的顶点C，再去判断符不符合题意就行了。

（注意有两种情况，都要枚举）

#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}//快读
int n;
int ans;
int f[2010][2010],a[2010][2010],d[11111111];
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            read(a[i][j]);
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int x=1;x<=i;x++)
            for(int y=1;y<=j;y++)
            d[f[i][j]-f[i][y-1]-f[x-1][j]+f[x-1][y-1]]++;
            for(int x=i+1;x<=n;x++)
            for(int y=j+1;y<=n;y++)
            ans=ans+d[f[x][y]-f[x][j]-f[i][y]+f[i][j]];//枚举，统计答案
            for(int x=1;x<=i;x++)
            for(int y=1;y<=j;y++)
            d[f[i][j]-f[i][y-1]-f[x-1][j]+f[x-1][y-1]]=0;//做完一种情况后一定要清空数组
            for(int x=1;x<=i;x++)
            for(int y=j+1;y<=n;y++)
            d[f[i][y]-f[x-1][y]-f[i][j]+f[x-1][j]]++;
            for(int x=i+1;x<=n;x++)
            for(int y=1;y<=j;y++)
            ans=ans+=d[f[x][j]-f[i][j]-f[x][y-1]+f[i][y-1]];//枚举，统计答案
            for(int x=1;x<=i;x++)
            for(int y=j+1;y<=n;y++)
            d[f[i][y]-f[x-1][y]-f[i][j]+f[x-1][j]]=0;//清空

        }
    }
    printf("%d",ans);//输出答案
    return 0;
}