首先显然地，如果某个格子的权值超过2k，其一定不在答案之中；如果在[k,2k]中，其自身就可以作为答案。那么现在我们只需要考虑所选权值都小于k的情况。
可以发现一个结论：若存在一个权值都小于k的矩阵其权值和>=k，那么该矩阵一定存在权值和在[k,2k]中的子矩阵。
找到该子矩阵的过程和证明的过程是一样的：若其权值和已经在[k,2k]内，直接选择该矩阵即可；否则考虑从该矩阵中去掉一行（或一列）。如果矩阵剩下的部分权值和：
(1)在[0,k)内，对去掉的该行（或列）继续执行该操作
(2)在[k,2k]内，已找到答案
(3)在(2k,+∞)内，对剩下的矩阵继续执行该操作
由于矩阵中每一个权值都小于k，权值和不可能从>2k直接跳到<k，最终一定能找到合法矩阵。
于是只需要找到一个>=k的矩阵。悬线法即可。即先计算出每个位置向上向左向右最远能拓展到哪，然后根据其上方的点递推计算该悬线向左右拓展的最远位置。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 2010 int n,k,low,high,a[N][N],l[N][N],r[N][N],up[N][N]; int L,R,U,D; long long s[N][N]; long long sum(int l,int r,int u,int d) { return s[d][r]-s[d][l-1]-s[u-1][r]+s[u-1][l-1]; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj1127.in","r",stdin); freopen("bzoj1127.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif k=read(),n=read(); low=k,high=k<<1; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]=read()); if (a[i][j]>=low&&a[i][j]<=high) {cout<<j<<‘ ‘<<i<<‘ ‘<<j<<‘ ‘<<i;return 0;} } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) if (a[i][j]<low) up[i][j]=up[i-1][j]+1,l[i][j]=l[i][j-1]+1; for (int j=n;j>=1;j--) if (a[i][j]<low) r[i][j]=r[i][j+1]+1; for (int j=1;j<=n;j++) if (up[i][j]>1) l[i][j]=min(l[i][j],l[i-1][j]); for (int j=n;j>=1;j--) if (up[i][j]>1) r[i][j]=min(r[i][j],r[i-1][j]); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]<low&&sum(j-l[i][j]+1,j+r[i][j]-1,i-up[i][j]+1,i)>=low) { L=j-l[i][j]+1,R=j+r[i][j]-1,U=i-up[i][j]+1,D=i; break; } if (!L) cout<<"NIE"; else { while (sum(L,R,U,D)>high) { if (D>U) { if (sum(L,R,U,D-1)<low) U=D; else D--; } else R--; } cout<<L<<‘ ‘<<U<<‘ ‘<<R<<‘ ‘<<D; } return 0; }
原文：https://www.cnblogs.com/Gloid/p/9501829.html