当前位置: 首页 > 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…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

深入解析 ReentrantLock:原理、公平锁与非公平锁的较量

ReentrantLock 是 Java 中 java.util.concurrent.locks 包下的一个重要类,用于实现线程同步,支持可重入性,并且可以选择公平锁或非公平锁的实现方式。下面将详细介绍 ReentrantLock 的实现原理以及公平锁和非公平锁的区别。 ReentrantLock 实现原理 基本架构 ReentrantLo…...

计算机系统结构复习-名词解释2

1.定向&#xff1a;在某条指令产生计算结果之前&#xff0c;其他指令并不真正立即需要该计算结果&#xff0c;如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方&#xff0c;那么就可以避免停顿。 2.多级存储层次&#xff1a;由若干个采用不同实现技术的存储…...

轻量安全的密码管理工具Vaultwarden

一、Vaultwarden概述 Vaultwarden主要作用是提供一个自托管的密码管理器服务。它是Bitwarden密码管理器的第三方轻量版&#xff0c;由国外开发者在Bitwarden的基础上&#xff0c;采用Rust语言重写而成。 &#xff08;一&#xff09;Vaultwarden镜像的作用及特点 轻量级与高性…...