【蓝桥杯备赛】123(前缀和的复杂应用)
5. 前缀和的复杂应用
5.1. 123(4 星)
5.1.1. 题目解析
- 这道题仍然是求一段区间的和,很容易能够想到前缀和
- 找规律:
1------------------1 号块
1 2----------------2 号块
1 2 3--------------3 号块
1 2 3 4------------4 号块
- 可以将其看做是若干个块,每个块内都是公差为 1 的等差数列
- 我们只需要判断这个区间是第几号块,然后算出来当前的前缀和,使用之前的公式
s[r]-s[l-1]
得到这段区间的和
来两道例子:
比如要求下标为 5 之前的前缀和。
我们可以根据规律求出这一块之前的前缀和
,然后再根据它位于本块的第几位
,求出应该在块区间和
中的第几位,修正这个之前的前缀和
。
详细过程:
-
- 要求的下标为 5,算出其在 4 下标开始的块中,因为 5 >= 4。(就是 a[3]=4)
- 这块之前的前缀和为
4
,需要在 4 的基础上修正。(s[3-1]=4) - 求出原数组中下标为 5 的数字,距离本块开头是 3 位,所以应该加上 1~3 的和
6
。(6-a[3]+1=3,b[3] = 6) - 4+6=10
比如要求下标为 8 的前缀和。
-
- 求出这个在以 7 开头的块中,因为 8 >= 7。(a[4]=7)
- 这块之前的前缀和是
10
,需要在 10 的基础上进行修正。(s[4-1]=10) - 因为下标为 8,距离本块开头的距离为 2,所以需要加上 1~2 的和
3
。(8-a[4]+1=2,b[2] = 3) - 10+3=13
5.1.2. 代码
package lanqiao;import java.util.Scanner;public class _23_123 {static Scanner in = new Scanner(System.in);static int N = (int) (1e6 + 1e6 + 1e6);static long[] a = new long[N];// 区间开头的下标static long[] b = new long[N];// 每个区间的和static long[] s = new long[N];// 所有的前缀和public static void main(String[] args) {long t = in.nextLong();// 构建区间,前缀和a[0] = 1;for (int i = 1; i < N; i++) {a[i] = a[i - 1] + i;b[i] = b[i - 1] + i;s[i] = s[i - 1] + b[i];}// 查找l和r应该在哪个区间for (int i = 0; i < t; i++) {long l = in.nextLong(), r = in.nextLong();// 找>=xsolve(l, r);}}private static void solve(long x, long y) {int l = 0, r = N - 1;// 找到l在哪个区间l = getL(x, l, r);// 开始坐标是a[l-1],上一个区间结束的前缀和是s[l-1],本区间的和是b[l-1]long gap = x - a[l];
// System.out.print("l: " + l + " ");
// System.out.print( (s[l] + x-a[l]));long q = s[l] + b[(int) gap];// 找到r在哪个区间l = 0;r = N - 1;l = getL(y, l, r);gap = y - a[l] + 1;
// System.out.println();
// System.out.print("l: " + l);
// System.out.println(" " + (s[l] + y-a[l]));long w = s[l] + b[(int) gap];System.out.println(w - q);
// System.out.println("------_");}private static int getL(long x, int l, int r) {while (l < r) {int mid = (l + r + 1) >> 1;if (a[mid] > x) {r = mid - 1;} else {l = mid;}}return l;}
}
相关文章:

【蓝桥杯备赛】123(前缀和的复杂应用)
5. 前缀和的复杂应用 5.1. 123(4 星) 5.1.1. 题目解析 这道题仍然是求一段区间的和,很容易能够想到前缀和找规律: 1------------------1 号块 1 2----------------2 号块 1 2 3--------------3 号块 1 2 3 4------------4 号…...
MINES
MINES (m)6A (I)dentification Using (N)anopor(E) (S)equencing Tombo(v1.4) 命令在 MINES 之前执行: (仅在 fast5 文件中尚未包含 fastq 时需要) tombo preprocess annotate_raw_with_fastqs --fast5-basedir /fast5_dir/ --fastq-file…...

H.265流媒体播放器EasyPlayer.js H5流媒体播放器关于如何查看手机端的日志信息并保存下来
现今流媒体播放器的发展趋势将更加多元化和个性化。人工智能的应用将深入内容创作、用户体验优化等多个方面,带来前所未有的个性化体验。 EasyPlayer.js H.265流媒体播放器属于一款高效、精炼、稳定且免费的流媒体播放器,可支持多种流媒体协议播放&#…...

uni-app快速入门(十一)--常用JS API(上)
在前面学习了uni-app的布局、组件、路由等知识点以后,还要掌握uni-app的JS API ,也可以理解为基于uni-app的java script。本节介绍uni-app的request请求、文件上传、数据缓存、获取位置、获取系统信息、获取手机的网络状态、拨打电话API。 一、request请求 使用uni…...

Flink任务提交到yarn上slot数量为0的问题
现象:Flink提交到yarn上slot数量为0的问题 解决方法: 参考论坛上的方案,修改flink-conf.yaml文件都不管用 最终解决方法: $FLINK_HOME/lib 路径下有2个非.jar结尾的文件,把这几个文件移走之后,再启就可…...

