解题思路:
思路总结一下吧:第一步:算每个((行)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分
5 人评分
点我有惊喜!你懂得!浏览:2726 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:614 |
校门外的树 (C语言代码)浏览:725 |
2^k进制数 (C++代码)使用递归方法浏览:729 |
2005年春浙江省计算机等级考试二级C 编程题(3),复杂度最低的方法没有之一!!!!!浏览:839 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:768 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:478 |
数对 (C语言代码)浏览:735 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1087 |
核桃的数量 (C语言代码)浏览:887 |
Bingbong 2024-03-19 20:44:44 |
当初写的时候是错的,神奇C语言网不知道咋过的,现在是对的,主要在于p.erase(*)和p.erase()里面没*的区别,在于删除迭代器,有*是迭代器,会删除所有相同元素,没*删除单个。