Bingbong


私信TA

用户名:dotcpp0610876

访问量:1633

签 名:

等  级
排  名 3258
经  验 1913
参赛次数 4
文章发表 3
年  龄 0
在职情况 学生
学  校 河南科技学院
专  业

  自我简介:

解题思路:

思路总结一下吧:第一步:算每个((行)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 人评分

看不懂代码?想转换其他语言的代码? 或者想问其他问题? 试试问问AI编程助手,随时响应你的问题:

编程语言转换

万能编程问答  

代码解释器

代码纠错

SQL生成与解释

  评论区

这个代码在蓝桥云课上面怎么只通过30%,谁能解答一下到底以哪个为标准
2024-03-16 10:37:03
tql
2023-08-16 11:09:54
  • «
  • 1
  • »