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

蓝桥杯——123

123

二分+等差数列求和+前缀和数组

题目分析

在这里插入图片描述
连续一段的和我们想到了前缀和,但是这里的l和r的范围为1e12,明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点,可以按照等差数列对序列进行分块。如上图,在求前10个数的和的时候,我们可以这样求1+3(1+2)+6(1+2+3)+10(1+2+3+4)=20。我们不需要遍历10次就可以求出来。求前缀和代码如下

sum = new long[1500010];
for (int i = 1; i <= 1500000; i++) {t += i;sum[i] = sum[i-1]+t;
}

这里的t最开始等于1,是第一块的数字和,然后等于3,是第二块数字的和,然后等于6是第三块数字的和,以此类推。sum[i]表示的是分块后前i块包含数字的和。

我们可以求出前n块数字的和,那么我们需要知道第l个数字是在哪一块里面,然后求第l个数字是所在块的第几个数字。因为对于最后一块来说,不是所有的数字都会被包含进来,我们要单独对最后一块求数字和。

第一阶段利用二分求第x个数所在的块

​ 图1

如图1所示,我们可以把这个序列分块,第一块有1个数,第二块有2个数,第三块有3个数,第四块有4个数,每一块拥有数的个数是一个等差数列。现在要找到序列中第x个数所在的块数,假设x=3,那么第x个数在第2块中,如果x=4,那么第x个数在第3块中。求第x个数所在的块数,就是求从左往右数,前缀和第一个大于等于x的块。

比如第2块的前缀和就是3,第三块的前缀和就是5。这个可以用二分去求。

    int l = 1;int r = 1500000;//最多可以分的块数while(l < r) {int mid = (l + r) / 2;if(sum(mid) < x) {//求mid个块中包含的数字的个数,如果小于x,就是不符合条件,我要向左找l = mid + 1;}else {//符合条件,我要看前面的块是否也是大于等于x的r = mid;}}

这里的sum函数的作用就是求前mid块中包含的数字的个数,因为是等差数列,所以直接用等差数列的求和公式就可以了,sum函数如下

private static long sum(long x) {    return (1L + x) * x / 2;
}

第二阶段求前x个数的前缀和

接下来分析二分结束之和我要怎么操作,我要求前x个数字的和。

假设x=8,那么第x个数在第4块中,我还要知道,第x个数是第4块中的第几个数字。如图,第4块有4个数,第x个数第4块的第2个数上,那么第2个数是怎么来的呢?就是x-sum(r-1)=8-6=2。其实就是我二分算出来了第x个数在第r块上,那么我只需要把前r-1块包含的数的个数减去就算出来x是在第r块上的第几个数上了。结合上图更好理解。那么前x个数的和就是前r-1块包含数的和加上第r块里面前x-sum(r-1)个数的和。

某一块里面包含的数也是等差数列,求前n个数的和依然可以直接用sum(n)去求。而数组sum[r]里面记录的是前r块包含数字值的前缀和。所以二分结束后的代码是这样子的

private static long f(long x) {int l = 1;int r = 1500000;//最多可以分的块数while(l < r) {int mid = (l + r) / 2;if(sum(mid) < x) {//求mid个块中包含的数字的个数l = mid + 1;}else {r = mid;}}//r--是表示完整的块的个数r--;//就是上文里的r-1//x表示x处在他所在块的第几个位置,需要减去前面所有块包含的数的个数//本来要求x个数字,前r个块中已经包含了sum(r)个数字,第r+1个块x -= sum(r);//前r个块中已经包含了多少个数字return sum[r]+sum(x);
}

还是对于x=8的例子,二分求出来r=4,r–后,r=3,sum[3]=10。x-=sum(3)=8-6=2。sum[3]+sum(2)=10+3=13

注意这道题里对于sum函数的多次应用,但是不是每一次应用含义都是一样的。因为每一块包含的数字个数是等差数列,而每一块内每个数字形成的也是等差数列。

题目代码

