牛客小白月赛90(A,B,C,D,E,F)

比赛链接

官方题解(视频)

这场偏思维,感觉好像没啥算法。E需要动态维护前 k k k 小,F是个离散化加dp,状态和递推方程比较 非常规,建议还是看一下涨涨姿势。


A 小A的文化节

思路:

签到

code:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=105;

int n,m,a[maxn];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int ans=0;
	for(int i=1,t;i<=m;i++){
		cin>>t;
		ans+=a[t];
	}
	cout<<ans;
	return 0;
}

B 小A的游戏

思路:

只有两种加分方式,一种是一个人加 3 3 3 分,另一个人加 0 0 0 分,一种是两人各加 1 1 1 分.。

发现如果没有平局的话,两人分数一定是 3 3 3 的倍数,加入平局后,两人分数的差值仍然是 3 3 3 的倍数。反过来,如果分数的差值是 3 3 3 的倍数的话,就可以凑出来某人赢了几场,平了几场,输了几场。换句话说,就是两人分数之差为 3 3 3 的倍数=有解。

code:

#include <iostream>
#include <cstdio>
using namespace std;

int T,a,b;

int main(){
	cin>>T;
	while(T--){
		cin>>a>>b;
		puts((abs(a-b)%3==0)?"Yes":"No");
	}
	return 0;
}

C 小A的数字

思路:

看半天以为是二进制位,结果是十进制位。。。

当然是尝试贪心地将每个数位都置为 0 0 0,如果本来就是 0 0 0 就置为 1 1 1。因为要求是正整数,所以结果为 0 0 0 的时候还需要特判。

code:

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

int T,n;

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		int flag=n%10;
		stack<int> s;
		while(n){
			s.push((n%10)?0:1);
			n/=10;
		}
		while(!s.empty() && s.top()==0)s.pop();
		if(s.empty()){
			if(flag==1)s.push(2);
			else s.push(1);
		}
		
		while(!s.empty()){
			cout<<s.top();
			s.pop();
		}
		cout<<endl;
	}
	return 0;
}

D 小A的线段(easy version)

思路:

因为 m ≤ 10 m\le 10 m10 很小,所以直接暴力枚举选取线段的情况,然后逐一验证即可。

验证的时候可以用差分来优化。

code:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=15;

int n,m;
int st[maxn],ed[maxn];

bool check(int sta){
	vector<int> a(n+5);
	for(int i=0;i<m;i++){
		if(sta>>i&1){
			a[st[i]]++;
			a[ed[i]+1]--;
		}
	}
	for(int i=1;i<=n;i++){
		a[i]+=a[i-1];
		if(a[i]<2)return false;
	}
	return true;
}

int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++)cin>>st[i]>>ed[i];
	
	int ans=0;
	for(int i=0;i<(1<<m);i++)
		ans+=check(i);
	cout<<ans;
	return 0;
}

E 小A的任务

思路:

因为我们选了所有前 i i i A A A 任务,才有资格去前 i i i B B B 任务中选任务,一开始的想法是 d p dp dp。第 i i i 个任务我们可以只选一个 A A A 任务,或者同时选择一个 A A A 任务和相应的 B B B 任务,设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 个任务选 j j j B B B 任务的最小时间,转移方程为 d p [ i ] [ j ] = m i n { d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] + B i } + A i dp[i][j]=min\{dp[i-1][j],dp[i-1][j-1]+B_i\}+A_i dp[i][j]=min{dp[i1][j],dp[i1][j1]+Bi}+Ai。不过这样转移时间复杂度是 O ( n 2 ) O(n^2) O(n2) 的,因为它会同时处理出前 i i i 个任务中选择 0 ∼ i 0\sim i 0i B B B 任务的最小代价,因此时间复杂度降不下来,大部分数据我们根本用不到。

考虑其他做法,发现如果我们决定只做前 i i i A A A 任务后,我们做 k k k B B B 任务一定是做前 i i i 个中用时最小的 k k k 个任务。这么做的好处是我们可以使用一个堆来动态维护住前 i i i B B B 任务中最小的 k k k 个用时,这样我们跑一遍下来就得到了 i i i k ∼ n k\sim n kn 所有情况下 B B B 任务的选取情况,也就得到了最小的用时。验证一遍的时间复杂度是 O ( n ∗ l o g k ) O(n*logk) O(nlogk) 的,总时间复杂度应该是 O ( n ∗ q ∗ l o g k ) O(n*q*logk) O(nqlogk),运算次数约为 1 0 5 ∗ 100 ∗ l o g ≈ 2 ∗ 1 0 8 10^5*100*log\approx2*10^8 105100log2108,时限有 3 s 3s 3s ,可以通过。

code:

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;

int n,q;
int a[maxn],b[maxn];

