解题思路:
思路总结一下吧:第一步:算每个((行)a*(列)1)的最小值。
第二步,再增加列数,当列数达到b的时候这样就构成了一个(a*b)的矩阵,这样就可以得出一个矩阵的最小值。以此类推。
最大值同样道理
注意事项:1..multiset定义排序规则需要用类实现
2.每次进入新行需要清空排序容器
参考代码:
#include<iostream> #include<vector> #include<set> using namespace std; #define ll long long const int N=1010,mod=998244353; int n,m,a,b; ll w[N][N]; ll lmin[N][N],lmax[N][N]; class cmp{ public: bool operator()(ll x,ll y) { return x>y; } }; vector<ll>ansmin; vector<ll>ansmax; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>a>>b; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>w[i][j]; //计算以a为行数的,1为列数的所有列条的最小值 multiset<ll>p; for(int j=1;j<=m;j++) for(int i=1;i<=n;i++){ if(i==1) p.clear(); p. insert(w[i][j]); //先删除最顶端的不在范围内的那个值,再去取最小值 if(i>a){ p.erase(*p.find(w[i-a][j])); } if(i>=a) { lmin[i-a+1][j]=*p.begin(); } } //计算以a为行数的,1为列数的所有列条的最大值 multiset<ll,cmp>q; for(int j=1;j<=m;j++) for(int i=1;i<=n;i++){ if(i==1) q.clear(); q. insert(w[i][j]); //先删除最顶端的不在范围内的那个值,再去取最小值 if(i>a){ q.erase(*q.find(w[i-a][j])); } if(i>=a) { lmax[i-a+1][j]=*q.begin(); } } vector<ll>ansmin; multiset<ll>x; //搜索每个二维区间的最小值 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ //算下一行需要更新排序容器,防止上一行后面的残留数据影响当前新的矩阵的最值判断 if(j==1) x.clear(); x.insert(lmin[i][j]); if(j>b){ x.erase(*x.find(lmin[i][j-b])); } if(j>=b){ //这要的是以(i,j)为左上顶点的以a*b为矩阵的最小值 ansmin.push_back(*x.begin()); } } vector<ll>ansmax; multiset<ll,cmp>y; //搜索每个二维区间的最大值 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ //算下一行需要更新排序容器,防止上一行后面的残留数据影响当前新的矩阵的最值判断 if(j==1) y.clear(); y.insert(lmax[i][j]); if(j>b){ //这要的是以(i,j)为左上顶点的以a*b为矩阵的最大值 y.erase(*y.find(lmax[i][j-b])); } if(j>=b){ ansmax.push_back(*y.begin()); } } //算最后的结果,由于数据量的一致性,所以两个存放最大值和最小值的容器大小一致 ll ans=0; for(int i=0;i<ansmin.size();i++) ans=(ans+(ansmin[i]%mod)*ansmax[i]%mod)%mod; cout<<ans; return 0; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题6.2 (C++代码)为什么回车不算字符浏览:1166 |
人民币问题 (C语言代码)浏览:636 |
A+B for Input-Output Practice (V) (C语言代码)浏览:430 |
IP判断 (C++代码)浏览:651 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:715 |
C语言训练-阿姆斯特朗数 (C语言代码)浏览:823 |
C语言训练-排序问题<1> (C语言代码)浏览:1325 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:614 |
C语言考试练习题_保留字母 (C语言代码)浏览:557 |
简单的a+b (C语言代码)浏览:471 |