简要题意：
给你一个n * n的非负矩阵，求问是否有子矩阵满足和在[k, 2k]之间。若有输出方案。n<=2000。
解：
首先n4暴力很好想(废话)，然后发现可以优化成n3log2n，但是还是过不了.....
正解十分之玄妙.....
首先所有大于2k的都不可用。
然后若有一个子矩阵的和不小于k，那么一定有解，且解是这个矩阵的一个子矩阵。
证：
当这个矩阵的和大于2k时，切这个矩阵。
一定有一块大于k。
然后就这样了......
具体实现就看代码了。
#include <cstdio>
#include <algorithm> typedef long long LL;
const int N = ;
const LL INF = (1ll << ) - ; LL G[N][N], sum[N][N];
int h[N][N], l[N], r[N], p[N], top; inline LL getsum(int left, int right, int u, int d) {
return sum[d][right] - sum[d][left - ] - sum[u - ][right] + sum[u - ][left - ];
} int main() { int n, m;
LL k;
scanf("%lld%d", &k, &n);
m = n;
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
scanf("%lld", &G[i][j]);
sum[i][j] = sum[i][j - ] + sum[i - ][j] - sum[i - ][j - ] + G[i][j];
}
} for(int j = ; j <= m; j++) {
for(int i = ; i <= n; i++) {
if(G[i][j] > (k << )) {
h[i][j] = ;
}
else {
h[i][j] = h[i - ][j] + ;
}
//printf("h %d %d %d \n", i, j, h[i][j]);
}
} LL large = -INF;
int u, d, left, right; for(int i = ; i <= n; i++) { // down
top = ;
p[] = ;
for(int j = ; j <= m; j++) {
while(top && h[i][p[top]] >= h[i][j]) {
top--;
}
l[j] = p[top] + ;
p[++top] = j;
}
top = ;
p[] = m + ;
for(int j = m; j >= ; j--) {
while(top && h[i][p[top]] >= h[i][j]) {
top--;
}
r[j] = p[top] - ;
p[++top] = j;
} for(int j = ; j <= m; j++) {
LL t = getsum(l[j], r[j], i - h[i][j] + , i);
if(t > large) {
large = t;
u = i - h[i][j] + ;
d = i;
left = l[j];
right = r[j];
}
}
} if(large < k) {
printf("NIE");
return ;
} while(large > (k << )) {
if(u < d) {
int mid = (u + d) >> ;
if(getsum(left, right, u, mid) >= k) {
d = mid;
}
else {
u = mid + ;
}
}
else {
int mid = (left + right) >> ;
if(getsum(left, mid, u, d) >= k) {
right = mid;
}
else {
left = mid + ;
}
}
large = getsum(left, right, u, d);
} printf("%d %d %d %d", left, u, right, d); return ;
}
AC代码