ll solve(int k){
	ll tot=0,ans;
	priority_queue<int> h;
	for(int i=1;i<=k;i++){
		tot+=a[i];
		tot+=b[i];
		h.push(b[i]);
	}
	ans=tot;
	for(int i=k+1;i<=n;i++){
		tot+=a[i];
		if(b[i]<h.top()){
			tot-=h.top();
			h.pop();
			tot+=b[i];
			h.push(b[i]);
			ans=min(ans,tot);
		}
	}
	return ans;
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	
	while(q--){
		int k;
		cin>>k;
		cout<<solve(k)<<endl;
	}
	return 0;
}

F 小A的线段(hard version)

思路:

不难发现其实区间里很多位置其实都是没啥用的。 1 0 5 10^5 105 个位置被 200 200 200 个线段分成了 400 400 400 多个段,段内的所有位置其实没啥用,我们其实可以直接把这些段看成一个点,一个位置。这样离散化一下, 1 0 5 10^5 105 个位置就变成了 400 400 400 多个位置。

因为每个位置只要覆盖两次及以上就行了,所以每个位置我们可以看作只有三种状态:覆盖了零次,覆盖了一次,覆盖两次以上,每条线段可以将若干位置的状态进行变化,因此考虑动态规划。

d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 个位置覆盖了两次及以上,前 j j j 个位置覆盖了一次的选取线段方法数,为了前面状态不会出现断层(比如前面先覆盖了两次,然后后面变成覆盖一次,然后又变成覆盖了两次),我们对所有线段按左端点进行排序,然后按顺序取更新 d p dp dp 值即可(因为我们考虑了左端点在前 i i i 个位置的线段,那么前面的位置就必须都是覆盖了两次,否则后面更新 d p dp dp 也不可能更新状态,这样就保证了我们不需要考虑前面出现断层的情况,因为一定更新不了答案)。

官方题解给出的状态转移方程如下:
在这里插入图片描述
我写的时候没看题解,直接分类讨论的,思路是一样的。转移方程如下:

假设我们现在考虑到了第 k k k 个线段,线段左右端点分别为 l , r l,r l,r,设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 个位置覆盖了两次及以上,前 j j j 个位置覆盖了一次的选取线段方法数 ( l ≤ r , i ≤ j ) (l\le r,i\le j) (lr,ij)。于是有(箭头表示可以转移):

  1. d p [ k − 1 ] [ i ] [ j ] → d p [ k ] [ i ] [ j ] dp[k-1][i][j]\rightarrow dp[k][i][j] dp[k1][i][j]dp[k][i][j]
  2. l − 1 ≤ i ≤ j ≤ r l-1\le i\le j\le r l1ijr 时, d p [ k − 1 ] [ i ] [ j ] → d p [ k ] [ j ] [ r ] dp[k-1][i][j]\rightarrow dp[k][j][r] dp[k1][i][j]dp[k][j][r]
  3. l − 1 ≤ i ≤ r ≤ j l-1\le i\le r\le j l1irj 时, d p [ k − 1 ] [ i ] [ j ] → d p [ k ] [ r ] [ j ] dp[k-1][i][j]\rightarrow dp[k][r][j] dp[k1][i][j]dp[k][r][j]
  4. r < i ≤ j r\lt i\le j r<ij 时, d p [ k − 1 ] [ i ] [ j ] → d p [ k ] [ i ] [ j ] dp[k-1][i][j]\rightarrow dp[k][i][j] dp[k1][i][j]dp[k][i][j]

根据递推式,发现我们实际用的其实是 l − 1 l-1 l1,而不是 l l l,因为离散化后点与点之间相邻关系会被打破,比如 3 , 7 3,7 3,7 离散化后是 1 , 2 1,2 1,2,虽然离散化后 2 2 2 减一就等于 1 1 1,但这并不代表 7 7 7 减一就等于 3 3 3,所以我们离散化的时候直接对 l − 1 l-1 l1 离散化,而不是 l l l

另外就是 1 1 1 n n n 作为区间左右端点也要放入到离散化数组中去,左端点由于上面所有线段左端点都减一的影响,这里也要减 1 1 1,也就是说认为左端点是 0 0 0

code:

还能滚动数组优化,不过没写

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxm=205;
const ll mod=998244353;

int n,m;
vector<pii> itv;

vector<int> tmp;

