加载中...
题解 P6537 【[COCI2013-2014#1] RATAR】

前言:

这道题想了好久啊,花了我一个晚上的时间,题目有点坑,但是不难(

正文

思路:

前缀和预处理每个点与左上角形成的矩阵的元素和,然后枚举对顶点,枚举左上-右下,左下-右上符合条件的矩阵(小小地用一下容斥原理),记录个数。

$O(N^4)$暴力枚举就能过。

一个小细节:当你在一个频繁调用的函数或循环里使用了memset时,请三思。memset复杂度为$O(N)$,可能会导致TLE。在本题中,可以使用几个临时数组来记录待改变的值,赋值后再改回$0$,复杂度为$O(2500)$,可有效避免超时。

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mp[55][55],sum[55][55],pre[55][55];
int tmp[5000005],ans,n,ding[2505];
int get(int x,int y,int x2,int y2)
{
    return sum[x2][y2]-sum[x2][y-1]-sum[x-1][y2]+sum[x-1][y-1];
}
int main()
{
    //freopen("ratar.in","r",stdin);
    //freopen("ratar.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) cin>>mp[i][j];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) pre[i][j]=pre[i][j-1]+mp[i][j];
    for(int j=1;j<=n;j++)
    for(int i=1;i<=n;i++) sum[i][j]=sum[i-1][j]+pre[i][j];
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            int f,cnt=0;
            for(int ii=1;ii<=i;ii++)
            for(int jj=1;jj<=j;jj++)
            {
                f=get(ii,jj,i,j)+2500000;
                tmp[f]++;
                ding[++cnt]=f;
            }
            for(int ii=i+1;ii<=n;ii++)
            for(int jj=j+1;jj<=n;jj++) ans+=tmp[get(i+1,j+1,ii,jj)+2500000];
            for(int ii=1;ii<=cnt;ii++) tmp[ding[ii]]=0;
            cnt=0;
            for(int ii=i+1;ii<=n;ii++)
            for(int jj=1;jj<=j;jj++)
            {
                f=get(i+1,jj,ii,j)+2500000;
                tmp[f]++;
                ding[++cnt]=f;
            }
            for(int ii=1;ii<=i;ii++)
            for(int jj=j+1;jj<=n;jj++) ans+=tmp[get(ii,j+1,i,jj)+2500000];
            for(int ii=1;ii<=cnt;ii++) tmp[ding[ii]]=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

后记

求点赞和评论QAQ


  目录
劳动
快乐