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

【蓝桥杯备赛】123(前缀和的复杂应用)

5. 前缀和的复杂应用

5.1. 123(4 星)

5.1.1. 题目解析

  1. 这道题仍然是求一段区间的和,很容易能够想到前缀和
  2. 找规律:

1------------------1 号块

1 2----------------2 号块

1 2 3--------------3 号块

1 2 3 4------------4 号块

  1. 可以将其看做是若干个块,每个块内都是公差为 1 的等差数列
  2. 我们只需要判断这个区间是第几号块,然后算出来当前的前缀和,使用之前的公式 s[r]-s[l-1]得到这段区间的和

来两道例子:

比如要求下标为 5 之前的前缀和。

我们可以根据规律求出这一块之前的前缀和,然后再根据它位于本块的第几位,求出应该在块区间和中的第几位,修正这个之前的前缀和

详细过程:

    1. 要求的下标为 5,算出其在 4 下标开始的块中,因为 5 >= 4。(就是 a[3]=4)
    2. 这块之前的前缀和为 4,需要在 4 的基础上修正。(s[3-1]=4)
    3. 求出原数组中下标为 5 的数字,距离本块开头是 3 位,所以应该加上 1~3 的和 6。(6-a[3]+1=3,b[3] = 6)
    4. 4+6=10

比如要求下标为 8 的前缀和。

    1. 求出这个在以 7 开头的块中,因为 8 >= 7。(a[4]=7)
    2. 这块之前的前缀和是 10,需要在 10 的基础上进行修正。(s[4-1]=10)
    3. 因为下标为 8,距离本块开头的距离为 2,所以需要加上 1~2 的和 3。(8-a[4]+1=2,b[2] = 3)
    4. 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&#xff08;4 星&#xff09; 5.1.1. 题目解析 这道题仍然是求一段区间的和&#xff0c;很容易能够想到前缀和找规律&#xff1a; 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 之前执行&#xff1a; &#xff08;仅在 fast5 文件中尚未包含 fastq 时需要&#xff09; tombo preprocess annotate_raw_with_fastqs --fast5-basedir /fast5_dir/ --fastq-file…...

H.265流媒体播放器EasyPlayer.js H5流媒体播放器关于如何查看手机端的日志信息并保存下来

现今流媒体播放器的发展趋势将更加多元化和个性化。人工智能的应用将深入内容创作、用户体验优化等多个方面&#xff0c;带来前所未有的个性化体验。 EasyPlayer.js H.265流媒体播放器属于一款高效、精炼、稳定且免费的流媒体播放器&#xff0c;可支持多种流媒体协议播放&#…...

uni-app快速入门(十一)--常用JS API(上)

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

Flink任务提交到yarn上slot数量为0的问题

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

vue3怎么根据字符串获取组件实例

例子&#xff1a; 我在使用vue2开发的时候&#xff0c;定义了一个方法 handler(strRef){ this.$refs[strRef].innerText hello world }&#xff0c; 我在点击某个按钮的时候&#xff0c;调用了方法handler&#xff0c;传递了一个参数是字符串 condition&#xff0c;然后方法…...

ISUP协议视频平台EasyCVR私有化视频平台新能源汽车充电停车管理方案的创新与实践

在环保意识提升和能源转型的大背景下&#xff0c;新能源汽车作为低碳出行的选择&#xff0c;正在全球迅速推广。但这种快速增长也引发了充电基础设施短缺和停车秩序混乱等挑战&#xff0c;特别是在城市中心和人口密集的居住区&#xff0c;这些问题更加明显。因此&#xff0c;开…...

智领未来: 宏集物联网HMI驱动食品与包装行业迈向智能化新高度

行业现状与挑战 食品与包装行业对设备的自动化、智能化水平要求日益提高&#xff0c;特别是瓶装和灌装生产线需要实现高速、高效的生产。此外&#xff0c;该行业还需遵循严格的卫生标准和安全规范&#xff0c;以保证产品质量符合消费者需求。在提高生产效率的同时&#xff0c;…...

redis-击穿、穿透、雪崩

