P6463

WeLikeStudying · 2020-08-30 13:44:45 · 题解

前言：

题目的数据似乎被人为扩充到了 n,m≤350 。
以前好像数据很水，各种暴力都能卡过。
题面是n,m≤100是错的。
注意 n,m≤350 ，别被坑得RE。

题面简述

n×m 的方阵，得找一个金字塔那样的东西，第一圈是1，第二圈是2，...，有k次机会让某一个点的值提高1，求能够建成的最高的金字塔。
n,m≤350 ，提高次数 k≤10⁸，矩阵的数字都在0到50之间。

思路

判断一个方阵是否能够搭建金字塔，需要：

判断金字塔要多少次提高地面的机会，这点，两个矩阵相减即可。
判断提高地面是否一定能建成，即判断第一层是否小于等于1，第二层是否小于等于2，...以此类推，否则机会再多也无法建成。

下面是一些算法（以下所有的时间复杂度基于m,n规模相差不大的假设)。

1. O(n^5) 算法

分别枚举正方形的两个顶点，可以确定整个正方形。

2.另一个 O(n^5) 算法

可以枚举正方形的中心和半径， O(n^2) 验证。
这样的方式有个比较特别的性质：它的部分数据可以重复利用。可以利用这一点优化。

3. O(n^4) 算法

也是基于二的改进，我们仍然 O(n^2) 枚举中心。
在枚举半径时，许多数据可以重复使用，如判断矩阵合法性，我们可以一层一层地判断，举个例子：比如一圈的最大值为4，肯定至少还得拓展3层：4，3，2，1，我把它称作“前瞻性判断”。
```
int maxv=get_square_max(i,j,d);//找到了最大值。
mind=max(mind,d+maxv-1);//看看第几层才能判断。
```
至于矩阵的和，更简单了，每次扫一遍，加上去即可。
因此，平均每次判断矩阵合法性复杂度变成了 O(n^2) 。

其它与2无异。

4.另一个 O(n^4) 算法

还是基于2的改进，我们看一看能不能通过预处理，使得判断一个矩阵变快。

方阵数值的和

考虑差分。

它是可以O(n²)预处理，O(1)求出的。
设c[i+1][j+1]为1~i行，1~j列的数的和。
预处理可以先算行的前缀和，再算列的前缀和。
i~k行，j~l列的数的和就是c[k][l]-c[k][j-1]-c[i-1][l]+c[i-1][j-1]。

四边形边框的最大值

本质上是一个区间的最大值，求每行每列的可以 O(n^2\log_2{n}) 预处理 O(1) 求出。考虑 ST 表。

这里可以设a[i][j][k]为第i行j~j+2^k-1列中数的最大值，
b[i][j][k]为第j行i~i+2^k-1列中数的最大值。
那么显然：
a[i][j][k]=max(a[i][j][k-1],a[i][j+(1<<(k-1))][k-1])
b[i][j][k]=max(b[i][j][k-1],b[i+(1<<(k-1))][j][k-1])
至于判断，由于有重复不会影响max值正确性，直接把两个大区间拼在一起。
类似这样：
inline int get_row_max(int i,int j,int k)
{
    int len=k-j+1;
    len=log2[len];
    return max(a[i][j][len],a[i][k+1-(1<<len)][len]);
}

因此， O(n) 可以单纯判断一个矩阵是否合法。

和 2 的做法几乎一致，不再赘述。

5. O(n^3) 算法

基于 4 和 5 的改进，我们仍然 O(n^2) 枚举中心。
在枚举半径时，和4一样，许多数据还是可以重复使用，但这次，我们的优化使得矩阵合法性的复杂度降到了 O(1) 。
估算了一下， 5×350 ³ =214375000 。确实会 TLE，但加 O2 优化就没事了。也就是说，对于题面的 n , m ≤ 100 它是一个完全可接受的算法。
程序

