第 7 场小白入门赛

2024-03-15 09:44:01
开发
32

第5题：兽之泪【算法赛】

AC_Code:C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
#define pb push_back

int const mod1=998244353,mod2=1e9+7;  
int const base=131;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;

int n,m,q;
PII a[N];
string s,t;
vector<int>e[N];

void solve(){
    
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)    scanf("%d%d",&a[i].x,&a[i].y);
    sort(a,a+(n-1));
       
       LL ans1=0,ans2=0;
       int t=m,mi=INF;
       for(int i=0;i<n;i++){    //不用最后一个数
           if(mi<a[i].x){
            ans1+=1LL*t*mi;
            t=0;    break;
        }
        ans1+=a[i].x;
        if(--t==0)    break;
        mi=min(mi,a[i].y);
       }
       ans1+=1LL*t*mi;
       
       t=m;    mi=INF;
       for(int i=0;i<n;i++){    //用最后一个数
        ans2+=a[i].x;
        if(--t==0)    break;
        mi=min(mi,a[i].y);    
       }
       ans2+=1LL*t*mi;
   
    cout<<min(ans1,ans2);
       
} 

void init(){                     
    
}

int main()
{
    //std::ios::sync_with_stdio(false);   cin.tie(0); cout.tie(0);
    init();
    int T=1;
    //cin>>T;
    //scanf("%d",&T);
    
    while(T--){
        solve();
    }
    
    return 0;
}

AC_Code:java

// package A;
import java.util.*;
import java.io.*;

public class Main{

    static final int N=(int)2e5+7;
    static int mod1=(int)998244353,mod2=(int)1e9+7;
    static long mod=3185689261L;
    static int INF=0x3f3f3f3f;
    static long INFF=0x3f3f3f3f3f3f3f3fL;
    static Node[] a=new Node[N];
    static int n,m;
    static List<Integer>[] g=new ArrayList[N];


    public static void solve()throws IOException{
        //Arrays.setAll(g,e->new ArrayList<>());
        n=nextInt(); m=nextInt();
        for(int i=0;i<n;i++)    a[i]=new Node(nextInt(),nextInt());
        Arrays.sort(a,0,n-1);   //怪兽之王，只能最后打


        int m1=m;
        long ans1=0,ans2=0;
        int mi=INF;
        for(int i=0;i<n&&m1>0;i++){ //有更小贡献，就提前计算贡献
            if(mi<a[i].x){
                ans1+=1L*mi*m1;
                m1=0;
                break;
            }
            ans1+=a[i].x;   m1--;
            mi=Math.min(mi,a[i].y);
        }
        ans1+=1L*mi*m1;

        mi=INF; m1=m;
        for(int i=0;i<n&&m1>0;i++){ //可以打怪兽之王的话就打，看是否有更小的贡献
            ans2+=a[i].x;   m1--;
            mi=Math.min(mi,a[i].y);
        }
        ans2+=1L*mi*m1;
        pw.println(Math.min(ans1,ans2));
        pw.flush();

    }

    static void init(){

    }


    public static void main(String[] args)throws IOException{
        init();
        int T=1;
        // T=nextInt();
        while(T-->0){
            solve();
        }

    }

    static Scanner sc=new Scanner(System.in);
    //这个读字符串可以带有空格，br.readLine(),不用刷新缓存区
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //读字符串时空格，回车，换行都进行分割
    static StreamTokenizer st = new StreamTokenizer(br);

    //pw.println(),没写一次记得刷新缓存区pw.flush()
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static int nextInt() throws IOException { st.nextToken(); return (int)st.nval; }
    public static long nextLong() throws IOException { st.nextToken(); return (long)st.nval; }

    public static float nextFloat() throws IOException{ st.nextToken(); return (float)st.nval; }
    //st读的本来就是double类型
    public static double nextDouble() throws IOException{ st.nextToken(); return st.nval; }


}

class Node implements Comparable<Node>{
    int x,y;

    public Node() {
    }

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compareTo(Node o){
        return Integer.compare(x,o.x);  //升序
    }
}

第6题：矩阵X【算法赛】

AC_Code:C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>

using namespace std;
typedef long long LL;
int const N=1e6+7;

int n,m,n1,m1;
int q1[N],q2[N];
int head1,head2,tail1,tail2;