击穿、穿透、雪崩经常听人说吧&#xff1f; 那他到底是啥呢&#xff1f;无非就是在有缓存层的情况下&#xff0c;对各种绕过缓存层从而直接落到了DB上的情况进行的分类。 概念性的东西大概如下&#xff0c;我是记不住&#xff0c;后期具体使用与规避这些问题才是大事&#xff…...

【Redis】服务器异常重启,导致redis启动失败

redis启动失败日志提示信息&#xff1a;Bad file format reading the append only file: make a backup of your AOF file, then use ./redis-check-aof --fix <filename> 错误日志示例图&#xff08;看最后一句&#xff09; 错误原因解析 这个错误通常是由于Redis的…...

Springboot+Vue的项目搭建(三)

一、拦截器 拦截器&#xff08;Interceptor&#xff09;是一种重要的软件设计模式&#xff0c;它在程序执行过程中能够拦截或截取特定的操作或事件&#xff0c;并在操作发生之前、之后或替代操作本身进行自定义的处理。以下是对拦截器知识点的详细归纳&#xff1a; 拦截器的定…...

【Word】一键批量引用论文上标——将正文字体改为上标格式

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

DAY1 网络编程(TCP客户端服务器)

作业&#xff1a; TCP客户端服务器。 server服务器代码&#xff1a; #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软件&#xff0c;以下有两种方式&#xff1a;第一种直接在ubuntu的软件商店里搜索CloudCompare软件进行install&#xff0c;我这里已经安装完毕。 方式二&#xff1a;可以直接原码安装&#xff1a; github地址&#xff1a; https://github.co…...

AWTK 最新动态:支持鸿蒙系统(HarmonyOS Next)

HarmonyOS是全球第三大移动操作系统&#xff0c;有巨大的市场潜力&#xff0c;在国产替代的背景下&#xff0c;机会多多&#xff0c;AWTK支持HarmonyOS&#xff0c;让AWTK开发者也能享受HarmonyOS生态的红利。 AWTK全称为Toolkit AnyWhere&#xff0c;是ZLG倾心打造的一套基于C…...

vue数据变化但页面不变

记录一下vue中数据变了 但是页面没有变化的几种情况和解决办法 情况一&#xff1a;vue无法检测实例不存在于data中的变量 原因&#xff1a;由于 Vue 会在初始化实例时对data中的数据执行getter/setter转化&#xff0c;所以变量必须在data对象上存在才能让Vue将它转化成响应式…...

Leetcode128. 最长连续序列(HOT100)

链接 第一次错误提交&#xff1a; class Solution { public:int longestConsecutive(vector<int>& nums) {int n nums.size();int res 0;sort(nums.begin(),nums.end());//第一次错误写作&#xff1a;sort(nums,numsn);nums是std::vector<int>类型&#xf…...

【阅读笔记】Dense trajectories and motion boundary descriptors for action recognition

论文地址&#xff1a;Dense Trajectories and Motion Boundary Descriptors for Action Recognition | International Journal of Computer Vision 如何用一句话描述这份工作&#xff1f;&#x1f4a1; 在多个尺度上&#xff0c;对视频序列中每一帧的密集网格上的特征点采样&a…...

React 远程仓库拉取项目部署,无法部署问题

项目场景&#xff1a; 提示&#xff1a;相关背景&#xff1a; React 远程仓库拉取项目部署&#xff0c;二次开发 问题描述 提示&#xff1a;项目中遇到的问题&#xff1a; React 远程仓库拉取项目部署&#xff0c;正确安装依赖后&#xff08;开发混乱&#xff0c;造成packg…...

CSS3新特性——字体图标、2D、3D变换、过渡、动画、多列布局

目录 一、Web字体 二、字体图标 三、2D变换 1.位移 &#xff08;1&#xff09;浮动 &#xff08;2&#xff09;相对定位 &#xff08;3)绝对定位和固定定位 &#xff08;4&#xff09;位移 用位移实现盒子的水平垂直居中 2.缩放 利用缩放调整字体到12px以下&#xff…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

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&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》

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

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...

JavaScript 标签加载

目录 JavaScript 标签加载script 标签的 async 和 defer 属性&#xff0c;分别代表什么&#xff0c;有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...