公司的网站建设,免费建站优化,wordpress手动摘要不显示,男子做网站题目链接 题目链接 题解 题面上面很明显的提示了需要严格\(O(n^3)\)的算法。 先考虑一个过不了的做法#xff0c;枚举右下角的\((x,y)\)#xff0c;然后二分矩形面积#xff0c;枚举其中一边#xff0c;则复杂度是\(O(n^3 \log n^2)\)的。 考虑另外一个做法#xff0c;同样…题目链接 题目链接 题解 题面上面很明显的提示了需要严格\(O(n^3)\)的算法。 先考虑一个过不了的做法枚举右下角的\((x,y)\)然后二分矩形面积枚举其中一边则复杂度是\(O(n^3 \log n^2)\)的。 考虑另外一个做法同样是枚举右下角\((x,y)\)然后枚举一边长度显然现在只需要知道左边最远能延伸到哪这个玩意显然是有单调性的那么尺取一下套个单调队列判断即可。 注意细节。 #include bits/stdc.h
using namespace std;namespace io {
char buf[121], *p1 buf, *p2 buf;
inline char gc() {if(p1 ! p2) return *p1;p1 buf;p2 p1 fread(buf, 1, 1 21, stdin);return p1 p2 ? EOF : *p1;
}
#define G gc#ifndef ONLINE_JUDGE
#undef G
#define G getchar
#endiftemplateclass I
inline void read(I x) {x 0; I f 1; char c G();while(c 0 || c 9) {if(c -) f -1; c G(); }while(c 0 c 9) {x x * 10 c - 0; c G(); }x * f;
}templateclass I
inline void write(I x) {if(x 0) {putchar(0); return;}I tmp x 0 ? x : -x;if(x 0) putchar(-);int cnt 0;while(tmp 0) {buf[cnt] tmp % 10 0;tmp / 10;}while(cnt 0) putchar(buf[--cnt]);
}#define in(x) read(x)
#define outn(x) write(x), putchar(\n)
#define out(x) write(x), putchar( )} using namespace io;#define ll long long
const int N 510;struct Node {int x, y, v;
};
int T, n, m;
int a[N][N], mx[N], mn[N];
int qmin[N], qmax[N];int main() {read(T);while(T--) {int ans 0;read(n); read(m);for(int i 1; i n; i) for(int j 1; j n; j) read(a[i][j]);for(int l 1; l n; l) {for(int i 1; i n; i) mn[i] 1e9, mx[i] 0;for(int r l; r n; r) {for(int i 1; i n; i) {mn[i] min(mn[i], a[r][i]);mx[i] max(mx[i], a[r][i]);}int cur 1, l0 1, l1 1, r0 0, r1 0;for(int i 1; i n; i) {while(l0 r0 mn[qmin[r0]] mn[i]) --r0;while(l1 r1 mx[qmax[r1]] mx[i]) --r1;qmin[r0] i; qmax[r1] i;while(l0 r0 l1 r1 cur i mx[qmax[l1]] - mn[qmin[l0]] m) {cur;while(l0 r0 qmin[l0] cur) l0;while(l1 r1 qmax[l1] cur) l1;}if(mx[qmax[l1]] - mn[qmin[l0]] m) ans max(ans, (r - l 1) * (i - cur 1));}}}outn(ans);}
} 转载于:https://www.cnblogs.com/henry-1202/p/11247694.html
