Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge
Submit: 485 Solved: 174
[Submit][Status][Discuss]
Description
给一个n*n的地图，每个格子有一个价格，找一个矩形区域，使其价格总和位于[k,2k]
Input
输入k n（n<2000)和一个n*n的地图
Output
输出矩形的左上和右下的列-行坐标或NIE
Sample Input
inputdata1
4 3
1 1 1
1 9 1
1 1 1
inputdata2
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2
4 3
1 1 1
1 9 1
1 1 1
inputdata2
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2
Sample Output
outputdata1
NIE
outputdata2
2 1 4 2
NIE
outputdata2
2 1 4 2
HINT
1<=k<=10^9 每个价格都是不大于2*10^9的非负整数
Source
首先可以特判是否有单个元素满足条件,如果没有就说明元素都是<k或>2k的
>2k的肯定不能选,对于<k的元素,我们将其染色为1 >2k染色为0
现在要做的就是找到颜色全为1的极大子矩阵,判断它其中是否有满足条件的矩阵
如果一个矩阵>=k那么它一定会有一个子矩阵满足条件,可以证明：
如果整个矩阵和<=2k直接输出,剩下的情况都是矩阵和>2k,一直缩小矩阵直到矩阵和<=2k
假设去掉第一行后,矩阵权值和>=k ,去掉第一行继续处理矩阵
假设去掉第一行后,矩阵权值和<k 那么由于矩阵和>2k,第一行肯定是>k的,直接处理第一行
当只有一行时还>2k直接缩减元素
代码调不出来了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 2005
#define ll long long
using namespace std;
int n,m,l[N][N],a[N][N],r[N][N],h[N][N];ll sum[N][N];
ll calc(int x1,int y1,int x2,int y2)
{return sum[x2][y2]+sum[x1-][y1-]-sum[x1-][y2]-sum[x2][y1-];}
void print(int x1,int y1,int x2,int y2){
if(calc(x1,y1,x2,y2)>*m){
if(x1==x2)y2--;
else if(calc(x1+,y1,x2,y2)>=m)x1++;
else x2--;
}
printf("%d %d %d %d\n",y1,x1,y2,x2);
exit();
} int main(){
//freopen("/home/noilinux/Desktop/data.in","r",stdin);
//freopen("/home/noilinux/Desktop/wa.out","w",stdout);
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
scanf("%d",&a[i][j]);
sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+a[i][j];
if(a[i][j]>=m&&a[i][j]<=m*){
printf("%d %d %d %d\n",j,i,j,i);
return ;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(a[i][j]<m)l[i][j]=l[i][j-]+;
else l[i][j]=;
for(int i=;i<=n;i++)
for(int j=n;j>=;j--)
if(a[i][j]<m)r[i][j]=r[i][j+]+;
else r[i][j]=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(a[i][j]<m)h[i][j]=h[i-][j]+;
else h[i][j]=; for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(a[i][j]>*m)continue;
if(h[i][j]>){
l[i][j]=min(l[i-][j],l[i][j]);
r[i][j]=min(r[i-][j],r[i][j]);
}
int x1=i-h[i][j]+,x2=i;
int y1=j-l[i][j]+,y2=j+r[i][j]-;
if(calc(x1,y1,x2,y2)>=m)print(x1,y1,x2,y2);
}
puts("NIE");
}