import java.util.Scanner;
public class Main {
static long[] sum;
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long t = 0;//前缀和的预处理sum = new long[1500010];for (int i = 1; i <= 1500000; i++) {t += i;sum[i] = sum[i-1]+t;}int n = scanner.nextInt();while(n-- > 0) {long l = scanner.nextLong();long r = scanner.nextLong();System.out.println(f(r)-f(l-1));//f(r)求的是序列中前r个数的和}
}
//二分  二分求的是x在哪一块中 n*(n-1)/2>l的第一个n
private static long f(long x) {int l = 1;int r = 1500000;//最多可以分的块数while(l < r) {int mid = (l + r) / 2;if(sum(mid) < x) {//求mid个块中包含的数字的个数l = mid + 1;}else {r = mid;}}//r--是表示完整的块的个数r--;//x表示x处在他所在块的第几个位置,需要减去前面所有块包含的数的个数//本来要求x个数字,前r个块中已经包含了sum(r)个数字,第r+1个块x -= sum(r);//前r个块中已经包含了多少个数字return sum[r]+sum(x);
}
//sum函数求前x块包含的数的个数,同时也可以表示某一个块中,前x个数的总和
private static long sum(long x) {// TODO Auto-generated method stub    return (1L + x) * x / 2;
}
}

相关文章:

蓝桥杯——123

123 二分等差数列求和前缀和数组 题目分析 连续一段的和我们想到了前缀和&#xff0c;但是这里的l和r的范围为1e12&#xff0c;明显不能用O(n)的时间复杂度去求前缀和。那么我们开始观察序列的特点&#xff0c;可以按照等差数列对序列进行分块。如上图&#xff0c;在求前10个…...

嵌入式基础知识-信号量,PV原语与前趋图

本篇来介绍信号量与PV原语的一些知识&#xff0c;并介绍其在前趋图上的应用分析。本篇的知识属于操作系统部分的通用知识&#xff0c;在嵌入式软件开发中&#xff0c;同样会用到这些知识。 1 信号量 信号量是最早出现的用来解决进程同步与互斥问题的机制&#xff08;可以把信…...

代码遗产:探索祖传代码的历史、挑战与现代融合艺术

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua&#xff0c;在这里我会分享我的知识和经验。&#x…...

Vue3:用vite创建Vue3项目

一、简介 vite是新一代前端构建工具&#xff0c;官网地址&#xff1a;https://vitejs.cn vite的优势如下&#xff1a; 轻量快速的热重载&#xff08;HMR&#xff09;&#xff0c;能实现极速的服务启动。对 TypeScript、JSX、CSS 等支持开箱即用。真正的按需编译&#xff0c;不…...

STM32 (2)

1.stm32编程模型 将C语言程序烧录到芯片中会存储在单片机的flsah存储器中&#xff0c;给芯片上电后&#xff0c;Flash中的程序会逐条进入到CPU中去执行&#xff0c;进而CPU去控制各种模块&#xff08;即外设&#xff09;去实现各种功能。 2.寄存器和寄存器编程 CPU通过控制其…...

docker部署nginx+反向代理配置/代理宿主机网段服务器

1、安装docker&#xff0c;并运行 2、拉取nginx镜像 docker pull nginx3、运行nginx容器&#xff0c;将文件拷贝至本地&#xff0c;并将nginx容器删除 #运行nginx容器 docker run -id --name mynginx -p 8080:80 nginx#将配置文件从容器内拷贝至本地 docker cp 容器ID:/et…...

初识Hive

官网地址为&#xff1a; Design - Apache Hive - Apache Software Foundation 一、架构 先来看下官网给的图&#xff1a; 图上显示了Hive的主要组件及其与Hadoop的交互。Hive的主要组件有&#xff1a; UI&#xff1a; 用户向系统提交查询和其他操作的用户界面。截至2011年&…...

Google发布Genie硬杠Sora:通过大量无监督视频训练最终生成可交互虚拟世界

前言 Sora 问世才不到两个星期&#xff0c;谷歌的世界模型也来了&#xff0c;能力看似更强大&#xff1a;它生成的虚拟世界自主可控 第一部分 首个基础世界模型Genie 1.1 Genie是什么 Genie是第一个以无监督方式从未标记的互联网视频中训练的生成式交互环境(the first gener…...

全球首台!未磁科技256通道无液氦脑磁图仪及芯片化原子磁力计正式发布

2024年2月3日&#xff0c;由北京未磁科技有限公司牵头的国家重点研发计划诊疗装备与生物医用材料重点专项“新型无液氦脑磁图系统研发”项目2023年度总结会暨2024年推进会顺利召开。会上发布了项目取得的重大成果——全球首台256通道无液氦脑磁图仪Marvel MEG Pro。此项重磅成果…...

openssl3.2 - exp - 内存操作(建立,写入,读取)配置

