P3474 [POI 2008] KUP-Plot purchase 题解

_fairytale_ · 2025-02-01 00:34:12 · 题解

草。

扔掉所有 >2k 的格子之后，如果能在剩下的格子中找到一个权值和 \ge k 的矩形就有解。

证明：

如果存在一个格子权值在 [k,2k] 之间直接选取它即可。为了方便，我们认为剩下的所有格子权值在 [0,k) 之间。

• 如果找到了这样的矩形，考察它的每一列：

  • 如果它的权值在 [k,2k] 之间，直接选取即可。
  • 如果它的权值 >2k，从上往下依次删掉这一列的格子，因为格子的权值 <k，所以必然存在一个时刻它的权值位于 [k,2k] 之间（因为不会从 >2k 突变到 <k）。
  • 所以我们只需考虑每一列权值 <k 的情况，直接把每一列当成一个格子，套用上一种情况的构造即可。

• 如果不存在这样的矩形，显然无解。

因为每个格子的权值是非负整数，所以直接找极大的子矩形即可。

单调栈 while 打成 if 调了一年。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>k>>n;
    auto ans=[&](int i1,int i2,int j1,int j2)->void{
        cout<<j1<<" "<<i1<<" "<<j2<<" "<<i2<<'\n';
        exit(0);
    };
    rep(i,1,n) {
        rep(j,1,n) {
            cin>>a[i][j];
            if(a[i][j]>k+k)a[i][j]=-inf;
            else if(a[i][j]>=k)ans(i,i,j,j);
        }
    }
    rep(i,1,n)rep(j,1,n)pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
    auto s=[&](int i1,int i2,int j1,int j2)->ll {
        return pre[i2][j2]-pre[i1-1][j2]-pre[i2][j1-1]+pre[i1-1][j1-1];
    };
    rep(i,1,n) {
        rep(j,1,n) {
            if(a[i][j]==-inf)h[j]=0;
            else ++h[j];
        }
        stac[top=0]=0;
        rep(j,1,n) {
            while(top&&h[j]<=h[stac[top]])--top;
            L[j]=stac[top]+1;
            stac[++top]=j;
        }
        stac[top=0]=n+1;
        per(j,n,1) {
            while(top&&h[j]<=h[stac[top]])--top;
            R[j]=stac[top]-1;
            stac[++top]=j;
        }
        rep(j,1,n) {
            if(s(i-h[j]+1,i,L[j],R[j])>=k) {
                for(int i1=i-h[j]+1,i2=i,j1=L[j],j2=R[j]; j1<=j2; --j2) {
                    if(s(i1,i2,j1,j2)<=k+k)ans(i1,i2,j1,j2);
                    if(s(i1,i2,j2,j2)>k+k){
                        for(;i1<=i2;++i1)if(s(i1,i2,j2,j2)<=k+k)ans(i1,i2,j2,j2);
                    }
                    if(s(i1,i2,j2,j2)>=k)ans(i1,i2,j2,j2);
                }
                assert(0);
            }
        }
    }
    cout<<"NIE\n";
    return 0;
}