第 7 场 小白入门赛

第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);  //升序
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/456956.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

介绍Oracle的SQL调化健康检查脚本（SQLHC）

介绍Oracle的SQL调化健康检查脚本（SQLHC）

概述 Oracle提供了一个SQL调优健康检查脚本&#xff08;SQLHC&#xff09;&#xff0c;用于检查需要优化的SQL的运行环境&#xff0c;生成报告以便帮助DBA找到SQL性能不佳的原因。SQLHC是SQLT的一个子集&#xff08;我后续的文章会介绍SQLT&#xff09;&#xff0c;但SQLHC与S…
阅读更多...
【string一些函数用法的补充】

【string一些函数用法的补充】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 string类对象的修改操作 我们来看 c_str 返回c格式的字符串的操作&#xff1a; 我们来看 rfind 和 substr 的操作&#xff1a; string类非成员函数 我们来看 r…
阅读更多...
安全访问服务边缘解决方案

安全访问服务边缘解决方案

随着云计算、大数据和物联网技术的快速发展&#xff0c;企业对于业务数据的访问需求日益增多&#xff0c;而安全访问服务边缘&#xff08;Secure Access Service Edge&#xff0c;SASE&#xff09;作为一种新兴的网络架构&#xff0c;正逐渐成为企业保障数据安全、优化网络性能…
阅读更多...
Python引入其他文件作为包

Python引入其他文件作为包

1.首先当我们写的代码&#xff0c;可能要被其他文件引用&#xff0c;那么在建文件夹的时候&#xff0c;记得选包 不是文件夹&#xff01;&#xff08;选第4个&#xff0c;不是第3个&#xff09; 因为文件夹默认没有init 方法&#xff0c;不能导包... 如果已经是文件夹了&#…
阅读更多...
Claude3、Gemini、Sora与GPT-4：谁将成为AI领域的明日之星？

Claude3、Gemini、Sora与GPT-4：谁将成为AI领域的明日之星？

【最新增加Claude3、Gemini、Sora、GPTs讲解及AI领域中的集中大模型的最新技术】 2023年随着OpenAI开发者大会的召开&#xff0c;最重磅更新当属GPTs&#xff0c;多模态API&#xff0c;未来自定义专属的GPT。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义&#xff0c;不亚…
阅读更多...
ECCV2022 | BEVFormer原文翻译

ECCV2022 | BEVFormer原文翻译

BEVFormer: Learning Bird’s-Eye-View Representation from Multi-Camera Images via Spatiotemporal Transformers BEVFormer: 通过时空变换器从多摄像头图像中学习鸟瞰图表征 Figure 1: We propose BEVFormer, a paradigm for autonomous driving that applies both Trans…
阅读更多...
【Java探索之旅】运算符解析 算术运算符，关系运算符

【Java探索之旅】运算符解析 算术运算符，关系运算符

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Java编程秘籍 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一、什么是运算符二、算术运算符2.1 基本四则运算&#xff08;-*/%&#xff09;2.2 增…
阅读更多...
2049.不容易系列之(4)——考新郎

2049.不容易系列之(4)——考新郎

2048的升级 当nm时则全排错&#xff0c;与上题一样 当n>m时&#xff0c;则有n-m个是排对的&#xff0c;剩下m个全错 import java.util.*;public class Main {public static void main(String[] args) {Scanner scannernew Scanner(System.in);int num scanner.nextInt()…
阅读更多...
LeetCode2.07链表相交

LeetCode2.07链表相交

2.07链表相交 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函数返回结…
阅读更多...
洛谷 P5018 对称二叉树

洛谷 P5018 对称二叉树

题目背景 NOIP2018 普及组 T4 题目描述 一棵有点权的有根树如果满足以下条件&#xff0c;则被轩轩称为对称二叉树&#xff1a; 二叉树&#xff1b;将这棵树所有节点的左右子树交换&#xff0c;新树和原树对应位置的结构相同且点权相等。 下图中节点内的数字为权值&#xf…
阅读更多...
Compose UI 之 BottomAppBar 底部应用栏

Compose UI 之 BottomAppBar 底部应用栏

