首页 > 代码库 > bzoj1047题解

bzoj1047题解

2024-09-11 01:41:05   217人阅读

【解题思路】

　　（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 }
View Code

 

bzoj1047题解


联系
我们