int main(){
	cin>>n>>m;
	tmp.push_back(0);
	tmp.push_back(n);
	for(int i=1,l,r;i<=m;i++){
		cin>>l>>r;l--;
		tmp.push_back(l);
		tmp.push_back(r);
		itv.push_back(pii(l,r));
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	n=tmp.size();
	auto find=[&](int x)->int{return lower_bound(tmp.begin(),tmp.end(),x)-tmp.begin()+1;};
	for(auto& [l,r]:itv){
		l=find(l);
		r=find(r);
	}
	sort(itv.begin(),itv.end());
	
	vector<vector<vector<ll> > > dp(m+1,vector<vector<ll> >(n+1,vector<ll>(n+1,0)));
	dp[0][1][1]=1;
	for(int k=1;k<=m;k++){
		auto [l,r]=itv[k-1];
		for(int i=0;i<=n;i++)
			for(int j=i;j<=n;j++)
				dp[k][i][j]=dp[k-1][i][j];
		for(int i=0;i<=n;i++){
			for(int j=i;j<=n;j++){
				if(l<=i){
					if(i<=r){
						if(j<=r){
							dp[k][j][r]+=dp[k-1][i][j];
							dp[k][j][r]%=mod;
						}
						else {
							dp[k][r][j]+=dp[k-1][i][j];
							dp[k][r][j]%=mod;
						}
					}
					else {
						dp[k][i][j]+=dp[k-1][i][j];
						dp[k][i][j]%=mod;
					}
				}
			}
		}
		
	}
	cout<<dp[m][n][n]<<endl;
	return 0;
}

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

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

相关文章

我国量子信息科技创新发展面临的挑战及建议——基于中美对比视角的分析

2024年2月&#xff0c;中国科学技术发展战略院慕慧娟博士、丁明磊研究员及光子盒顾成建一起在《科技管理研究》上发表文章——《我国量子信息科技创新发展面临的挑战及建议&#xff1a;基于中美对比视角的分析》。 在此&#xff0c;我们整理并发布这篇文章&#xff0c;欢迎感兴…

springCloudAlibaba集成sentinel实战(超详细)

一、Sentinel介绍 1. 什么是Sentinel Sentinel是阿里开源的项目&#xff0c;提供了流量控制、熔断降级、系统负载保护等多个维度来保障服务之间的稳定性。 分布式系统的流量防卫兵&#xff1a; 随着微服务的普及&#xff0c;服务调用的稳定性变得越来越重要。Sentinel以“流…

实现创建线程的五种写法

创建线程的五种写法 1、通过继承Thread类并实现run方法创建一个线程package 创建线程;2、通过实现Runnable接口&#xff0c;并实现run方法的方法创建一个线程3、通过Thread匿名内部类创建一个线程4、通过Runnable匿名内部类创建一个线程5、通过Lambda表达式的方式创建一个线程 …

airtest-ios真机搭建实践

首先阅读4 ios connection - Airtest Project Docs 在Windows环境下搭建Airtest对iOS真机进行自动化测试的过程相对复杂&#xff0c;因为iOS的自动化测试通常需要依赖Mac OS系统&#xff0c;但理论上借助一些工具和服务&#xff0c;Windows用户也可以间接完成部分工作。下面是…

IP SSL证书免费申请教程(给IP地址开启https)

首先IP地址申请的前提&#xff1a;80端口有打开&#xff0c;或者可以短暂的打开10分钟左右等验证完IP管理权再关掉。 一&#xff1a;打开JoySSL官网选择IP地址证书并下单加入购物车&#xff0c;之后结账后就会跳转到证书申请界面。 二&#xff1a;填写需要申请证书的IP信息 三&…

【RV1106的ISP使用记录之一】基础环境搭建

公司缺少ISP工程师&#xff0c;做为图像算法工程师的我这就不就给顶上来了么&#xff0c;也没给发两份工资&#xff0c;唉~ 先写个标题&#xff0c;占一个新坑&#xff0c;记录RK平台的传统ISP工作。 一、基础环境的硬件包括三部分&#xff1a; 1、相机环境&#xff0c;用于采…

Python 网络爬虫技巧分享:优化 Selenium 滚动加载网易新闻策略

简介 网络爬虫在数据采集和信息获取方面发挥着重要作用&#xff0c;而滚动加载则是许多网站常用的页面加载方式之一。针对网易新闻这样采用滚动加载的网站&#xff0c;如何优化爬虫策略以提高效率和准确性是一个关键问题。本文将分享如何利用 Python 中的 Selenium 库优化滚动…

利用爬虫技术实现自动化数据分析

目录 前言 一、爬虫技术概述 二、自动化数据分析的步骤 1. 确定数据需求 2. 网页分析和定位 3. 编写爬虫程序 4. 数据存储和处理 5. 数据分析和可视化 三、示例代码 总结 前言 在信息时代&#xff0c;数据已成为重要的资源之一&#xff0c;并且随着互联网的发展&…

计算机网络——交换机和路由器

目录 前言 引言 交换机是用来做什么的&#xff1f; 与路由器有什么区别&#xff1f; 网关 子网掩码 网关、路由 前言 本博客是博主用于复习计算机网络的博客&#xff0c;如果疏忽出现错误&#xff0c;还望各位指正。 这篇博客是在B站掌芝士zzs这个UP主的视频的总结&am…

flutter跑通腾讯云直播Demo

运行示例 前提条件 要求java jdk 11版本 并且配置到了环境变量 重要 要求flutter 版本 2.8.0 并且配置到了环境变量 重要 要求dart-sdk版本2.15 并且配置到了环境变量 重要 您已 注册腾讯云 账号&#xff0c;并完成 实名认证。 申请 SDKAPPID 和 SECRETKEY 登录实时音视频控…

全栈开发医疗小程序 SpringBoot2.X + Vue + UniAPP 带源码

看到好多坛友都在求SpringBoot2.X Vue UniAPP&#xff0c;全栈开发医疗小程序 – 带源码课件&#xff0c;我看了一下&#xff0c;要么链接过期&#xff0c;要么课件有压缩密码。特意整理了一份分享给大家&#xff0c;个人认为还是比较全面的。希望对大家有所帮助&#xff01;…

FFmpeg: 简易ijkplayer播放器实现--04消息队列设计

文章目录 播放器状态转换图播放器状态对应的消息&#xff1a; 消息对象消息队列消息队列api插入消息获取消息初始化消息插入消息加锁初始化消息设置消息参数消息队列初始化清空消息销毁消息启动消息队列终止消息队列删除消息 消息队列&#xff0c;用于发送&#xff0c;设置播放…

探探各个微前端框架

本文作者为 360 奇舞团前端开发工程师 微前端架构是为了在解决单体应用在一个相对长的时间跨度下&#xff0c;由于参与的人员、团队的增多、变迁&#xff0c;从一个普通应用演变成一个巨石应用(Frontend Monolith)后&#xff0c;随之而来的应用不可维护的问题。这类问题在企业级…

全新华为MateBook X Pro发布,将Ultra9放入980g超轻薄机身

2024年4月11日&#xff0c;在华为鸿蒙生态春季沟通会上全新的华为MateBook X Pro正式发布。该机以美学设计、创新科技以及智慧体验&#xff0c;追求重新定义Pro、重新定义旗舰&#xff0c;将颠覆消费者对传统轻薄本的认知。 华为MateBook X Pro追求极致轻薄与强大性能的完美结合…

怎样将PDF转成PPT,有免费的工具吗?

PDF转换为PPT的需求在现代办公和学习中越来越常见。很多人可能遇到过需要将PDF文件中的内容转移到PPT中以方便编辑和展示的情况。幸运的是&#xff0c;现在市面上有许多工具可以帮助我们实现这一目标&#xff0c;而且其中不乏一些免费的选项。本文将详细介绍如何使用这些免费工…

linux学习:栈

目录 顺序栈 结构 初始化一个空顺序栈 压栈 出栈 例子 十进制转八进制 链式栈 管理结构体的定义 初始化 压栈 出栈 顺序栈 顺序栈的实现&#xff0c;主要就是定义一块连续的内存来存放这些栈元素&#xff0c;同时为了方便管理&#xff0c; 再定义一个整数变量来代表…

计算机基础知识-第9章-存储的本质(2)——硬盘和文件系统基础知识

一、机械硬盘的原理 概括来说&#xff0c;硬盘的工作原理是利用特定的磁粒子的极性来记录数据。磁头在读取数据时&#xff0c;将磁力子的不同极性转换成不同的电脉冲信号&#xff0c;再利用数据转换器将这些原始信号变成电脑可以使用的数据&#xff0c;写的操作正好与此相反。…

前端docker jenkins nginx CI/CD持续集成持续部署-实战

最近用go react ts开发了一个todolist后端基本开发完了,前端采用CI/CD方式去部署。 步骤总结 先安装docker 和 docker-compose。安装jenkins镜像,跑容器的时候要配好数据卷。配置gitee或github(我这里使用gitee)在服务器上一定要创建好dokcer的数据卷,以便持久保存jenkin…

Transformer模型-decoder解码器,target mask目标掩码的简明介绍

今天介绍transformer模型的decoder解码器&#xff0c;target mask目标掩码 背景 解码器层是对前面文章中提到的子层的包装器。它接受位置嵌入的目标序列&#xff0c;并将它们通过带掩码的多头注意力机制传递。使用掩码是为了防止解码器查看序列中的下一个标记。它迫使模型仅使用…

pytorch实现胶囊网络(capsulenet)

胶囊网络在hinton刚提出来的时候小热过一段时间&#xff0c;之后热度并没有维持多久。vision transformer之后基本少有人问津了。不过这个模型思路挺独特的&#xff0c;值得研究一下。 这个模型的提出是为了解决CNN模型学习到的特征之间没有空间上的关系&#xff0c;从而对于各…