int main()
{
    scanf("%d%d%d%d", &n, &m,&n1,&m1);
    vector<vector<int>> a(n+1,vector<int>(m+1));
    vector<vector<int>> mx(n+1,vector<int>(m+1));
    vector<vector<int>> mi(n+1,vector<int>(m+1));
    vector<vector<LL>> pre(n+1,vector<LL>(m+1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    
//    先对每一行，跑一个滑动窗口        
    for(int i=1;i<=n;i++){
        head1=head2=0;
        tail1=tail2=-1;
        for(int j=1;j<=m;j++){
            while(tail1>=head1&&a[i][j]<=a[i][q1[tail1]])    tail1--;
            q1[++tail1]=j;
            if(tail1>=head1&&j-m1+1>q1[head1])   head1++;    //滑出窗口
            if(j>=m1) mi[i][j-m1+1]=a[i][q1[head1]];
            
            while(tail2>=head2&&a[i][j]>=a[i][q2[tail2]])   tail2--;
            q2[++tail2]=j;
            if(tail2>=head2&&j-m1+1>q2[head2])   head2++;
            if(j>=m1) mx[i][j-m1+1]=a[i][q2[head2]];
        }
    }
    
    //对每一列跑一遍滑动窗口
    for(int j=1;j<=m;j++){
        head1=head2=0;
        tail1=tail2=-1;
        for(int i=1;i<=n;i++){
            while(tail1>=head1&&mi[i][j]<=mi[q1[tail1]][j])   tail1--;
            q1[++tail1]=i;
            if(tail1>=head1&&i-n1+1>q1[head1])   head1++;
            if(i>=n1)    mi[i-n1+1][j]=min(mi[i-n1+1][j],mi[q1[head1]][j]);
            
            while(tail2>=head2&&mx[i][j]>=mx[q2[tail2]][j])   tail2--;
            q2[++tail2]=i;
            if(tail2>=head2&&i-n1+1>q2[head2])   head2++;
            if(i>=n1)    mx[i-n1+1][j]=max(mx[i-n1+1][j],mx[q2[head2]][j]);
        }
    }
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+a[i][j];
        }
    
    long long ans=0;  //枚举起点，更新答案
    for(int i=1;i<=n-n1+1;i++)
        for(int j=1;j<=m-m1+1;j++){
            int x2=i+n1-1,y2=j+m1-1;
            ans=max(ans,(pre[x2][y2]-pre[x2][j-1]-pre[i-1][y2]+pre[i-1][j-1])*(mx[i][j]-mi[i][j]));
        }
            
            
    cout<<ans<<endl;

    return 0;
}

AC_Code:java

// package A;
import java.util.*;
import java.io.*;

public class Main{

    static final int N=(int)2e5+7;
    static int mod1=(int)998244353,mod2=(int)1e9+7;
    static long mod=3185689261L;
    static int INF=0x3f3f3f3f;
    static long INFF=0x3f3f3f3f3f3f3f3fL;
    static int[] a=new int[N];
    static int n,m;
    static List<Integer>[] g=new ArrayList[N];


    public static void solve()throws IOException{
        n=nextInt(); m=nextInt();
        int n1=nextInt(),m1=nextInt();
        int[][] a=new int[n+1][m+1];
        int[][] mx=new int[n+1][m+1];
        int[][] mi=new int[n+1][m+1];
        long[][] pre=new long[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=nextInt();
                pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
            }
        }

        int[] q1=new int[n*m+1],q2=new int[n*m+1];
        int tt1=-1,hh1=0,tt2=-1,hh2=0;

        //列
        for(int i=1;i<=n;i++){
            tt1=-1; hh1=0; tt2=-1; hh2=0;
            for(int j=1;j<=m;j++){
                //小
                while(tt1>=hh1&&a[i][q1[tt1]]>=a[i][j]) tt1--;
                q1[++tt1]=j;
                if(j-q1[hh1]+1>m1)  hh1++;
                if(j>=m1)   mi[i][j-m1+1]=a[i][q1[hh1]];

                //大
                while(tt2>=hh2&&a[i][q2[tt2]]<=a[i][j]) tt2--;
                q2[++tt2]=j;
                if(j-q2[hh2]+1>m1)  hh2++;
                if(j>=m1)   mx[i][j-m1+1]=a[i][q2[hh2]];
            }
        }

        //行
        for(int j=1;j<=m;j++){
            tt1=-1; hh1=0; tt2=-1; hh2=0;
            for(int i=1;i<=n;i++){
                //小
                while(tt1>=hh1&&mi[q1[tt1]][j]>=mi[i][j]) tt1--;
                q1[++tt1]=i;
                if(i-q1[hh1]+1>n1)  hh1++;
                if(i>=n1)   mi[i-n1+1][j]=Math.min(mi[i-n1+1][j],mi[q1[hh1]][j]);

                //大
                while(tt2>=hh2&&mx[q2[tt2]][j]<=mx[i][j])   tt2--;
                q2[++tt2]=i;
                if(i-q2[hh2]+1>n1)  hh2++;
                if(i>=n1)   mx[i-n1+1][j]=Math.max(mx[i-n1+1][j],mx[q2[hh2]][j]);
            }
        }

        long ans=0;
        for(int i=1;i+n1-1<=n;i++){
            for(int j=1;j+m1-1<=m;j++){
//                pw.print(mx[i][j]+"*"+mi[i][j]+" ");
                int x2=i+n1-1,y2=j+m1-1;
                ans=Math.max(ans,(pre[x2][y2]-pre[x2][j-1]-pre[i-1][y2]+pre[i-1][j-1])*(mx[i][j]-mi[i][j]));
            }
//            pw.println();
        }


        pw.println(ans);
        pw.flush();
    }

    static void init(){

    }


    public static void main(String[] args)throws IOException{
        init();
        int T=1;
        // T=nextInt();
        while(T-->0){
            solve();
        }

    }

    static Scanner sc=new Scanner(System.in);
    //这个读字符串可以带有空格，br.readLine(),不用刷新缓存区
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //读字符串时空格，回车，换行都进行分割
    static StreamTokenizer st = new StreamTokenizer(br);

    //pw.println(),没写一次记得刷新缓存区pw.flush()
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static int nextInt() throws IOException { st.nextToken(); return (int)st.nval; }
    public static long nextLong() throws IOException { st.nextToken(); return (long)st.nval; }

    public static float nextFloat() throws IOException{ st.nextToken(); return (float)st.nval; }
    //st读的本来就是double类型
    public static double nextDouble() throws IOException{ st.nextToken(); return st.nval; }


}

class Node implements Comparable<Node>{
    int x,y;

    public Node() {
    }

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compareTo(Node o){
        return Integer.compare(x,o.x);  //升序
    }
}

原文地址:https://blog.csdn.net/qq_74861982/article/details/136722331 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1768453062030135296.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部