首页 > 代码库 > BZOJ1047 [HAOI2007]理想的正方形
BZOJ1047 [HAOI2007]理想的正方形
昨天刷水累死蒟蒻了。。。
每天一到题解总还是要写的。。。于是就是这个了！
二维RMQ，第一反应是二维线段树，妥妥MLE + TLE
想起来去年市选小题有一道一模一样的，我当时就是写二维线段树，然后MLE0分、、、真是悲剧
发现长度是固定的为n，和动态规划的某个叫单调队列的优化很像：
先求出每一列的某个点向下n个数的最大/小值，然后求出每一行某个点向右的n个单调队列的最大/小值，方法依旧是单调队列。。。
程序写的很烦。。。是照抄网上的。。。（太烦了不想写呢><）
1 /************************************************************** 2 Problem: 1047 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1604 ms 7 Memory:16600 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 const int N = 1005;15 16 int mp[N][N];17 int q[N][N], h[N], t[N], Q[N];18 int mx[N][N], mn[N][N];19 int s, e, a, b, n;20 21 inline int read(){22 int x = 0, sgn = 1;23 char ch = getchar();24 while (ch < ‘0‘ || ch > ‘9‘){25 if (ch == ‘-‘) sgn = -1;26 ch = getchar();27 }28 while (ch >= ‘0‘ && ch <= ‘9‘){29 x = x * 10 + ch - ‘0‘;30 ch = getchar();31 }32 return sgn * x;33 }34 35 void getmax(){36 for (int i = 1; i <= b; ++i)37 h[i] = 1, t[i] = 0;38 for (int i = 1; i <= a; ++i){39 for (int j = 1; j <= b; ++j){40 while (h[j] <= t[j] && i - q[j][h[j]] >= n) ++h[j];41 while (h[j] <= t[j] && mp[q[j][t[j]]][j] <= mp[i][j]) --t[j];42 q[j][++t[j]] = i;43 }44 e = 0, s = 1;45 for (int j = 1; j <= b; ++j){46 while (s <= e && j - Q[s] >= n) ++s;47 while (s <= e && mp[q[Q[e]][h[Q[e]]]][Q[e]] <= mp[q[j][h[j]]][j]) --e;48 Q[++e] = j;49 mx[i][j] = mp[q[Q[s]][h[Q[s]]]][Q[s]];50 }51 }52 }53 54 void getmin(){55 for (int i = 1; i <= b; ++i)56 h[i] = 1, t[i] = 0;57 for (int i = 1; i <= a; ++i){58 for (int j = 1; j <= b; ++j){59 while (h[j] <= t[j] && i - q[j][h[j]] >= n) ++h[j];60 while (h[j] <= t[j] && mp[q[j][t[j]]][j] >= mp[i][j]) --t[j];61 q[j][++t[j]] = i;62 }63 e = 0, s = 1;64 for (int j = 1; j <= b; ++j){65 while (s <= e && j - Q[s] >= n) ++s;66 while (s <= e && mp[q[Q[e]][h[Q[e]]]][Q[e]] >= mp[q[j][h[j]]][j]) --e;67 Q[++e] = j;68 mn[i][j] = mp[q[Q[s]][h[Q[s]]]][Q[s]];69 }70 }71 }72 73 int main(){74 a = read(), b = read(), n = read();75 for (int i = 1; i <= a; ++i)76 for (int j = 1; j <= b; ++j)77 mp[i][j] = read();78 79 getmax();80 getmin();81 int ans = (int) 1e9;82 for (int i = n; i <= a; ++i)83 for (int j = n; j <= b; ++j)84 ans = min(ans, mx[i][j] - mn[i][j]);85 printf("%d\n", ans);86 return 0;87 }
BZOJ1047 [HAOI2007]理想的正方形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。