POI2008 Plot purchase

POI
最大子矩形, 构造

POI2008 Plot purchase

题目大意:

给出一个$n \times n$的地图，每一个格子有一个价格，找一个矩形，使其价格总和位于$[k,2 \times k]$ 。

题解：

首先看一下$1 \times n$ 的情况，如果有一个格子价值在$[k,2 \times k]$ 之内，那么可以直接输出该点。

其次，若所有格子的和小于k，显然不满足。

接下来，只要没有一个数大于$2 \times k$ 则一定可以构造出可行解。

因为没有一个数大于等于$2 \times k$ ，而又没有一个格子价值在$[k,2 \times k]$ 之内，说明所有格子小于k。

而所有格子的和大于等于k，我们把前缀和写出来，总可以找到一个前缀的和在给定范围内。因为所有格子小于k，这意味着相邻两个前缀和相差并不会大于等于k，因而总可以有解。

因而对于$1 \times n$ 的情况，只要枚举每一个不含大于等于$2 \times k$的数的区间，并判定是否可行即可。

我们发现，这个方法是可以推广到二维矩形上的。

同样的，如果有一个格子价值在$[k,2 \times k]$ 之内，那么可以直接输出该点。

其次，若所有格子的和小于k，显然不满足。

接下来，只要没有一个数大于$2 \times k$ 则一定可以构造出可行解。

首先我们枚举每一行，若这一行的和大于等于k，说明可以在该行找到解。(也就是上面$1 \times n$ 的情况)

若没有找到解，说明每一行的和都小于k。

那么我们可以把这一层压成一个数字。(也就是说，要取就一整行地取)

这样，每一个被压缩的数字都小于k，但它们的和大于等于k，与上面同理，我们可知，一定可以构造出可行解。

综上，只要一个矩形和大于等于k，并且没有一个数大于$2\times k$，我们总可以构造出解。

那么，我们不妨把每一个大于等$2\times k$的数看做障碍。

那么，我们利用最大子矩形算法枚举每一个极大子矩形，看看是否满足即可。

综上，复杂度为$O(n^2)$。

PS. 关于最大子矩形，推荐一篇论文。

浅谈用极大化思想解决最大子矩形问题 —福州第三中学 王知昆

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void Rd(ll&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=2002;
int n,k;
ll sum[N][N],line[N];
ll calc(int x,int y){
	return sum[x][y]-sum[x-1][y]-sum[x][y-1]+sum[x-1][y-1];
}
void judge(int lx,int ly,int rx,int ry){//计算一个极大子矩形是否存在一个合法解 
	if(ly>ry)return;
	ll tot=sum[rx][ry]-sum[lx-1][ry]-sum[rx][ly-1]+sum[lx-1][ly-1];
	if(tot<k)return;//显然不可能 
	if(tot>=k&&tot<=2*k){//本身满足 
		printf("%d %d %d %d\n",ly,lx,ry,rx);
		exit(0);
	}
	for(int i=lx;i<=rx;i++){
		line[i]=sum[i][ry]-sum[i-1][ry]-sum[i][ly-1]+sum[i-1][ly-1];
		if(line[i]>=k){//可以在本行找到ans 
			ll cur_sum=0;
			for(int j=ly;j<=ry;j++){
				cur_sum+=calc(i,j);
				if(cur_sum>=k&&cur_sum<=k*2){
					printf("%d %d %d %d\n",ly,i,j,i);
					exit(0);
				}
			}
		}
	}
	//把每一行压成一个数字，竖下来在列中找 
	ll cur_sum=0;
	for(int i=lx;i<=rx;i++){
		cur_sum+=line[i];
		if(cur_sum>=k&&cur_sum<=k*2){
			printf("%d %d %d %d\n",ly,lx,ry,i);
			exit(0);
		}
	}
}
#define left kfsdkgfh
#define right ljlsdjgl
short height[N][N],left[N][N],right[N][N];
int main(){
	cin>>k>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			Rd(sum[i][j]);
			if(sum[i][j]>=k&&sum[i][j]<=k*2){
				printf("%d %d %d %d\n",j,i,j,i);
				return 0;
			}
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
		}
	}
	for(int i=1;i<=n;i++){//预处理 
		left[i][0]=0;
		for(int j=1;j<=n;j++){
			left[i][j]=left[i][j-1];
			if(calc(i,j)>2*k)left[i][j]=j;
		}
		right[i][n+1]=n+1;
		for(int j=n;j>=1;j--){
			right[i][j]=right[i][j+1];
			if(calc(i,j)>2*k)right[i][j]=j;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(calc(i,j)>2*k)continue;//有障碍 
			if(i==1||calc(i-1,j)>2*k){//上面一个点有障碍 
				height[i][j]=1;
			}else{//上面一个点没有障碍 
				height[i][j]=height[i-1][j]+1;
				left[i][j]=max(left[i-1][j],left[i][j]);
				right[i][j]=min(right[i-1][j],right[i][j]);
			}
			judge(i-height[i][j]+1,left[i][j]+1,i,right[i][j]-1);
		}
	}
	printf("NIE\n");
	return 0;
}
分享到 评论