#include<fstream>
using namespace std;
const int MAXN=350,MAXLOG=10;
int T,n,m,v[MAXN][MAXN],a[MAXN][MAXN][MAXLOG];
int b[MAXN][MAXN][MAXLOG],log2[MAXN];
long long maxcost,c[MAXN][MAXN];
inline void input()
{
    scanf("%d%d%lld",&n,&m,&maxcost);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        scanf("%d",&v[i][j]);
        a[i][j][0]=b[i][j][0]=c[i+1][j+1]=v[i][j];
    }
}
inline void prepare_sum()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    c[i][j]+=c[i-1][j];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    c[i][j]+=c[i][j-1];
}
inline void prepare_max()
{ 
    for(int k=1;k<=log2[n];k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        //The second mistake
        //if(i+(1<<(k-1)|1)>=n)
        if(i+(1<<(k-1))>=n)
        b[i][j][k]=b[i-1][j][k];
        else
        b[i][j][k]=
        //The first mistake
        //max(b[i][j][k-1],b[i+(1<<(k-1)|1)][j][k-1])
        max(b[i][j][k-1],b[i+(1<<(k-1))][j][k-1]);
    } 
    for(int k=1;k<=log2[m];k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        //The second mistake
        //if(j+(1<<(k-1)|1)>=n)
        //The third mistake
        //if(j+(1<<(k-1))>=n)
        if(j+(1<<(k-1))>=m)
        a[i][j][k]=a[i][j-1][k];
        else
        a[i][j][k]=
        //The first mistake
        //max(a[i][j][k-1],a[i][j+(1<<(k-1)|1)][k-1]);
        max(a[i][j][k-1],a[i][j+(1<<(k-1))][k-1]);
    }
}
inline long long get_sum(int i,int k,int j,int l)
{
    return c[k+1][l+1]-c[k+1][j]-c[i][l+1]+c[i][j];
}
inline int get_row_max(int i,int j,int k)
{
    int len=k-j+1;
    len=log2[len];
    return max(a[i][j][len],a[i][k+1-(1<<len)][len]);
}
inline int get_column_max(int j,int k,int i)
{
    int len=k-j+1;
    len=log2[len];
    return max(b[j][i][len],b[k+1-(1<<len)][i][len]);
}
inline int get_square_max(int x,int y,int d)
{
    return max(max(get_row_max(x-d,y-d,y+d),
    get_row_max(x+d,y-d,y+d)),
    max(get_column_max(x-d,x+d,y-d),
    get_column_max(x-d,x+d,y+d)));
}
inline bool ok(int x,int y,int d)
{
    return x-d>=0&&x+d<n&&y-d>=0&&y+d<m; 
}
inline void just_do_it()
{
    int ans=0;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        long long alsum=0;
        int mind=0;//最小的d 
        for(int d=0;ok(i,j,d);d++)
        {
            alsum+=(d<<1|1)*(d<<1|1);
            //需要检查： i±d (j-d,j+d)
            //j±d (i-d,i+d) 
            int maxv=get_square_max(i,j,d);//事实上是方框 
            //然后这个值说明了什么？
            //maxv(d)，maxv-1(d+1)，...，1(d+maxv-1)
            //说明……还有maxv-1歩才行
//          printf("(%d %d)*%d %d\n",i+1,j+1,d,maxv);
            long long sm=get_sum(i-d,i+d,j-d,j+d);
//          printf("(%d %d)*%d %lld %lld\n",i+1,j+1,d,
//          alsum,sm);
            mind=max(mind,d+maxv-1);
            if(mind<=d&&alsum-sm<=maxcost)
            ans=max(ans,d+1);
        }
    }
    printf("%d\n",ans);
}
inline void solve()
{
    input();
    prepare_sum();
    prepare_max();
/*  for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        printf("%3lld ",c[i][j]);
        printf("\n");
    }
    printf("%d\n",get_sum(1,2,1,3));
    printf("%d\n",get_row_max(1,1,4));*/
    just_do_it();
}
int main()
{
    scanf("%d",&T);
    for(int i=2;i<=MAXN;i++)
    log2[i]=log2[i-1]+!(i&(i-1));
    while(T--)
    solve(); 
    return 0;
}