当前位置: 首页 > news >正文

牛客小白月赛66

牛客小白月赛66_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

冒着期末挂科的风险打了打,缓解了一下网瘾,感觉还行

最近为了期末鸽了很多期的div3,一学期末就手痒想训,感觉再不打人要没了,结果就是预习期末也预习不进去,比赛也没打,这几天不知道在干什么,白白的浪费时间

19号才全部考完,还有8天才训练自由,md,心情非常不愉悦啊

A-先交换

小分类讨论

题意:

思路:

分类讨论即可

#include <bits/stdc++.h>
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
using namespace std;int n;
int a[mxn];
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ok=0;for(int i=2;i<=n;i++){if(a[i]<a[1]&&a[i]%2==1) ok=1;}if(a[1]%2==1) cout<<0<<'\n';else if(ok&&a[1]%2==0) cout<<1<<'\n';else cout<<-1<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}

B-再交换

构造+小分类讨论

题意:

思路:

构造题,交换的两个数的位置一定是特殊的,考虑i=j的情况进行交换,这样就是小分类讨论

注意特判的情况,当两个串串完全相同时,不代表无解,还可以交换别的数来满足条件

在a数组找到第一个不是最小值的数,在b数组找到最后一个最小值,进行交换即可

#include <bits/stdc++.h>
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
using namespace std;int n;
string s,t;
void solve(){s.clear(),t.clear();cin>>n;cin>>s>>t;s=" "+s;t=" "+t;int mi=1e9;for(int i=1;i<=n;i++){mi=min(mi,s[i]-'a'+1ll);if(s[i]==t[i]) continue;else if(s[i]<t[i]){if(i==n) cout<<1<<" "<<1<<'\n';else cout<<n<<" "<<n<<'\n';return;}else{cout<<i<<" "<<i<<'\n';return;}}int ansi;for(int i=n;i>=1;i--){if(t[i]-'a'+1==mi){ansi=i;break;}}int p=1;while(s[p]-'a'+1==mi) p++;if(p!=1) cout<<p<<" "<<p-1<<'\n';else{cout<<1<<" "<<ansi<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}

C-空洞骑士

构造+大(小)分类讨论

思路:

首先这题是让我们构造位置,那位置肯定是特殊的

考虑一个0到1e9的数轴,中间的金币是随机分配的,我们只需要记录第一个金币和最后一个金币的位置,然后去考虑起点s的位置

三种情况:

s=0

s=中间某个位置

s=1e9

画个图就可以发现,s为中间那个位置的贡献一定比另外两种小

如果s在中间,贡献差不多就是1.5个p_end-p_start,但是如果s=0或1e9,贡献显然>2*(p_end-p_start),所以第二种情况可以直接淘汰了

那么讨论另外两种情况,然后算一算贡献就行

当s=0时,t取1e9或1,两种情况算贡献取大的那个

当s=1e9,t=1e9-1或1,两种情况算贡献取大的那个

我自己在写的时候把中间的那种情况也算进去了,但是不影响ac

#include <bits/stdc++.h>
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
const int end_p=1000000000;
using namespace std;int m;
int p[mxn];
void solve(){cin>>m;int p_mx=-1e9,p_mi=1e9;for(int i=1;i<=m;i++){cin>>p[i];p_mx=max(p_mx,p[i]);p_mi=min(p_mi,p[i]);}sort(p+1,p+1+m);int mx=-1e9,ansi;for(int i=1;i<=m;i++){if(mx<min(p_mx-p[i],p[i]-p_mi)){mx=min(p_mx-p[i],p[i]-p_mi);ansi=p[i];}}int a1=max(p_mx+p_mx-1ll,(long long)1e9);int a3=((1e9-1)-p_mi>p_mi?(1e9-1)-p_mi:p_mi)+1e9-p_mi;int a2=min(p_mx-ansi,ansi-p_mi)+p_mx-p_mi+(p_mx-ansi<ansi-p_mi?p_mi:1e9-p_mx);int ans_a=max(max(a1,a2),a3);//cout<<a3<<'\n';if(ans_a==a1){if(p_mx-1>1e9-p_mx) cout<<0<<" "<<1<<'\n';else cout<<0<<" "<<end_p<<'\n';}else if(ans_a==a2){if(p_mx-ansi<ansi-p_mi) cout<<ansi<<" "<<0<<'\n';else cout<<ansi<<" "<<end_p<<'\n';}else{if(1e9-1-p_mi>p_mi) cout<<end_p<<" "<<end_p-1<<'\n';else cout<<end_p<<" "<<0<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

D-障碍

枚举+前缀和

题意:

思路:

这道题只需要注意到x的取值范围,那么就很好做了,关键是比赛的时候还注意不到

L最大取2e5,那么x最大就是500,如果超过500那么答案就会是负的

遇到小数据,我们考虑暴力枚举就好了

去枚举拿掉多少个障碍,然后去维护最大的答案值

#include <bits/stdc++.h>
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
using namespace std;int n,m,x;
int a[mxn];
void solve(){cin>>n>>m;for(int i=1;i<=m;i++) cin>>a[i];a[0]=0,a[m+1]=n;int ans=-1e9;for(int len=0;len<=500;len++){for(int l=0;l<=m;l++){int r=l+len+1;ans=max(ans,a[r]-a[l]-len*len);}}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

E生成树与路径

图论+构造

题意:

思路:

关于图论的构造还没怎么写过

这道题的构造条件是:

1.n个点,m条边

2.最小生成树的大小是最短路大小

3.特殊条件是边是个排列

对于第一个条件,考虑构造1到n的一条链,并边长是1-n-1,这样就满足了第一个条件

然后因为要m条边,所以我们要继续连边,但是在连边的过程中要保证第一个条件

我们考虑这样连边:

#include <bits/stdc++.h>
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
using namespace std;int n,m,u,v,idx=0;
void solve(){idx=0;cin>>n>>m;for(int len=2;len<=n;len++){for(int l=1;l+len-1<=n;l++){int r=l+len-1;cout<<l<<" "<<r<<" "<<++idx<<'\n';if(idx==m) return;}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}

F-球球大作战

贪心+反证法(?)+二分

题意:

思路:

我们要求的是,对于一个球,是否存在一种方法使得这个球作为最终的胜利者

首先是一个结论:其他n-1个球自相残杀之后,再和这个球去碰撞,这样这个球是最大值

证明:

反证法,如果该球和其他任意一个球撞击:

若这个球比较小,直接输掉

若这个球比较大,权值变成(a1+a2)/2,且a2<a1,所以权值不会变大,证毕

那么,其他n-1个球该怎么去撞可以最小化这n-1个球碰撞后的值呢,求出最好情况就可以看是否存在解法了

另一个结论就是:

这n-1个球从小到大排好序之后最大值和次大值碰撞可以使n-1个值碰撞之后的值最小

(另外n-1个球是无序的,所以可以考虑排序)

证明:

反证法:

考虑三个球,直接去计算它们的贡献:

注意到a1的贡献除了2,a2和a3的贡献除了4

因此先撞大的球会使贡献变小

证毕

如果我们就这样去枚举球,复杂度是O(n2)的,肯定T

但是对于两个球,如果权值较小的那个球都有解的可能性,那权值较大的一定有解

因为,权值较小的球,其他n-1个球碰撞之后的权值一定比除了那个权值较大的球其他n-1个球碰撞之后的权值来的大

所以满足了单调性,直接去二分刚好有解的权值的下标就好了,前提是数组排好序

#include <bits/stdc++.h>
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
using namespace std;int n,ans;
int a[mxn],b[mxn];
bool check(int x){int ans=a[n];for(int i=n-1;i>=1;i--){if(i==x) continue;ans+=a[i];ans/=2;}return ans<=a[x];
}
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];sort(a+1,a+1+n);int l=1,r=n;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}//cout<<ans<<'\n';int s=a[ans];for(int i=1;i<=n;i++){if(b[i]>=s) cout<<1;else cout<<0;}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

相关文章:

牛客小白月赛66

牛客小白月赛66_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)冒着期末挂科的风险打了打&#xff0c;缓解了一下网瘾&#xff0c;感觉还行最近为了期末鸽了很多期的div3&#xff0c;一学期末就手痒想训&#xff0c;感觉再不打人要没了&#xff0c;结果…...

加载sklearn新闻数据集出错 fetch_20newsgroups() HTTPError: HTTP Error 403: Forbidden解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。喜欢通过博客创作的方式对所学的知识进行总结与归纳,不仅形成深入且独到的理…...

图解LeetCode——剑指 Offer 53 - I. 在排序数组中查找数字 I

一、题目 统计一个数字在排序数组中出现的次数。 二、示例 示例 1 【输入】nums [5,7,7,8,8,10], target 8 【输出】2 示例 2: 【输入】nums [5,7,7,8,8,10], target 6 【输出】0 提示&#xff1a; 0 < nums.length < 10^5-10^9 < nums[i] < 10^9nums 是一…...

python 实现热门音乐分析 附代码+数据 +论文

项目概述: 本选取了抖音当下最热门的 400 首音乐,通过一系列方法提取每首歌的波形特征,再经过降维以及机器学习等手段,进行无监督学习对音乐数据进行聚类的同时训练并使用监督学习分类器进行音乐流派分类,并通过可视化方法呈现分类聚类效果。 关键词:特征提取,PCA 主成分…...

【2335. 装满杯子需要的最短总时长】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 现有一台饮水机&#xff0c;可以制备冷水、温水和热水。每秒钟&#xff0c;可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开始、长度为 3 的整数数组 amount &#xff0c;…...

再不跳槽,就晚了

从时间节点上来看&#xff0c;3月、4月是每年跳槽的黄金季&#xff01; 以 BAT 为代表的互联网大厂&#xff0c;无论是薪资待遇、还是平台和福利&#xff0c;都一直是求职者眼中的香饽饽&#xff0c;“大厂经历” 在国内就业环境中无异于一块金子招牌。在这金三银四的时间里&a…...

Java 内存结构解密

程序计数器 物理上被称为寄存器&#xff0c;存取速度很快。 作用 记住下一条jvm指令的执行地址。 特点 线程私有&#xff0c;和线程一块出生。 不存在内存溢出。 虚拟机栈 每个线程运行时所需要的内存&#xff0c;称为虚拟机栈。 每个栈由多个栈帧组成&#xff0c;…...

ROS小车研究笔记2/11/2023:使用ssh远程登录小车

1 SSH简介&#xff1a; SSH全称Secure Shell&#xff0c;是一种建立在应用层的安全网络协议。其安全性又非对称加密(RSA)实现 对称加密&#xff1a;使用同一密钥对信息进行加密和解密&#xff0c;但是一旦该密钥被窃取就会威胁通信安全 非对称加密&#xff1a;使用公钥和私钥。…...

koa ts kick off 搭建项目的基本架子

koa ts kick off 使用ts开发koa项目的基本架子&#xff0c;便于平时随手调研一些技术 项目结构 ├── src │ ├── controller //controller层 │ ├── service //service层 │ ├── routes.ts //路由 │ └── index.ts //项目入…...

h2database源码解析-查询优化器原理

目录一、成本计算规则二、单表查询三、多表关联查询一、成本计算规则 h2的查询优化器基于成本的&#xff0c;因此在执行查询前&#xff0c;会基于成本计算使用哪个索引&#xff0c;如果涉及多表关联&#xff0c;还会计算不同表关联顺序的成本&#xff0c;最终基于最小成本得出…...

2月11日,30秒知全网,精选7个热点

///国产邮轮首制船将于今年5月底出坞&#xff0c;年底交付 浦东新区近期将发布相关政策支持包括外高桥造船在内的船舶产业发展 ///首批个人养老金理财产品名单发布&#xff1a;3家机构7只产品 中国理财网发布的信息显示&#xff0c;首批个人养老金理财产品名单发布&#xff0…...

vue组件的构成 <template> <script> <style>节点的使用 <

1.vue组件组成结构 每个.vue组件都由3部分构成&#xff0c;分别是: template ->组件的模板结构script ->组件的JavaScript行为style ->组件的样式 其中&#xff0c;每个组件中必须包含template模板结构&#xff0c;而script行为和style样式是可选的组成部分。 2.组…...

windows + vscode + rust

1 安装VSCODE略2 安装rust插件1、说明&#xff1a;第4步本人是一个一个点击状态。上图禁用按钮在没装之前是显示“安装”按钮&#xff0c;应该点击“安装”也可以。2、还需要安装C插件&#xff0c;搜索C即可&#xff0c;装微软的3 创建rust工程由于初次使用&#xff0c;不知道目…...

二十九、异常处理

目录 ①前言: ②常见的运行时异常 ③常见的编译时异常 ④异常的处理机制 ⑤自定义异常 ①前言: 1.什么是异常&#xff1f; 异常是程序在“编译”或者“执行”的过程中可能出现的问题&#xff0c;注意&#xff1a;语法错误不算在异常体系中。 比如: 数据索引越界异常&…...

RTOS之二环境搭建初识RTOS

参考&#xff1a;https://blog.csdn.net/kouxi1/article/details/123650688视频&#xff1a;https://www.bilibili.com/video/BV1b14y1c783/RTOS本质就是切换线程栈&#xff0c;栈换了环境就换了&#xff0c;一个重要的结构tcb&#xff08;linux叫PCB或thread_info&#xff09;…...

【Java】 JAVA Notes

JAVA语言帮助笔记Java的安装与JDKJava命名规范JAVA的数据类型自动类型转换强制类型转换JAVA的运算符取余运算结果的符号逻辑运算的短路运算三元运算符运算符优先级JAVA的流程控制分支结构JAVA类Scanner类Math 类random方法获取随机数Java的安装与JDK JDK安装网站&#xff1a;h…...

Java笔记-volatile和AtomicInteger

目录1. volatile1.1.什么是volatile1.2.JMM-Java内存模型2 验证volatile的特性2.1 可见性2.2.验证volatile不保证原子性2.3 volatile实现禁止指令重排序3.使用AtomicInteger解决volatile的不能实现原子性的问题3.2 AtomicInteger的方法说明&#xff1a;3.3 CAS3.4 应用1. volat…...

[标准库]STM32F103R8T6 高级定时器--PWM输出和带死区互补PWM输出

前言 STM32F103系列的MCU&#xff0c;相比普通的51单片机&#xff0c;在输出硬件PWM这个功能上要强不少&#xff0c;两者实现的方式都类似&#xff0c;都是通过一个定时器来启用硬件PWM输出&#xff0c;不过在输出PWM通道的数量上&#xff0c;32F103要强上不少。仅通过一个高级…...

Camtasia2023最新版电脑视频录屏记录编辑软件

在Mac或Wind上有各种可用的视频记录和编辑软件&#xff0c;其中Camtasia被称为视频记录器和视频编辑器。录屏软件Camtasia2023到底有什么特色功能&#xff1f;本文将帮助您选择理想的选择来开始视频捕获&#xff0c;创建和编辑。Camtasia2023是Mac/win平台上一款使用非常简单的…...

管理用户安全性

每个数据库用户帐户都包括以下项&#xff1a;唯一的用户名验证方法 默认表空间临时表空间用户概要文件初始使用者组帐户状态验证用户口令验证、外部验证、全局验证管理员验证操作系统安全性&#xff1a;• DBA 必须具有创建或删除文件的操作系统权限。• 普通数据库用户不应具有…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...