刷题记录:牛客NC53370 Forsaken的三维数点
传送门:牛客
题目描述:
Forsaken现在在一个三维空间中,空间中每个点都可以用(x,y,z)表示。突然,三维空间的主人出现
了,如果Forsaken想要继续在三维空间中呆下去,他就必须回答三维空间主人的问题.主人会在空间
中坐标为(x,y,z)处加一点能量值,当他加了一定的次数之后,他会问Forsaken一个问题:如果坐标
(0,0,0)为球心,那么至少需要多大的半径才能使得球内的能量值总和大于或者等于
k,在这里,半径为0也是可以的。这对于Forsaken来说实在是太难了,因此他把这个问题交给了你。
输入:
2
1 1 1 1
2 1
输出:
2
一道权值线段树的题目,并且需要快速查询前缀和是否满足要求
和这道题维护方法相同,同样有两种方法,甚至比那道题要简单,因为本题并没有区间修改操作,不需要lazylazylazy,所以具体如何使用线段树维护方法在这里就不再赘述了
对于本题来说,我们发现我们输出的半径必须为整数(md,刚开始我还在想如何维护double类型的呢),那么对于一个介于aaa和bbb的小数,显然只有当我们的半径为bbb的时候才能将这个数加入我们的计数当中,所以对于每一个距离,我们都进行向上取整即可
需要注意的是,因为有000的存在,这就需要我们对于每一个距离都加111,然后在最后得到半径的时候将半径-1输出即可
下面是具体的代码部分(用的是直接查询,不是二分):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,sum;
}tree[maxn*4];
int n;
void pushup(int rt) {tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {return;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt) {if(tree[rt].l==pos&&tree[rt].r==pos) {tree[rt].sum+=1;return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) update(pos,ls);else update(pos,rs);pushup(rt);
}
int query(int l,int r,int rt,int k) {if(l==r) return l;int mid=(tree[rt].l+tree[rt].r)>>1;if(tree[ls].sum>=k) return query(l,mid,ls,k);else return query(mid+1,r,rs,k-tree[ls].sum);
}
int main() {n=read();build(1,180000,1);for(int i=1;i<=n;i++) {int opt=read();if(opt==1) {int x=read(),y=read(),z=read();double dist=__builtin_sqrt((double)x*x+(double)y*y+(double)z*z);int Dist=ceil(dist);update(Dist+1,1);}else {int k=read();if(tree[1].sum<k) {printf("-1\n");continue;}printf("%d\n",query(1,n,1,k)-1);}}return 0;
}
相关文章:
刷题记录:牛客NC53370 Forsaken的三维数点
传送门:牛客 题目描述: Forsaken现在在一个三维空间中,空间中每个点都可以用(x,y,z)表示。突然,三维空间的主人出现 了,如果Forsaken想要继续在三维空间中呆下去,他就必须回答三维空间主人的问题.主人会在空间 中坐标为(x,y,z)处…...

lombok的原理 和 使用
原理Lombok能以简单的注解形式来简化java代码,提高开发人员的开发效率。其实并没有改变字节码文件的任何内容,只是简化的程序员编写代码的方式。不使用lombok:使用lombok:lombok常用注解Setter :注解在类或字段&#x…...

UDP网络编程
UDP和TCP 前几节我们提到了计算机网络编程中的TCP编程,TCP和UDP都是计算机机网络通信的传输层中的传输协议,今天我们来学习计算机网络编程中的基于UDP传输协议的网络编程 首先我们要了解TCP和UDP的区别 它们是同属于计算机网络传输层的传输协议 TCP&…...
“合并区间”问题解析及其思考
合并区间题目以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。解析本题思路相对比较容易想先对各个区间按左…...
2023年理想新能源汽车核心部件解密
理想主要硬件清单(L9车型) 汽车结构 设置名称 规格 备注 价格 供应商 感知层...
C++ 将一个vector内容赋值给另一个vector,及swap与assign的区别
在本文中,我们将主要介绍5种将一个vector内容赋值给另一个vector的方式,顺便讨论下swap与assign的区别。 赋值 方式一、申明时赋值 vector<int> v2; v2.push_back(0); v2.push_back(1);vector<int> v1(v2); //声明方式二、使用assign赋值…...

PMP的价值有哪些?
我个人认为,考证只有两个出发点是正确的。一是为了提升自己或者满足自己的兴趣,另一个是和自己的职业规划相关。 比如,有同学想提升自己英语能力,可以考四六级,或者更厉害一点的考雅思、托福。比如,有的同…...

OnGUI label 控件||Unity 3D GUI教程||OnGUI Background Color 控件
Unity 3D Label 控件用于在设备的屏幕上创建文本标签和纹理标签,和Box 控件类似,可以显示文本内容或图片。Label 控件一般用于显示提示性的信息,如当前窗口的名称、游戏中游戏对象的名字、游戏对玩家的任务提示和功能介绍等。具体使用方法如下…...

从 JavaScript 中的数组中删除空对象
从数组中删除空对象: 使用 Array.filter() 方法遍历数组。将每个对象传递给 Object.keys() 方法并检查键的长度是否不等于 0。filter 方法将返回一个不包含空对象的新数组。 const arr [{}, {id: 1}, {}, {id: 2}, {}];const results arr.filter(element > {…...

【C++】AVL树和红黑树(插入和测试详解)
文章目录1、AVL树1.1 AVL树的插入1.2 总结与测试AVL树2、红黑树2.1 红黑树的插入2.2 红黑树的测试了解AVL树是为了了解红黑树,了解红黑树是为了更好的理解set和map。 1、AVL树 AVL树是在二叉搜索树的基础上进行了严格的平衡,能做到平衡的关键是通过平衡…...

Centos7 安装 Mysql 8.0.32,详细完整教程(好文章!!)
mysql5.7的安装方式参考之前的文章: centos7 安装 Mysql 5.7.27,详细完整教程(好文章!!)_HD243608836的博客-CSDN博客 一、检查mysql版本冲突 先检查是否已经存在mysql,若存在卸载࿰…...

Apache Beanutils为什么被禁止使用?
收录于热门专栏Java基础教程系列(进阶篇) 在实际的项目开发中,对象间赋值普遍存在,随着双十一、秒杀等电商过程愈加复杂,数据量也在不断攀升,效率问题,浮出水面。 问:如果是你来写…...

sql server执行md5加密的时候,字符串前带N和不带N的结果是不一样的
最近因为项目的需要,报表中需要对数据进行MD5加密,结果报表系统得出来的sql语句,字符串前都自动带了N,执行时,发现得到的结果跟在数据库中执行的sql(字符串不带N)得的值不一样,最后自…...
01Python编译器和编辑器下载
Python下载 通过python官网下载:https://www.python.org/因为python官网的服务器在国外,我们可以通过腾讯软件中心下载https://pc.qq.com/search.html#!keyword=python 腾讯软件中心下载请使用普通下载,其他什么下载会自动帮你下个电脑管家(没必要) python简单描述 python…...

CHAPTER 5 自动发现、自动注册、分布式监控、SNMP监控
自动发现与自动注册5.1 自动发现与自动注册5.1.1 简介5.1.2 两种模式5.2 自动发现--被动模式5.3 自动注册--主动模式5.4 分布式监控5.4.1 介绍5.4.2 配置zabbix proxy5.5 SNMP监控5.5.1 使用范围5.5.2 安装snmp程序5.5.3 配置snmp程序5.5.4 测试snmp5.5.5 在web界面进行配置5.1…...
P5311 [Ynoi2011] 成都七中
题目描述 给你一棵 nnn 个节点的树,每个节点有一种颜色,有 mmm 次查询操作。 查询操作给定参数 lrxl\ r\ xl r x,需输出: 将树中编号在 [l,r][l,r][l,r] 内的所有节点保留,xxx 所在连通块中颜色种类数。 每次查询操…...
Python 日期和时间格式
Python 程序能用很多方式处理日期和时间,转换日期格式是一个常见的功能。Python 提供了一个 time 和 calendar 模块可以用于格式化日期和时间。时间间隔是以秒为单位的浮点小数。每个时间戳都以自从1970年1月1日午夜(历元)经过了多长时间来表…...
电脑和手机的软件推荐
安卓软件 jota text 记事本 x浏览器 (支持禁js,支持嗅探 视频 音频) __ 空缺 暂未能发现好用的office软件 snapseed图片调整 可谓手机界的photoshop vidtrim视频剪辑 librera reader (无广告 电子书软件 但是发音很差 lithum或者…...

酸回收树脂的应用
酸洗废水 在轧钢、金属表面处理、电子元件制造等过程中需要清除钢材表面氧化铁皮而使用酸进行酸洗,酸洗过程中会产生废酸液和酸洗废水。 这些废酸产量大、酸度高,而且由于酸洗废水来自钢铁和金属表面处理的清洗水,水中含有多种重金属离子&am…...

windows上配置IIS全过程
文章目录1️⃣ 配置IIS1.1 从开始打开服务器管理1.2 添加角色和功能1.3 添加角色和功能向导1.4 按照如下步骤选择2️⃣ 问题:缺少源文件解决方案优质资源分享作者:xcLeigh 文章地址:https://blog.csdn.net/weixin_43151418/article/details/1…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...