2024.4.5|牛客小白月赛90

2024.4.5|牛客小白月赛90

A.小A的文化节
B.小A的游戏
C.小A的数字
D.小A的线段（easy version）
E.小A的任务
F.小A的线段（hard version）

心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。
在这里插入图片描述

小A的文化节

题目：
小A的学校举办了一年一度的文化节！
在文化节中有 n 个项目，其中参加第 i 个项目的欢乐度是 ai 。虽然小A很想把全部项目都体验一遍，但是她的时间是有限的，因此她只能参加其中的 m 个项目。
现在小A告诉你她参加了哪些项目，请你帮她计算一下她的欢乐度吧。

输入描述:

第一行两个正整数 n 和 m(1≤m≤n≤100) ，分别表示文化节总的项目数和小A参加的项目数。 第二行 n 个正整数，其中第 i 个数字
​ (1≤ai≤105 ) 表示参加第 i 个项目得到的欢乐度。 第三行 m 个正整数，其中第 i 个数字 (1≤b i≤n)
表示小A参加了编号为 bi的项目。数据保证 bi各不相同。

输出描述:

输出一行一个整数表示小A的欢乐度。

示例1
输入
5 3
1 2 3 4 5
1 3 5
输出
9

注意：
A题是签到题。

实践代码：

void solve(){
    int n,m;cin>>n>>m;
    int sum=0;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<m;i++){
        int x;cin>>x;
        sum+=a[x];
    }
    cout<<sum;
}

小A的游戏

题目：
小A和小B在玩一个游戏，每局游戏的结果可能有胜平负三种。游戏的胜者得到 3 分，败者不得分，若打平则双方都得 1 分。
现在他们进行了若干局游戏，比分记录着小A为 X 分，小B为 Y 分。由于持续的时间太长了，他们不确定记录的比分是否是正确的了，请你来判断一下此时的比分是否合法吧。

输入描述:

多组测试。
第一行一个正整数
T(1≤T≤103) ，表示测试数据组数。
接下来 T 行，每行两个整数 X 和 Y(0≤X,Y≤109) ，分别表示比分所记录的小A和小B的分数。
小红希望你判断她的输出是否符合要求，你能帮帮她吗？

输出描述:

对于每组测试，如果合法输出一行 “Yes” ，否则输出 “No”（均不包含引号）。

示例1
输入
3
1 3
3 3
4 15
输出
No
Yes
No

注意：
B题贪心。

实践代码：

