牛客多校第三场 F Planting Trees

淡淡的烟草味﹌ 2021-10-15 23:37 282阅读 0赞

# 牛客多校第三场 F Planting Trees #

# 题意： #

求矩阵内最大值减最小值大于k的最大子矩阵的面积

# 题解： #

矩阵压缩的技巧

因为对于我们有用的信息只有这个矩阵内的最大值和最小值

所以我们可以将一个长度为i\*j的子矩阵给压缩成一个1\*i的序列

那么压缩成一维就是求区间内最大值减最小值大于k的最长长度了，这个问题用两个单调队列维护即可

# 代码： #

/** *　　　　　　　　┏┓　　 　┏┓ * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓ * 　　　　　　　┃　　　　　　　┃ 　 * 　　　　　　　┃　　　━　　 　┃ * 　　　　　　　┃　＞　　　＜　┃ * 　　　　　　　┃　　　　　　　┃ * 　　　　　　　┃...　⌒　... 　┃ * 　　　　　　　┃　　　　　　　┃ * 　　　　　　　┗━┓　　　┏━┛ * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　 * 　　　　　　　　　┃　　　┃ 神兽保佑,代码无bug * 　　　　　　　　　┃　　　┃　　　　　　　　　　　 * 　　　　　　　　　┃　　　┃ 　　　　　　 * 　　　　　　　　　┃　　　┃ * 　　　　　　　　　┃　　　┃　　　　　　　　　　　 * 　　　　　　　　　┃　　　┗━━━┓ * 　　　　　　　　　┃　　　　　　　┣┓ * 　　　　　　　　　┃　　　　　　　┏┛ * 　　　　　　　　　┗┓┓┏━┳┓┏┛ * 　　　　　　　　　　┃┫┫　┃┫┫ * 　　　　　　　　　　┗┻┛　┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // 佛祖保佑 永无BUG #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double Pi = acos(-1); LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } LL lcm(LL a, LL b) { return a / gcd(a, b) * b; } double dpow(double a, LL b) { double ans = 1.0; while(b) { if(b % 2)ans = ans * a; a = a * a; b /= 2; } return ans; } LL quick_pow(LL x, LL y) { LL ans = 1; while(y) { if(y & 1) { ans = ans * x % mod; } x = x * x % mod; y >>= 1; } return ans; } int a[505][505]; int qmax[505], qmin[505]; int Max[505], Min[505]; int main() { #ifndef ONLINE_JUDGE FIN #endif int T; scanf("%d", &T); while(T--) { int n, K; scanf("%d%d", &n, &K); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); } } LL res = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { Max[j] = -INF; Min[j] = INF; } for(int j = i; j <= n; j++) { for(int k = 1; k <= n; k++) { Max[k] = max(Max[k], a[j][k]); Min[k] = min(Min[k], a[j][k]); } int l = 1, hmax = 0, hmin = 0, tmax = 1, tmin = 1; for(int r = 1; r <= n; r++) { while(tmax <= hmax && Max[r] >= Max[qmax[hmax]]) hmax--; while(tmin <= hmin && Min[r] <= Min[qmin[hmin]]) hmin--; qmax[++hmax] = r; qmin[++hmin] = r; while(l <= r && ( Max[qmax[tmax]] - Min[qmin[tmin]] > K) ) { l++; if(qmax[tmax] < l)tmax++; if(qmin[tmin] < l)tmin++; } res = max(res, 1LL * (r - l + 1) * (j - i + 1)); } } } printf("%lld\n", res); } return 0; }

转载于:https://www.cnblogs.com/buerdepepeqi/p/11323613.html