BottomAppBar 底部应用栏 BottomAppBar 是一个在 Jetpack Compose 中用于创建底部应用栏的组件。它提供了一个高度可定制且功能丰富的底部导航解决方案。 它的使用方式与 TopAppBar 类似。下面的图是 BottomAppBar 的基本样式图。 常见使用场景 BottomAppBar 在应用中常用于…
阅读更多...
【JavaScript】使用debugger语句快速开启浏览器调试代码工具

【JavaScript】使用debugger语句快速开启浏览器调试代码工具

简言 有的时候我们想开启浏览器代码调试功能&#xff0c;这个时候应该使用debugger语句。 debugger debugger 语句调用任何可用的调试功能&#xff0c;例如设置断点。如果没有调试功能可用&#xff0c;则此语句不起作用。 debugger;可以多次使用 debugger语句&#xff0c;使…
阅读更多...
蓝桥杯练习系统（算法训练）ALGO-976 P0804字符串压缩

蓝桥杯练习系统（算法训练）ALGO-976 P0804字符串压缩

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 编写一个函数void strcompress(char *s)&#xff0c;输入一个字符串&#xff08;只包含小写字母和空格&#xff0c;且长度小于1000&am…
阅读更多...
基于springboot社团管理系统的设计与实现

基于springboot社团管理系统的设计与实现

互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差&#xff0c;劳…
阅读更多...
leetcode代码记录（有效的括号

leetcode代码记录（有效的括号

目录 1. 题目&#xff1a;2. 我的代码&#xff1a;小结&#xff1a; 1. 题目&#xff1a; 给定一个只包括 ‘(’&#xff0c;‘)’&#xff0c;‘{’&#xff0c;‘}’&#xff0c;‘[’&#xff0c;‘]’ 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&…
阅读更多...
香港理工大学主办！2024年第八届电力能源系统与应用国际会议（ICoPESA 2024）即将召开！

香港理工大学主办！2024年第八届电力能源系统与应用国际会议（ICoPESA 2024）即将召开！

2024年第八届电力能源系统与应用国际会议&#xff08;ICoPESA 2024&#xff09; 2024年6月24日-26日 中国香港 ICoPESA 2024-Hong Kong (icpesa.org)https://icpesa.org/index.html 会议组织单位 会议出版及检索&#xff1a; 会议录用并注册的论文将由IEEE出版&#xff0c;…
阅读更多...
Let’s Move Sui , 一起来学习吧

Let’s Move Sui , 一起来学习吧

Let’s Move Sui是一个全新的交互式学习平台&#xff0c;通过SuiFrens的帮助教您如何在Sui上构建。设计供新手和经验丰富的开发者使用&#xff0c;Let’s Move Sui提供了一次非凡的Sui开发之旅&#xff0c;利用了Move在Sui上的独特之处&#xff0c;从基于对象的数据模型的基础知…
阅读更多...
3、鸿蒙学习-在AGC创建HarmonyOS 项目或应用

3、鸿蒙学习-在AGC创建HarmonyOS 项目或应用

项目和应用介绍 关于项目 项目是资源、应用的组织实体。资源包括服务器、数据库、存储&#xff0c;以及您的应用、终端用户的数据等。在您使用部分服务时&#xff0c;您是数据的控制者&#xff0c;数据将按照您设置的数据处理位置来存储在指定区域。 通常&#xff0c;您不需…
阅读更多...
SE园区综合实验（未补齐版）

SE园区综合实验（未补齐版）

实验要求&#xff1a; 1.局域网存在vlan10和vlan20两个业务vlan&#xff0c;ip网段分别对应192.168.1.0/24和192.168.2.0/24 2.业务vlan可以在所有链路上传输数据 3.sw1和sw2之间的直连链路上配置静态链路聚合实现链路冗余&#xff0c;并提高链路带宽 4.sw3为某接入点二次交…
阅读更多...
C# ListView 控件使用

C# ListView 控件使用

1.基本设置 listView1.Columns.Add("序号", 60); //向 listView1控件中添加1列 同时设置列名称和宽度listView1.Columns.Add("温度", 100); //下同listView1.Columns.Add("偏移", 100);listView1.Columns.Add("分割", 50);listView1…
阅读更多...
最新文章

Copyright @ 2022~2023