void solve(){
    int x,y;cin>>x>>y;
    int ans=abs(x-y);
    if(ans%3==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

小A的数字

题目：
小A给定一个数字 n ，请你帮她找出从低位对齐后任意一位均与 n 对应数位不同的最小正整数。
对于本题题面描述中的从低位对齐后任意一位均与 n 对应数位不同，你需要保证你所输出的答案的位数小于 n 的位数时，即使在添加前导零至与 n 的位数相同后，也不应有任意一位的数字两两相同。

输入描述:

多组测试。
第一行一个正整数 T(1≤T≤103) ，表示测试数据组数。 对于每组测试数据，一行一个不含前导零的整数
n(2≤n≤109) ，表示所给的数字。

输出描述:

对于每组测试，输出一行一个正整数表示答案。

示例1
输入
3
2
10
101
输出
1
1
10

注意：
C题，分为两种情况(n中包含0和不包含0的情况)和一种特殊情况(n只有一位)。如果包含0就找数字n从左向右第一次出现0的位数是在哪一位，然后将此位设置为1，(左边的默认为前导0，所以一定不会跟n在此位左边的任何一位有相同数字)然后从此位开始往右边位数找：遇1变0，遇除1以外其他数(0,2…9)变1；如果不包含0就只管个位数就行(其他位补充前导0即可)；如果n只有个位数，则遇1变2(题目中要求最小正整数)，遇除1以外其他数变1。本题用字符串处理比较方便。
举个栗子：
n：2103842
ans：10000

实践代码：

void solve(){
    string s,t;cin>>s;
    if(s.length()==1){
        if(s[0]=='1') {cout<<2<<endl;return;}
        cout<<1<<endl;return;
    }
    if(s.find("0")==string::npos){
        if(s[s.length()-1]=='1') {cout<<2<<endl;return;}
        cout<<1<<endl;return;
    }
    for(int i=0;i<s.length();i++){
        if(s[i]=='0') t+="1";
        else if(s[i]!='0') {t+="0";}
    }
    int pos;
    for(int i=0;i<t.length();i++){
        if(t[i]=='0') continue;
        else {pos=i;break;}
    }
    for(int i=pos;i<t.length();i++) cout<<t[i];
    cout<<endl;
}

小A的线段（easy version）

题目：

本题为 easy version ，与 hard version 的区别仅为 m 的数据范围。

在一个标有 1−n 的数轴上给定 m 条线段，第 i 个线段的左右端点分别为 sti，edi ，求有多少种线段的选择方案可以使得数轴上的每个整数点至少被覆盖两次。

定义两种选择方案不同当且仅当至少有一个线段在两种方案中的状态（选/不选）不同。

由于方案数可能很多，所以你需要输出满足条件的方案数对 998244353 取模的结果。

输入描述:

第一行两个正整数 n(2≤n≤105) 和 m(1≤m≤10) ，分别表示数轴长度和线段个数。 接下来 m 行，每行两个正整数，其中第
i 行的两个正整数 sti 和 edi​ (1≤sti​<edi≤n) 分别表示第 i 条线段的起点和终点。

输出描述:

输出满足条件的方案数对 998244353 取模的结果。

示例1
输入
5 4
4 5
1 5
3 5
1 4

输出
3

注意：
D题是一个典型的dfs+差分。

实践代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define PII pair<int,int>
const int N = 1e5+10;
const int mod = 1e9+7;
int n,m,ans=0,use[12],l[12],r[12],a[N];//方案数ans,记录是否使用该线段use,左端点l，右端点r,差分数组a
void dfs(int now){
    if(now==m+1){//搜索到一条分枝的尽头
        memset(a,0,sizeof(a));
        for(int i=1;i<=m;i++){
            if(use[i]) {a[l[i]]++;a[r[i]+1]--;}//如果选了第i个线段,就用差分数组将两个端点包含的区间+1
        }
        int f=1;//f用来检查是否存在不满足要求的情况
        for(int i=1;i<=n;i++){
            a[i]+=a[i-1];//求差分数组的前缀和
            if(a[i]<2) f=0;//不满足数轴上每个整数点至少被覆盖2次的要求，将f置为0
        }
        if(!f) return;
        ans++;return;//都满足要求的，方案数ans+1
    }
    use[now]=1;//如果选now这条线段
    dfs(now+1);
    use[now]=0;//如果不选now这条线段
    dfs(now+1);

}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>l[i]>>r[i];
    dfs(1);
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(2);//保留两位小数
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

小A的任务

题目：

小A现在需要完成有序的 A 类任务和 B 类任务各 n 个，初始时只有第 1 个 A 类任务可以进行。进行第 i 个 A 类任务需在完成第 i − 1 个 A 类任务之后，进行第 i 个 B 类任务需要在完成第 i 个 A 类任务之后。且在同一时刻只能进行 A 类和 B 类中的一类任务，同一类的任务只能同时进行一个，任何一个任务都至多完成一次。
总共有 q 次询问，每次询问你需要回答完成 k 个 B 类任务至少需要多长时间。

输入描述:

第一行两个整数 n(1≤n≤105) 和 q(1≤q≤100) ，分别表示任务个数与询问次数。

第二行 n 个整数，其中第 i 个数字 (1≤ai ≤109 ) 表示完成第 i 个 A 类任务所需要的时间。第三行 n 个整数，其中第 i 个数字 (1≤bi≤109) 表示完成第 i 个 B 类任务所需要的时间。

接下来 q 行，每行一个整数 k(1≤k≤n) ，表示询问。
输出描述:
对于每次询问，输出一行一个整数，表示询问结果。
示例1
输入
4 3
1 2 3 4
4 1 2 3
1
2
3
输出
4
8
13
示例2
输入
5 2
19 1 20 2 17
12 20 17 4 2
3
5
输出
75
114

备注
对于样例一的第一个询问，需要先完成前 2 个 A 类任务，再完成第 2 个 B 类任务。

注意：
E题优先队列+枚举

实践代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f//long long 1e19
#define PII pair<int,int>
const int N = 1e5+10;
const int mod = 1e9+7;
vector<int> a(N),b(N);
void solve(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];//A类任务
    for(int i=1;i<=n;i++) cin>>b[i];//B类任务
    int k;
    while(q--){
        cin>>k;
        priority_queue<int> qe;//大根堆(优先队列)，存储当前b任务中最小的k个任务
        int ans=INF,sum=0,qesum=0;//当前优先队列中k个元素的总和qesum
        for(int i=1;i<=n;i++){
            sum+=a[i];//a类任务时间直接加
            qe.push(b[i]);qesum+=b[i];//将b任务的第i个存进优先队列
            if(qe.size()>k) {qesum-=qe.top();qe.pop();}
            //此时优先队列的元素个数大于k，那么qesum就减去当前优先队列中最大的元素(用较小的元素替换最大的元素)，保证所用时间最少
            if(qe.size()==k) ans=min(ans,sum+qesum);//记录做到当前k个b任务时的最优解(所用时间最少)
        }
        cout<<ans<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(2);//保留两位小数
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

小A的线段（hard version）

题目：

本题为 easy version ，与 hard version 的区别仅为 m 的数据范围。

在一个标有 1−n 的数轴上给定 m 条线段，第 i 个线段的左右端点分别为 sti，edi ，求有多少种线段的选择方案可以使得数轴上的每个整数点至少被覆盖两次。

定义两种选择方案不同当且仅当至少有一个线段在两种方案中的状态（选/不选）不同。

由于方案数可能很多，所以你需要输出满足条件的方案数对 998244353 取模的结果。

输入描述:

第一行两个正整数 n(2≤n≤105) 和 m(1≤m≤200) ，分别表示数轴长度和线段个数。 接下来 m 行，每行两个正整数，其中第
i 行的两个正整数 sti 和 edi​ (1≤sti​<edi≤n) 分别表示第 i 条线段的起点和终点。

输出描述:

输出满足条件的方案数对 998244353 取模的结果。

示例1
输入
5 4
4 5
1 5
3 5
1 4

输出
3

注意：
F题跟D题的区别是m的范围，难度直接max。需要离散化+特判
在这里插入图片描述

实践代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
const int N = 1e5+10;
const int mod = 998244353;
int dp[404][404][404];
void add(int &x,int y){//相加取模
    x+=y;
    if(x>mod)x-=mod;//直接传x的值回本身
}
void solve(){
        int n,m;
        cin>>n>>m;
        vector<int>alls,s,t;
        vector<PII>a(m+1);
        for(int i=1;i<=m;i++){//将坐标点离散化
            cin>>a[i].first>>a[i].second;
            --a[i].first;//防止起点和终点重合误判，只要线段右端大于线段左端
            alls.push_back(a[i].first);//将点压入点的集合
            alls.push_back(a[i].second);
        }
        alls.push_back(0),alls.push_back(n);//还有0和n
        sort(alls.begin(),alls.end());//进行排序形成数轴
        alls.erase(unique(alls.begin(),alls.end()),alls.end());//删除重复的的点
        //用到unique函数，来去重
        auto get =[&](int x)->int{//定义一个函数参数为x,返回大于等于该数的值
            return lower_bound(alls.begin(),alls.end(),x)-alls.begin();//返回坐标
        };//不为普通函数，能在alls函数中找值
        //用lower_bound应该是前面减了1吧
        for(int i=1;i<=m;i++){
            auto [s,t]=a[i];//将a[i]装入s,t数组
            a[i]={get(s),get(t)};//再在alls中找相应的点的坐标
        }
        sort(a.begin(),a.end());//a数组值对应all点的下标
        n=alls.size();//离散点总点数
        dp[0][0][0]=1;//状态定义，dp[i][l][k]l表示0到l至少被覆盖两次，l到r表示被覆盖一次，r到n表示没有被覆盖
        //当l为0,r为0时，表示初始默认0被覆盖两次，初始状态就有一种情况，此时有0个线段
        for(int k=1;k<=m;k++){//表示m条线段
            for(int i=0;i<=n;i++){//表示l
                for(int j=i;j<n;j++){//表示r
                    add(dp[k][i][j],dp[k-1][i][j]);//先将前面的线段值赋给现在状态
                    if(a[k].first<=i){//当当前线段的左端点小于l时满足状态条件
                        add(dp[k][max(i,min(j,a[k].second))][max(j,a[k].second)],dp[k-1][i][j]);
                        //l值为线段右端点与k比较大小后判断哪个点更近，近的之前表示覆盖两次以上
                        //然后和标记覆盖两次以上的i进行大小比较更新大的那一个作为状态
                        //加上没有这个线段的时候
                    }
                }
            }
        }
        cout<<dp[m][n-1][n-1]<<"\n";
     
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(2);//保留两位小数
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

心有猛虎，细嗅蔷薇。再见了朋友~

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

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

相关文章

【鸿蒙 HarmonyOS】获取设备的地理位置

【鸿蒙 HarmonyOS】获取设备的地理位置

一、背景 获取移动设备的地理位置&#xff0c;包含&#xff1a;经度、维度、具体地理位置等&#xff0c;地理位置信息能在许多业务场景中被应用&#xff0c;如导航、地图服务、位置服务、社交媒体等。 下面以一个Demo例子&#xff0c;来实现获取设备地理位置的功能 官方文档…
阅读更多...
无头单向非循环链表的实现

无头单向非循环链表的实现

1.链表的结构 在用代码实现之前&#xff0c;我们要先了解这种链表的逻辑结构和物理结构&#xff0c; 在逻辑上我们能知道这种链表能够通过前一个节点的 next 来存储下一个节点的地址&#xff0c;从而能够找到下一个数据&#xff0c;这就是一种线性结构&#xff0c;我们可以把数…
阅读更多...
智能感应门改造工程

智能感应门改造工程

今天记录一下物联网专业学的工程步骤及实施过程 智能感应门改造工程 1 规划设计1.1 项目设备清单1.2项目接线图 软件设计信号流 设备安装与调试工程函数 验收 1 规划设计 1.1 项目设备清单 1.2项目接线图 软件设计 信号流 设备安装与调试 工程函数 工程界面: using System; …
阅读更多...
循环队列的实现及应用——桶排序bucket_sort、基数排序radix_sort

循环队列的实现及应用——桶排序bucket_sort、基数排序radix_sort

一、循环队列的实现 代码解释 1、完成初始化 2、定义方法 3、测试实例 4、完整代码 class AQueue:def __init__(self, size=10):self.__mSize = sizeself.__front=0self.__rear = 0self.__listArray = [None] * size#清空元素def clear(self):self.__front = 0self.__rear =…
阅读更多...
腾讯游戏革命：手游内400+AI角色个性化成长，成本削减90%｜TodayAI

腾讯游戏革命：手游内400+AI角色个性化成长，成本削减90%｜TodayAI

在全球游戏开发者大会&#xff08;GDC&#xff09;上&#xff0c;腾讯游戏以一场技术革新的展示&#xff0c;震撼了整个游戏界。最令人瞩目的是&#xff0c;《火影忍者》手游中包含了超过400个AI角色&#xff0c;每个角色都拥有独特的个性。这一成就得益于腾讯新开发的大规模强…
阅读更多...
江协科技STM32：TIM输出比较

江协科技STM32：TIM输出比较

输出比较模块的主要功能&#xff1a;输出一定频率和占空比的PWM波形 CC是捕获比较的意思,R是Register&#xff0c;寄存器的意思&#xff0c;CCR捕获比较寄存器它是输入捕获和输出比较共用的 当使用输入捕获&#xff0c;它就是捕获寄存器 当使用输出比较&#xff0c;它就是比…
阅读更多...
RK3588 NPU 研究（二）

RK3588 NPU 研究（二）

RK提供了两个模型&#xff0c;mobilenet和YOLO5。 mobilenet模型相对小&#xff0c;使用起来不是很明显yolo5模型大一些&#xff0c;可以对88种目标进行检测&#xff0c;提供检测的结果包括类别、包围框坐标、可信度等信息。基于rknn_yolov5_demo进行分析。 rknn_yolov5_demo基…
阅读更多...
Vue3全家桶和小兔鲜儿案例

Vue3全家桶和小兔鲜儿案例

查看node.js版本&#xff0c;需要是16.0以上版本 node -v创建一个vue应用 npm init vuelatest在windows窗口中进入vs code命令 code ./创建项目后vs code打开安装依赖 npm install安装好以后运行程序 打开页面 deep有性能损耗&#xff0c;尽量不开启deep 生命周期函数指…
阅读更多...
记录Linux系统中vim同时开多个窗口编辑文件

记录Linux系统中vim同时开多个窗口编辑文件

在使用Linux进行文本编辑的时候&#xff0c;通常使用vim编辑器编辑文件&#xff0c;当然啦&#xff0c;vim也可以创建文件&#xff0c;如果只是一个一个创建&#xff0c;只需要vim创建即可&#xff0c;但是如何一次性打开多个窗口编辑呢&#xff1f; 目录 1、目标&#xff1a;…
阅读更多...
Unity和Android的交互

Unity和Android的交互

Unity和Android的交互 一、前言二、Android导出jar/aar包到Unity2.1 版本说明2.2 拷贝Unity的classes.jar给Android工程2.2.1 classes.jar的位置2.2.2 Android Studio创建module2.2.3 拷贝classes.jar 到 Android工程并启用 2.3 编写Android工程代码2.3.1 创建 MainActivity2.…
阅读更多...
springboot之mybatisPlus多表查询及分页查询

springboot之mybatisPlus多表查询及分页查询

文章目录 一、多表查询二、mybatis-plus条件查询三、分页查询 一、多表查询 可能会用到的注解 这里的场景是&#xff0c;查询每个用户及其所有的订单。就是查询你的id号的同时&#xff0c;把你所有的历史订单信息都拉出来。 表结构这样 CREATE TABLE User ( id INT PRIMARY…
阅读更多...
docker笔记（一）：安装、常用命令

docker笔记（一）：安装、常用命令

一、docker概述 1.1docker为什么会出现 各种环境配置十分繁琐&#xff0c;每一个机器都需要配置环境&#xff0c;难免出现各种问题。 发布一个项目jar需要配置&#xff08;MySQL、redis、jdk、…&#xff09;&#xff0c;项目不能都带上环境安装打包&#xff1a; 传统&…
阅读更多...
PostgrerSQL基本使用与数据备份

PostgrerSQL基本使用与数据备份

前言 上篇了解了 PostgrerSQL 数据库的部署PostgreSQL关系型数据库介绍与部署-CSDN博客&#xff0c;本篇将继续就其基本操作、备份与还原内容做相关介绍。 目录 一、数据库的操作 1. 本机登录 2. 开启远程登录 2.1 开放远程端口 2.2 编辑配置文件 2.3 修改配置密码 2.…
阅读更多...
前端三剑客 —— JavaScript （第一天）

前端三剑客 —— JavaScript （第一天）

目录 回顾内容 1.弹性布局 2.网格布局 JavaScript 概述 发展 浏览器 什么是Javascript JavaScript 能干什么 JavaScript需要的环境 JavaScript初体验 基本数据 JS书写方式 行内JS 页面JS 外部JS 1&#xff09;创建外部JS文件 2&#xff09;编写页面 对话框 警…
阅读更多...
【踩坑日记】因不同系统换行符不同导致的文本读取结果不同的问题

【踩坑日记】因不同系统换行符不同导致的文本读取结果不同的问题

文章目录 1 问题现象描述2 解决过程&#xff08;点击直接跳到解决方法&#xff09;3 原因解释4 如何避免踩坑4.1 格式转换4.2 格式查看 1 问题现象描述 起因是群友问了这么一个问题 确实很奇怪&#xff0c;按理说第二个printf不会完全不输出&#xff0c;于是想到&#xff0c;…
阅读更多...
C++数据结构与算法——回溯算法组合问题

C++数据结构与算法——回溯算法组合问题

C第二阶段——数据结构和算法&#xff0c;之前学过一点点数据结构&#xff0c;当时是基于Python来学习的&#xff0c;现在基于C查漏补缺&#xff0c;尤其是树的部分。这一部分计划一个月&#xff0c;主要利用代码随想录来学习&#xff0c;刷题使用力扣网站&#xff0c;不定时更…
阅读更多...
SD-WAN如何解决更有性价比地跨境网络问题

SD-WAN如何解决更有性价比地跨境网络问题

云桥通SD-WAN利用智能路由和负载均衡技术&#xff0c;优化数据传输路径&#xff0c;提高网络性能和可靠性。这意味着数据在跨国传输时可以更快到达目的地&#xff0c;减少延迟和丢包率。跨境SD-WAN提高了网络连接速度和质量&#xff0c;使用户能够更快地访问跨国业务所需的资源…
阅读更多...
索引的概念

索引的概念

索引的概念    1.索引是一种可选的与表相关的数据库对象&#xff0c;用于提高数据的查询效率。    2.索引是一种有序的数据结构。    3.如果一个表没有创建索引&#xff0c;则对该表进行查询时需要进行全表扫描&#xff1b;如果创建了索引&#xff0c;则在有条件查询时…
阅读更多...
应用性能分析工具CPU Profiler

应用性能分析工具CPU Profiler

简介 本文档介绍应用性能分析工具CPU Profiler的使用方法&#xff0c;该工具为开发者提供性能采样分析手段&#xff0c;可在不插桩情况下获取调用栈上各层函数的执行时间&#xff0c;并展示在时间轴上。 开发者可通过该工具查看TS/JS代码及NAPI代码执行过程中的时序及耗时情况…
阅读更多...
福州装修答疑 | 飘窗能不能砸掉？福州中宅装饰，福州装修

福州装修答疑 | 飘窗能不能砸掉？福州中宅装饰，福州装修

装修中的飘窗是一种常见的装饰元素&#xff0c;它不仅可以增加室内的采光和通风效果&#xff0c;还能为居室增添一份雅致和温馨。然而&#xff0c;很多业主在装修中都会遇到一个共同的问题&#xff1a;装修中的飘窗到底能不能砸&#xff1f;什么情况下可以砸&#xff1f;什么情…
阅读更多...
最新文章

Copyright @ 2022~2023