B4222 [常州市赛 2023] 积木题解

· · 题解

B4222 [常州市赛 2023] 积木 题解

看到题解区均为二位前缀和的做法，这里提供二维 ST 表做法。

思路

首先肯定考虑二分。问题转化为求是否存在范围为 mid\times mid 的矩形满足矩形内每一个元素值均大于 mid。

注意到这里是判断区间最小值是否大于定值，考虑使用二维 ST 表维护，注意不同于一维，二维的判断需四个值进行维护。

最后输出的值为取走的方块数，所以应输出 sum - ans^3。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e3+5;
int n,m,sum;
int lg[maxn];
int st[25][maxn][maxn];
int minm(int x,int y,int aa,int bb)
{
    int res=min(aa,bb);
    res=min(res,y);
    res=min(res,x);
    return res;
}
int calc(int x,int y,int len)
{
    int sz=lg[len];
    return minm(st[sz][x][y],st[sz][x+len-(1<<sz)][y],st[sz][x][y+len-(1<<sz)],st[sz][x+len-(1<<sz)][y+len-(1<<sz)]);
}
bool check(int x)
{
    for(int i=1;i<=n-x;i++)
    {
        for(int j=1;j<=m-x;j++)
        {
            if(calc(i,j,x)>=x)
            {
                return 1;
            }
        }
    }
    return 0;
}
signed main()
{
    cin>>n>>m;
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>st[0][i][j];
            sum+=st[0][i][j];           
        }
    }
    int mx=lg[min(n,m)];
    for(int k=1;k<=mx;k++)
    {
        for(int i=1;i+(1<<k)-1<=n;i++)
        {
            for(int j=1;j+(1<<k)-1<=m;j++)
            {
                st[k][i][j]=minm(st[k-1][i][j],st[k-1][i+(1<<k-1)][j],st[k-1][i][j+(1<<k-1)],st[k-1][i+(1<<k-1)][j+(1<<k-1)]);
            }               
        }
    }
    int l=1,r=min(n,m);
    int ans=1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }   
    cout<<sum-ans*ans*ans;
    return 0;
}