当前位置: 首页 > 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;象形柱图是…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...