P7410

szzzzs · 2021-04-24 22:19:47 · 题解

题目传送门

芜湖~

起飞~

Subtask 1-4

设 A,B 两点，一个作为矩阵左上角的点，一个作为右下角的点，这样就可以确定一个矩阵区间。

接下来直接枚举其中的点判断此举这是否合法即可。

for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
    if(a[i][j]<100) continue;
    for(int ii=i; ii<=n; ii++)
    for(int jj=j; jj<=n; jj++)
    {
        pan1=0,pan2=0;
        for(int l=i; l<=ii; l++)
        {
            if(pan2) break;
            for(int r=j; r<=jj; r++)
            {
                if(a[l][r]==100) pan1=1;
                if(a[l][r]<100) pan2=1;
                if(pan2==1) break;
            }
        }
        if(pan1&&!pan2) ans++;
}

Subtask1-8

首先将所有绿度值大于等于 100 的格子看做可以形成矩阵的格子求出矩阵个数。然后将绿度值等于 100 的格子删除后再次求出格子数再次求出矩阵个数。前者减去后者就是答案。

那么怎么求出由多个小正方向形组成的不规则图形的子矩阵个数便是我们当前要解决的问题了。

具体思路如下：

首先把上面数据转化位由 0,1 组成的矩阵，样例转化出来后如下：

0 1 0
1 1 1
0 1 1

我们可以从 （1,1） 开始枚举到 （n，n）. 因此我们只需要算一下当前的点与右下形成的矩阵个数即可（因为与左上方的小正方形形成的矩阵在先前应已被判断）。

怎么处理与右下方小正方形形成的矩阵数呢?

我的方法比较 LJ 只是简单的枚举。

从左向右枚举，直到没有 1 的时候暂停，记录当前宽度的最小值（因为如果此列超过了上面长度的最小值组成的就不是矩阵了），然后在从上到下枚举，看一看能不能枚举到下一行（当然是从最左边向下枚举）。

就这样一个一个枚答案就出来。

Code

void dt(int xx,int yy,int maxx)
{
    int maxn;
    if(!a[xx][yy]) return;
    for(int i=yy;i<=maxx;i++)
    if(!a[xx][i])break;
    else ans++,maxn=i;
    dt(xx+1,yy,maxn);
}
int main()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)   dt(i,j,n);
    swap(ans,ans2);
    for(int i=1;i<=num;i++)
    a[la[i].x][la[i].y]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)   dt(i,j,n);
    cout<<ans2-ans<<endl;
    return 0;
}

Subtask 1-10

上面的代码复杂度应该是O_{n^4}。听说 O_{n^3} 的复杂度就可以过所以我将数据先处理了一下。简单说就是将一个数下面连续接了几个1处理了出来拿样例举个栗子。

030
122
011

这时只需要从左向右枚举一排只可，不再需要向下枚举列了。但是要保证每次想右枚举时，本列列长不能大于最小列长。

Code

#include<iostream>
#include<cstdio>
#define N 510
using namespace std;
int a[N][N]；                    //处理之前
int n,num
int val[N][N];//处理后的数组
long long ans2,ans;;
struct bala{int x,y;} la[N*N];          //存储等于100的点
void dt(int xx,int yy)              //枚举当前点可形成的矩阵数
{
    int minn=val[xx][yy];           //minn是最小列长
    for(int i=yy;i<=n;i++)
        if(!a[xx][i]) break;
        else {
            minn=min(minn,val[xx][i]);
            ans+=minn;
        }
}
void prt()                  //预处理
{
    for(int j=1;j<=n;j++)
        for(int i=n;i>=1;i--) {
            val[i][j]=0;        //因为用了两遍所以在这里需要清空
            if(a[i][j]) val[i][j]=val[i+1][j]+1;
        }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        scanf("%d",&a[i][j]);
        if(a[i][j]==100)
        la[++num].x=i,la[num].y=j;
        if(a[i][j]>=100) a[i][j]=1;
        else a[i][j]=0;
    }
    prt();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)   dt(i,j,n);
    swap(ans2,ans);
    for(int i=1;i<=num;i++)
        a[la[i].x][la[i].y]=0;
    prt();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)   dt(i,j,n);
    cout<<ans2-ans<<endl;
    return 0;
}

来到你谷的第一篇题解，望过！

码风较丑勿喷