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

刷题记录:牛客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类型的呢),那么对于一个介于aaabbb的小数,显然只有当我们的半径为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现在在一个三维空间中&#xff0c;空间中每个点都可以用(x,y,z)表示。突然&#xff0c;三维空间的主人出现 了&#xff0c;如果Forsaken想要继续在三维空间中呆下去&#xff0c;他就必须回答三维空间主人的问题.主人会在空间 中坐标为(x,y,z)处…...

lombok的原理 和 使用

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

UDP网络编程

UDP和TCP 前几节我们提到了计算机网络编程中的TCP编程&#xff0c;TCP和UDP都是计算机机网络通信的传输层中的传输协议&#xff0c;今天我们来学习计算机网络编程中的基于UDP传输协议的网络编程 首先我们要了解TCP和UDP的区别 它们是同属于计算机网络传输层的传输协议 TCP&…...

“合并区间”问题解析及其思考

合并区间题目以数组 intervals 表示若干个区间的集合&#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间&#xff0c;并返回 一个不重叠的区间数组&#xff0c;该数组需恰好覆盖输入中的所有区间 。解析本题思路相对比较容易想先对各个区间按左…...

2023年理想新能源汽车核心部件解密

理想主要硬件清单(L9车型) 汽车结构 设置名称 规格 备注 价格 供应商 感知层...

C++ 将一个vector内容赋值给另一个vector,及swap与assign的区别

在本文中&#xff0c;我们将主要介绍5种将一个vector内容赋值给另一个vector的方式&#xff0c;顺便讨论下swap与assign的区别。 赋值 方式一、申明时赋值 vector<int> v2; v2.push_back(0); v2.push_back(1);vector<int> v1(v2); //声明方式二、使用assign赋值…...

PMP的价值有哪些?

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

OnGUI label 控件||Unity 3D GUI教程||OnGUI Background Color 控件

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

从 JavaScript 中的数组中删除空对象

从数组中删除空对象&#xff1a; 使用 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树是为了了解红黑树&#xff0c;了解红黑树是为了更好的理解set和map。 1、AVL树 AVL树是在二叉搜索树的基础上进行了严格的平衡&#xff0c;能做到平衡的关键是通过平衡…...

Centos7 安装 Mysql 8.0.32,详细完整教程(好文章!!)

mysql5.7的安装方式参考之前的文章&#xff1a; centos7 安装 Mysql 5.7.27&#xff0c;详细完整教程&#xff08;好文章&#xff01;&#xff01;&#xff09;_HD243608836的博客-CSDN博客 一、检查mysql版本冲突 先检查是否已经存在mysql&#xff0c;若存在卸载&#xff0…...

Apache Beanutils为什么被禁止使用?

收录于热门专栏Java基础教程系列&#xff08;进阶篇&#xff09; 在实际的项目开发中&#xff0c;对象间赋值普遍存在&#xff0c;随着双十一、秒杀等电商过程愈加复杂&#xff0c;数据量也在不断攀升&#xff0c;效率问题&#xff0c;浮出水面。 问&#xff1a;如果是你来写…...

sql server执行md5加密的时候,字符串前带N和不带N的结果是不一样的

最近因为项目的需要&#xff0c;报表中需要对数据进行MD5加密&#xff0c;结果报表系统得出来的sql语句&#xff0c;字符串前都自动带了N&#xff0c;执行时&#xff0c;发现得到的结果跟在数据库中执行的sql&#xff08;字符串不带N&#xff09;得的值不一样&#xff0c;最后自…...

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 个节点的树&#xff0c;每个节点有一种颜色&#xff0c;有 mmm 次查询操作。 查询操作给定参数 lrxl\ r\ xl r x&#xff0c;需输出&#xff1a; 将树中编号在 [l,r][l,r][l,r] 内的所有节点保留&#xff0c;xxx 所在连通块中颜色种类数。 每次查询操…...

Python 日期和时间格式

Python 程序能用很多方式处理日期和时间&#xff0c;转换日期格式是一个常见的功能。Python 提供了一个 time 和 calendar 模块可以用于格式化日期和时间。时间间隔是以秒为单位的浮点小数。每个时间戳都以自从1970年1月1日午夜&#xff08;历元&#xff09;经过了多长时间来表…...

电脑和手机的软件推荐

安卓软件 jota text 记事本 x浏览器 &#xff08;支持禁js&#xff0c;支持嗅探 视频 音频&#xff09; __ 空缺 暂未能发现好用的office软件 snapseed图片调整 可谓手机界的photoshop vidtrim视频剪辑 librera reader &#xff08;无广告 电子书软件 但是发音很差 lithum或者…...

酸回收树脂的应用

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

windows上配置IIS全过程

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

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...