1127: [POI2008]KUP
Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge
Submit: 317 Solved: 111
[Submit][Status][Discuss]
Description
给一个n*n的地图，每个格子有一个价格，找一个矩形区域，使其价格总和位于[k,2k]
Input
输入k n（n<2000)和一个n*n的地图
Output
输出矩形的左上和右下的列-行坐标或NIE
Sample Input
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
NIE
outputdata2
2 1 4 2
HINT
1<=k<=10^9 每个价格都是不大于2*10^9的非负整数
Source
Solution
这个题需要思路....
首先假设有一个一维的区间$[l,r]$，那么假设这个区间中满足$\forall x,x<K$，那么且这个区间的和$>=K$，那么答案肯定存在在这个区间中。
证明：
因为这个区间中满足$\forall x,x<K$，所以区间和每加上一个数，区间和的变化量一定是$<K$的;
所以，并不会存在一个数使得一个子区间（连续的）和加上他得到的新区间和直接从$(-\infty,K]$跳过$[K,2*K]$变成$[2*K,+\infty)$.
所以，只要从这个一维的区间的左/右端开始一一删除，就可以得到满足条件的区间。
但是这里的$N*N$的矩阵，所以要利用这个结论就必须扩展到多维区间块上面，但是这个结论是可以拓展的。
这样就是一个子矩阵满足$\forall x,x<K$，且子矩阵和$>=K$，那么这个子矩阵中存在答案。
证明类比上面的证明，这里分类讨论一下，可以利用上面的方法，先一行一行的删除，删成满足条件的，或者只剩一行，转成上述，再一个一个删.
然后就是找出这些需要搞得子矩形的方法了,把$x>2*K$的点认为是障碍，做一遍悬线法，就可以得到所有的极大子矩形，然后一一判断。
当然一开始读入的时候，如果存在一个$1*1$的位置$x$直接满足$x \in [K,2*K]$那么可以直接输出。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
int K,N,l[][],r[][],h[][];
LL sum[][],a[][];
inline LL Sum(int x1,int y1,int x2,int y2) {return sum[x2][y2]+sum[x1-][y1-]-sum[x2][y1-]-sum[x1-][y2];}
inline void Cut(int x1,int y1,int x2,int y2)
{
while (Sum(x1,y1,x2,y2)>*K)
{
if (x1==x2) {y2--; continue;}
if (Sum(x1,y1,x2-,y2)>=K) {x2--; continue;}
if (Sum(x1+,y1,x2,y2)>=K) {x1++; continue;}
}
printf("%d %d %d %d\n",y1,x1,y2,x2);
exit();
}
int main()
{
K=read(),N=read();
for (int i=; i<=N; i++)
for (int j=; j<=N; j++)
a[i][j]=read(),sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+a[i][j];
for (int i=; i<=N; i++)
for (int j=; j<=N; j++)
if (a[i][j]>=K && a[i][j]<=*K) {printf("%d %d %d %d\n",j,i,j,i); return ;}
for (int i=; i<=N; i++)
{
for (int j=,x=; j<=N; j++)
if (a[i][j]<=*K) l[i][j]=x; else l[i][j]=,x=j;
for (int j=N,x=N+; j>=; j--)
if (a[i][j]<=*K) r[i][j]=x; else r[i][j]=N+,x=j;
}
for (int i=; i<=N+; i++) r[][i]=N+;
for (int i=; i<=N; i++)
for (int j=; j<=N; j++)
if (a[i][j]<=*K)
h[i][j]=h[i-][j]+,
l[i][j]=max(l[i][j]+,l[i-][j]),
r[i][j]=min(r[i][j]-,r[i-][j]); // puts("==========================");
// for (int i=1; i<=N; i++,puts(""))
// for (int j=1; j<=N; j++)
// printf("%d ",h[i][j]);
// puts("==========================");
// for (int i=1; i<=N; i++,puts(""))
// for (int j=1; j<=N; j++)
// printf("%d ",l[i][j]);
// puts("==========================");
// for (int i=1; i<=N; i++,puts(""))
// for (int j=1; j<=N; j++)
// printf("%d ",r[i][j]);
// puts("=========================="); for (int i=; i<=N; i++)
for (int j=; j<=N; j++)
if (a[i][j]<=*K){
// printf("%d %d %d %d\n",i-h[i][j]+1,l[i][j],i,r[i][j]);
if (Sum(i-h[i][j]+,l[i][j],i,r[i][j])>=K) Cut(i-h[i][j]+,l[i][j],i,r[i][j]);
}
puts("NIE");
return ;
}
/*
2 3
3 25 7
6 1 2
16 11 20
*/