首页 > 代码库 > bzoj1047题解
bzoj1047题解
【解题思路】
(p.s.:刚看的时候一脸懵逼。。没看见N已经给定了,还以为要用某些高明的方法。。果然还是太naive了。。)
两遍预处理,第一遍处理出f[i][j][0/1]表示第i行从j-n+1~j中的最小/大值,第二遍基于f数组处理出g[i][j][0/1]表示以(i,j)为右下角的长度为n的正方形中最小/大值,然后O(ab)枚举即可。
预处理可以用单调队列均摊O(1),然而本人比较懒。。直接上了STL set,均摊复杂度O(log2n)。
总复杂度O(ab)(单调队列)或O(ablog2n)(STL set等带log数据结构)。
【参考代码】
1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 5 //#define __debug 6 #ifdef __debug 7 #define Function(type) type 8 #define Procedure void 9 #else10 #define Function(type) __attribute__((optimize("-O2"))) inline type11 #define Procedure __attribute__((optimize("-O2"))) inline void12 #endif13 14 #ifdef __int128_t15 typedef __int128_t integer;16 #else17 typedef long long integer;18 #endif19 20 using namespace std;21 22 //quick_io {23 Function(integer) getint()24 {25 char c=getchar(); for(;!isdigit(c)&&c!=‘-‘;c=getchar());26 short s=1; for(;c==‘-‘;c=getchar()) s*=-1; integer r=0;27 for(;isdigit(c);c=getchar()) (r*=10)+=c-‘0‘; return s*r;28 }29 //} quick_io30 31 multiset<int> rec; int r[1005][1005];32 int mn1[1005][1005],mx1[1005][1005],33 mn2[1005][1005],mx2[1005][1005];34 35 int main()36 {37 int a=getint(),b=getint(),n=getint();38 range(i,0,a) range(j,0,b) r[i][j]=getint();39 range(i,0,a)40 {41 rec.clear(); range(j,0,n) rec.insert(r[i][j]);42 mn1[i][n-1]=*rec.begin(),mx1[i][n-1]=*rec.rbegin();43 range(j,n,b)44 {45 rec.erase(rec.find(r[i][j-n]));46 rec.insert(r[i][j]);47 mn1[i][j]=*rec.begin(),mx1[i][j]=*rec.rbegin();48 }49 }50 range(i,0,b)51 {52 rec.clear();53 range(j,0,n)54 {55 rec.insert(mn1[j][i]),rec.insert(mx1[j][i]);56 }57 mn2[n-1][i]=*rec.begin(),mx2[n-1][i]=*rec.rbegin();58 range(j,n,a)59 {60 rec.erase(rec.find(mn1[j-n][i]));61 rec.erase(rec.find(mx1[j-n][i]));62 rec.insert(mn1[j][i]),rec.insert(mx1[j][i]);63 mn2[j][i]=*rec.begin(),mx2[j][i]=*rec.rbegin();64 }65 }66 int ans=0x7f7f7f7f;67 range(i,n-1,a) range(j,n-1,b)68 {69 ans=min(ans,mx2[i][j]-mn2[i][j]);70 }71 return printf("%d\n",ans),0;72 }
bzoj1047题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。