文章目录 openssl3.2 - exp - 内存操作(建立,写入,读取)配置概述笔记调试细节运行效果测试工程实现main.cppCMyOsslConfig.hCMyOsslConfig.cppEND openssl3.2 - exp - 内存操作(建立,写入,读取)配置 概述 我的应用的配置文件是落地加密的, 无法直接用openssl配置接口载入读取…...

前端食堂技术周刊第 114 期:Interop 2024、TS 5.4 RC、2 月登陆浏览器的新功能、JSR、AI SDK 3.0

美味值&#xff1a;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f; 口味&#xff1a;凉拌鸡架 食堂技术周刊仓库地址&#xff1a;https://github.com/Geekhyt/weekly 大家好&#xff0c;我是童欧巴。欢迎来到前端食堂技术周刊&#xff0c;我们先来看下…...

#QT(信号与槽)

1.IDE&#xff1a;QTCreator 2.实验:自动添加槽函数&#xff0c;手动添加槽函数 3.记录 &#xff08;1&#xff09;自动添加 a.拖拽widget.ui&#xff0c;放置push-button组件&#xff0c;并且自动生成槽函数 b.发现widget.cpp和widget.h中出现添加的槽函数&#xff0c;注意w…...

go 设置滚动日志

方案 通过 log/slog 实现结构化日志生成&#xff0c;这是go1.21中推出的新特性&#xff1b;通过 lumberjack 实现日志文件分割。 示例 package mainimport ("gopkg.in/natefinch/lumberjack.v2""log/slog""os""path/filepath" )fun…...

Rollup入门学习:前端开发的构建利器

在前端开发领域&#xff0c;构建工具对于优化项目结构和提升代码效率扮演着至关重要的角色。Rollup作为一款轻量级且功能强大的JavaScript模块打包器&#xff0c;近年来备受开发者青睐。本文将带你走进Rollup的世界&#xff0c;帮助你快速入门并掌握其核心用法。 一、Rollup简介…...

游戏寻路之A*算法(GUI演示)

一、A*算法介绍 A*算法是一种路径搜索算法,用于在图形网络中找到最短路径。它结合了Dijkstra算法和启发式搜索的思想,通过综合利用已知的最短路径和估计的最短路径来优化搜索过程。在游戏自动寻路得到广泛应用。 二、A*算法的基本思想 在图形网络中选择一个起点和终点。维护…...

软件工程顶会——ICSE '24 论文清单、摘要

1、A Comprehensive Study of Learning-based Android Malware Detectors under Challenging Environments 近年来&#xff0c;学习型Android恶意软件检测器不断增多。这些检测器可以分为三种类型&#xff1a;基于字符串、基于图像和基于图形。它们大多在理想情况下取得了良好的…...

Vue点击复制到剪切板

一、Vue2写法 安装 &#xff08;官网地址&#xff09; npm install --save vue-clipboard2 使用 //main.js import VueClipboard from vue-clipboard2 Vue.use(VueClipboard)//页面使用 <button type"button"v-clipboard:copy"message"v-clipboard:su…...

链路负载均衡之DNS透明代理

一、DNS透明代理 一般来说&#xff0c;企业的客户端上都只能配置一个运营商的DNS服务器地址&#xff0c;DNS服务器通常会将域名解析成自己所在ISP内的Web服务器地址&#xff0c;这将导致内网用户的上网流量都集中在一个ISP的链路上转发&#xff0c;最终可能会造成链路拥塞&…...

2024大语言模型LLM基础|语义搜索Semantic_Search全解

目录 语义搜索Semantic_Search代码详解 为甚麽用Pinecone做向量索引&#xff1f;优点是什么&#xff1f; 有哪些常见向量索引方法&#xff1f; Pinecone做向量索引怎么用&#xff1f; 向量索引全解&#xff1a;含原理解析&#xff1a; 语义搜索Semantic_Search代码详解 1…...

vue中使用echarts实现人体动态图

最近一直处于开发大屏的项目&#xff0c;在开发中遇到了一个小知识点&#xff0c;在大屏中如何实现人体动态图。然后看了下echarts官方文档&#xff0c;根据文档中的示例调整出来自己想要的效果。 根据文档上发现 series 中 type 类型设置为 象形柱形图&#xff0c;象形柱图是…...

OpenClaw云端体验指南:无需本地安装快速测试Phi-3-vision-128k-instruct