vue3怎么根据字符串获取组件实例
例子: 我在使用vue2开发的时候,定义了一个方法 handler(strRef){ this.$refs[strRef].innerText hello world }, 我在点击某个按钮的时候,调用了方法handler,传递了一个参数是字符串 condition,然后方法…...

ISUP协议视频平台EasyCVR私有化视频平台新能源汽车充电停车管理方案的创新与实践
在环保意识提升和能源转型的大背景下,新能源汽车作为低碳出行的选择,正在全球迅速推广。但这种快速增长也引发了充电基础设施短缺和停车秩序混乱等挑战,特别是在城市中心和人口密集的居住区,这些问题更加明显。因此,开…...

智领未来: 宏集物联网HMI驱动食品与包装行业迈向智能化新高度
行业现状与挑战 食品与包装行业对设备的自动化、智能化水平要求日益提高,特别是瓶装和灌装生产线需要实现高速、高效的生产。此外,该行业还需遵循严格的卫生标准和安全规范,以保证产品质量符合消费者需求。在提高生产效率的同时,…...
redis-击穿、穿透、雪崩
击穿、穿透、雪崩经常听人说吧? 那他到底是啥呢?无非就是在有缓存层的情况下,对各种绕过缓存层从而直接落到了DB上的情况进行的分类。 概念性的东西大概如下,我是记不住,后期具体使用与规避这些问题才是大事ÿ…...

【Redis】服务器异常重启,导致redis启动失败
redis启动失败日志提示信息:Bad file format reading the append only file: make a backup of your AOF file, then use ./redis-check-aof --fix <filename> 错误日志示例图(看最后一句) 错误原因解析 这个错误通常是由于Redis的…...
Springboot+Vue的项目搭建(三)
一、拦截器 拦截器(Interceptor)是一种重要的软件设计模式,它在程序执行过程中能够拦截或截取特定的操作或事件,并在操作发生之前、之后或替代操作本身进行自定义的处理。以下是对拦截器知识点的详细归纳: 拦截器的定…...

【Word】一键批量引用论文上标——将正文字体改为上标格式
【Word】一键批量引用论文上标——将正文字体改为上标格式 写在最前面Word一键批量引用论文上标技巧分享核心思路:Word 替换功能 通配符步骤详解1. 打开 Word 替换功能2. 输入通配符模式3. 设置替换格式为上标4. 批量替换 实际效果展示技巧扩展 🌈你好呀…...

DAY1 网络编程(TCP客户端服务器)
作业: TCP客户端服务器。 server服务器代码: #include <myhead.h> #define IP "192.168.110.52" #define PORT 8886 #define BACKLOG 20 int main(int argc, const char *argv[]) {int oldfdsocket(AF_INET,SOCK_STREAM,0);//IPV4通信…...

如何在Ubuntu当中利用CloudCompare软件进行点云配准拼接?
1.首先需要安装相应的cloudcompare软件,以下有两种方式:第一种直接在ubuntu的软件商店里搜索CloudCompare软件进行install,我这里已经安装完毕。 方式二:可以直接原码安装: github地址: https://github.co…...

AWTK 最新动态:支持鸿蒙系统(HarmonyOS Next)
HarmonyOS是全球第三大移动操作系统,有巨大的市场潜力,在国产替代的背景下,机会多多,AWTK支持HarmonyOS,让AWTK开发者也能享受HarmonyOS生态的红利。 AWTK全称为Toolkit AnyWhere,是ZLG倾心打造的一套基于C…...
vue数据变化但页面不变
记录一下vue中数据变了 但是页面没有变化的几种情况和解决办法 情况一:vue无法检测实例不存在于data中的变量 原因:由于 Vue 会在初始化实例时对data中的数据执行getter/setter转化,所以变量必须在data对象上存在才能让Vue将它转化成响应式…...
Leetcode128. 最长连续序列(HOT100)
链接 第一次错误提交: class Solution { public:int longestConsecutive(vector<int>& nums) {int n nums.size();int res 0;sort(nums.begin(),nums.end());//第一次错误写作:sort(nums,numsn);nums是std::vector<int>类型…...

【阅读笔记】Dense trajectories and motion boundary descriptors for action recognition
论文地址:Dense Trajectories and Motion Boundary Descriptors for Action Recognition | International Journal of Computer Vision 如何用一句话描述这份工作?💡 在多个尺度上,对视频序列中每一帧的密集网格上的特征点采样&a…...
React 远程仓库拉取项目部署,无法部署问题
项目场景: 提示:相关背景: React 远程仓库拉取项目部署,二次开发 问题描述 提示:项目中遇到的问题: React 远程仓库拉取项目部署,正确安装依赖后(开发混乱,造成packg…...

CSS3新特性——字体图标、2D、3D变换、过渡、动画、多列布局
目录 一、Web字体 二、字体图标 三、2D变换 1.位移 (1)浮动 (2)相对定位 (3)绝对定位和固定定位 (4)位移 用位移实现盒子的水平垂直居中 2.缩放 利用缩放调整字体到12px以下ÿ…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。
2024 年,高端封装市场规模为 80 亿美元,预计到 2030 年将超过 280 亿美元,2024-2030 年复合年增长率为 23%。 细分到各个终端市场,最大的高端性能封装市场是“电信和基础设施”,2024 年该市场创造了超过 67% 的收入。…...
JavaScript 标签加载
目录 JavaScript 标签加载script 标签的 async 和 defer 属性,分别代表什么,有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...