P3474 [POI 2008] KUP-Plot purchase 题解

草。

扔掉所有

>2k

的格子之后，如果能在剩下的格子中找到一个权值和

\ge k

的矩形就有解。

证明：

如果存在一个格子权值在

[k,2k]

之间直接选取它即可。为了方便，我们认为剩下的所有格子权值在

[0,k)

之间。

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

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

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

CPP

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;
}

P3474 [POI 2008] KUP-Plot purchase 题解

文章操作

相关推荐

评论

P3474 [POI 2008] KUP-Plot purchase 题解