OpenClaw云端体验指南&#xff1a;无需本地安装快速测试Phi-3-vision-128k-instruct 1. 为什么选择云端体验OpenClaw 作为一个长期折腾本地AI部署的技术爱好者&#xff0c;我完全理解那种"想先试试再决定是否投入"的心态。去年尝试在MacBook Pro上部署Llama 2时&am…...

LabelImg闪退报错别慌!手把手教你排查‘list index out of range’和‘ValueError’

LabelImg闪退报错全攻略&#xff1a;从崩溃到流畅标注的完整指南 当你正全神贯注地标注数据集时&#xff0c;LabelImg突然闪退并抛出一串红色错误信息——这种经历对任何AI从业者来说都堪称噩梦。别担心&#xff0c;这不是你一个人的问题。根据社区统计&#xff0c;超过60%的La…...

电子电路设计中7种关键接口技术解析与应用

1. 电路接口概述&#xff1a;信号传输的关键桥梁在嵌入式系统和电子电路设计中&#xff0c;接口技术就像城市之间的高速公路系统。当CPU需要与传感器"对话"&#xff0c;当存储器要与处理器"交换情报"&#xff0c;这些不同模块之间的信号传输总会面临三大挑…...

I2C设备扫描器:嵌入式系统总线拓扑发现与地址诊断工具

1. I2C设备扫描器&#xff1a;嵌入式系统中总线拓扑发现的核心工具IC&#xff08;Inter-Integrated Circuit&#xff09;总线因其仅需两根信号线&#xff08;SCL时钟线与SDA数据线&#xff09;、支持多主多从架构、内置仲裁与应答机制等特性&#xff0c;成为嵌入式系统中传感器…...

手把手教你用RFSoC ZU47DR的DAC/ADC:从单音信号到1200MHz宽带调制的避坑实践

手把手教你用RFSoC ZU47DR的DAC/ADC&#xff1a;从单音信号到1200MHz宽带调制的避坑实践 当一块开发板的价格抵得上半辆家用轿车时&#xff0c;每个操作步骤都值得反复推敲。这就是RFSoC ZU47DR给我的第一印象——强大到令人兴奋&#xff0c;复杂到让人却步。作为赛灵思第三代射…...

集成学习完全指南:从AdaBoost到随机森林,揭秘为什么一群“弱鸡”能吊打“学霸”

在机器学习领域&#xff0c;单个模型的表现往往受限于其固有的偏差&#xff08;Bias&#xff09;和方差&#xff08;Variance&#xff09;问题——这就好比一位再厉害的学霸&#xff0c;也难免有自己的知识盲区。集成学习&#xff08;Ensemble Learning&#xff09;正是为解决这…...

COMSOL水力压裂岩石多裂隙损伤耦合模型及含离散裂隙Matlab建模文件

comsol水力压裂岩石多裂隙损伤耦合模型&#xff0c;含离散裂隙matlab建模文件地下三千米的页岩层正在经历一场暴力美学——高压水柱像手术刀般精准切开岩石&#xff0c;形成错综复杂的裂缝网络。这个看似野蛮的过程背后&#xff0c;隐藏着流-固-损伤三场耦合的精密舞蹈。今天我…...

Atlas 800I A2实战:5小时搞定DeepSeek V3 W4A8量化全流程(含显存优化技巧)

Atlas 800I A2实战&#xff1a;5小时搞定DeepSeek V3 W4A8量化全流程&#xff08;含显存优化技巧&#xff09; 在AI模型部署领域&#xff0c;量化技术正成为突破硬件限制的关键手段。当我们面对Atlas 800I A2这样的高性能服务器时&#xff0c;如何充分发挥其64GB显存优势&#…...

2025Reddit养号实战:3步打造高Karma账号矩阵

1. Reddit养号基础&#xff1a;为什么Karma值如此重要&#xff1f; 如果你刚接触Reddit&#xff0c;可能会对这个平台的"Karma系统"感到困惑。简单来说&#xff0c;Karma就像你在Reddit社区里的信用积分&#xff0c;它决定了你的发言权和影响力。我刚开始运营Reddit账…...

在华为OpenEuler上同时安装Python 3.8.6和3.9.0,我是如何解决依赖冲突和whl包不全问题的

在华为OpenEuler上实现Python 3.8.6与3.9.0双版本共存的实战指南 当开发环境需要同时支持Python 3.8.6和3.9.0时&#xff0c;许多开发者都会面临依赖冲突、whl包不兼容等问题。特别是在华为OpenEuler这样的企业级操作系统上&#xff0c;系统自带的Python版本可能无法满足特定项…...