刷题记录:牛客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…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...