蓝桥杯冲刺题单--二分
二分
知识点
二分:
1.序列二分:在序列中查找(不怎么考,会比较难?)
序列二分应用的序列必须是递增或递减,但可以非严格
只要r是mid-1,就对应mid=(l+r+1)/2
2.答案二分:最值
答案二分更重要的是思路,要自己可以二分的点,一般先写暴力,再将其转为二分。
3.浮点数二分:连续性
1.1序列二分模板题–蓝桥18492
模板题目
package erfen;import java.util.Scanner;public class Test1 {static int N = 100010;static int n, q;static int[] a = new int[N];//找到等于x的最左边的数的下标static int getL(int l, int r, int x) {while (l < r) {int mid = l + r >> 1;//右移1表示除以2if (a[mid] >= x) r = mid;else l = mid + 1;}if (a[l] == x)return l;//返回下标elsereturn -1;//不存在}//找到等于x的最右边的数的下标static int getR(int l, int r, int x) {while (l < r) {int mid = l + r + 1 >> 1;//右移1表示除以2if (a[mid] <= x) l = mid;else r = mid - 1;}if (a[l] == x)return l;//返回下标elsereturn -1;//不存在}//找到大于等于x的第一个数的下标static int lower_bound(int l, int r, int x) {while (l < r) {int mid = l + r >> 1;//右移1表示除以2if (a[mid] >= x) r = mid;else l = mid + 1;}if (a[l] >= x)return l;//返回下标elsereturn -1;//不存在}//找到大于x的第一个数的下标static int upper_bound(int l, int r, int x) {while (l < r) {int mid = l + r >> 1;//右移1表示除以2if (a[mid] > x) r = mid;else l = mid + 1;}if (a[l] > x)return l;//返回下标elsereturn -1;//不存在}//主逻辑函数static void solve() {Scanner sc = new Scanner(System.in);n = sc.nextInt();q = sc.nextInt();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}for (int i = 0; i < q; i++) {int op = sc.nextInt();int l = sc.nextInt();int r = sc.nextInt();int x = sc.nextInt();if (op == 1) {System.out.println(getL(l, r, x));} else if (op == 2) {System.out.println(getR(l, r, x));} else if (op == 3) {System.out.println(lower_bound(l, r, x));} else if (op == 4) {System.out.println(upper_bound(l, r, x));}}}public static void main(String[] args) {solve();}
}
1.2最大通过数–蓝桥3346–前缀和+二分
本题利用了前缀和和二分
思想很重要,首先枚举左边,再在里面枚举右边的通过数。
先写暴力然后就很容易写二分。
注意数值范围
暴力
package erfen;import java.util.Scanner;public class Test2 {static int N = 200010;static int m,n;static long k;static long[] a = new long[N];static long[] b = new long[N];//主逻辑函数static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextLong();a[i] = a[i - 1] + a[i];//计算前缀和}for (int i = 1; i <= m; i++) {b[i] = sc.nextLong();b[i] = b[i - 1] + b[i];//计算前缀和}int ans = 0;for (int i = 0; i <= n; i++) {//循环左边if(a[i] > k) break;//a[0]为0,所以无需担心左边为0没有遍历右边long x = k - a[i];//左边可通过i关for (int j = 0; j <= m; j++) {if(x >= b[j]){//右边可通过j关ans = Math.max(ans, i + j);}else{break;}}}System.out.println(ans);}public static void main(String[] args) {solve();}
}
二分
计算前缀和数组,它是递增的,可以应用二分
要二分就要找到单调的趋势,找到可以二分的点。
package erfen;import java.util.Scanner;public class Test2 {static int N = 200010;static int m,n;static long k;static long[] a = new long[N];static long[] b = new long[N];//主逻辑函数static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextLong();a[i] = a[i - 1] + a[i];//计算前缀和}for (int i = 1; i <= m; i++) {b[i] = sc.nextLong();b[i] = b[i - 1] + b[i];//计算前缀和}int ans = 0;for (int i = 0; i <= n; i++) {//枚举左边if(a[i] > k) break;//a[0]为0,所以无需担心左边为0没有遍历右边long x = k - a[i];//剩下的//二分第二个山洞,找到大于x的第一个数//因为是找大于x的第一个数,x可能是最后一个即m,所以r的取值要是m+1int l = 0, r = m + 1;while(l < r){int mid = l + r >> 1;if(b[mid] > x) r = mid;else l = mid + 1;}ans = Math.max(ans, i + l - 1);}System.out.println(ans);}public static void main(String[] args) {solve();}
}
1.3答案二分模板–https://hydro.ac/d/shallowdream/p/33
求最小的最大值,这题和后面那道数列分段一样,都是要求一个最值。
这个最值是自己进行枚举来得到的,这是一个重要的思路。
第二个就是本题的k次加一操作转换为了元素要达到max需要消耗多少k值,由此找到最小的max
暴力
package erfen;import java.util.Scanner;public class Test3 {static int N = 100010;static int n;static long k;static int[] a = new int[N];static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}//枚举最小值for (int i = 1; i <= 1e14; i++) {long t = k;//每次都要重新初始化for (int j = 1; j <= n; j++) {//循环数组每个元素看能否达到iif(a[j] < i){t = t -(i - a[j]);//a[j]需要(i - a[j])次加一操作才能达到i}//结束后进行判断if(t < 0){//当前数组某个元素不能达到i,那整个数组都不能达到iSystem.out.println(i - 1);return;//结束全部}}}}public static void main(String[] args) {solve();}
}
二分
找到可以二分的点:随着枚举的最大的最小值越大,t的值即剩余的k操作越来越少。
package erfen;import java.util.Scanner;public class Test3 {static int N = 100010;static int n;static long k;static int[] a = new int[N];//static boolean check(long m){long t = k;//每次都要重新初始化for (int j = 1; j <= n; j++) {//循环数组每个元素看能否达到mif(a[j] < m){t = t -(m - a[j]);//a[j]需要(m - a[j])次加一操作才能达到m}//结束后进行判断if(t < 0){//当前数组某个元素不能达到i,那整个数组都不能达到i/*System.out.println(i - 1);*/return false;//结束全部}}//整个循环结束,表示整个数组可以达到mreturn true;}static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}//二分最大的最小值long l = 1;long r = (long)1e14;while(l < r){long mid = l + r + 1 >> 1;if(check(mid)) l = mid;//true,表示可以达到mid,但是这个mid不一定是最大的。所以让l=mid。else r = mid - 1;}System.out.println(l);}public static void main(String[] args) {solve();}
}
相关文章:
蓝桥杯冲刺题单--二分
二分 知识点 二分: 1.序列二分:在序列中查找(不怎么考,会比较难?) 序列二分应用的序列必须是递增或递减,但可以非严格 只要r是mid-1,就对应mid(lr1)/2 2.答…...
计网 2025/4/8
CDMA? CRC循环冗余检验 PPP协议的帧格式 字节填充(异步传输、7E->7D5E)零比特填充(同步传输、确保不会出现连续6个1) CSMA/CD协议 多点接入载波监听碰撞检测 一些概念: 争用期 一些公式: 最短有效帧…...
java设计模式-工厂模式
工厂模式 简单工厂模式 请看类: org.xwb.springcloud.factory.simple.PizzaStore 1、简单工厂模式是属于创建型模式,是工厂模式的一种,简单工厂模式是由一个工厂对象决定创建出哪一种产品类的实力。简单来工厂模式就是工厂模式家族中最简单最…...
2025年客运从业资格证备考刷题题库
题库中通常包含大量的题目,以全面覆盖考试的知识点。通过做大量的题目,考生可以熟悉各种考试题型和命题方式,提高答题的速度和准确性,同时也能发现自己在知识掌握上的薄弱环节,有针对性地进行复习和强化训练。 1、驾驶…...
Zephyr、FreeRTOS、RT-Thread 任务创建对比分析
一、任务模型与核心概念 特性ZephyrFreeRTOSRT-Thread任务术语线程(Thread)任务(Task)线程(Thread)执行单元线程(单地址空间)任务(共享内存空间)线程&#x…...
RK-realtime Linux
rk3562实时性数据:最大76us rk3568实时性数据:最大126us rk3588实时性数据:最大30us 注意事项 (1)RK3568 需要使用RT版本的BL31,实时性能更好 a)rkbin需要更新到最新,且包含这个补丁:...
Ubuntu 22 Linux上部署DeepSeek+RAG知识库操作详解(Dify方式)之1
一、安装Docker 1. 更新你的包索引 首先,确保你的包列表是最新的。打开终端并运行以下命令: sudo apt update 2. 安装必要的依赖项 安装Docker之前,你需要安装一些必要的依赖项。运行以下命令来安装它们: sudo apt install apt…...
将飞帆制作的网页作为 div 集成到自己的网页中
并且自己的网页可以和飞帆中的控件相互调用函数。效果: 上链接 将飞帆制作的网页作为 div 集成到自己的网页中 - 文贝 进入可以复制、运行代码...
【C++游戏引擎开发】《几何算法》(3)AABB/OBB碰撞检测
一、AABB(轴对齐包围盒) 1.1 定义 最小点: m i n = ( x min , y min , z min ) \mathbf{min} = (x_{\text{min}}, y_{\text{min}}, z_{\text{min}}) min=(xmin,ymin,zmin)最大点: m a x = ( x max , y max , z max ) \mathbf{max} = (x_{\text{max}}, y_{\text{…...
基于人工智能的高中教育评价体系重构研究
基于人工智能的高中教育评价体系重构研究 一、引言 1.1 研究背景 在科技飞速发展的当下,人工智能技术已广泛渗透至各个领域,教育领域亦不例外。人工智能凭借其强大的数据处理能力、智能分析能力和个性化服务能力,为教育评价体系的创新与发…...
【C++游戏引擎开发】数学计算库GLM(线性代数)、CGAL(几何计算)的安装与使用指南
写在前面 两天都没手搓实现可用的凸包生成算法相关的代码,自觉无法手搓相关数学库,遂改为使用成熟数学库。 一、GLM库安装与介绍 1.1 vcpkg安装GLM 跨平台C包管理利器vcpkg完全指南 在PowerShell中执行命令: vcpkg install glm# 集成到系…...
Python 字典和集合(常见的映射方法)
本章内容的大纲如下: 常见的字典方法 如何处理查找不到的键 标准库中 dict 类型的变种set 和 frozenset 类型 散列表的工作原理 散列表带来的潜在影响(什么样的数据类型可作为键、不可预知的 顺序,等等) 常见的映射方法 映射类型…...
Qt 自带的QSqlDatabase 模块中使用的 SQLite 和 SQLite 官方提供的 C 语言版本(sqlite.org)对比
Qt 自带的 QSqlDatabase 模块中使用的 SQLite 和 SQLite 官方提供的 C 语言版本(sqlite.org)在核心功能上是相同的,但它们在集成方式、API 封装、功能支持以及版本更新上存在一些区别。以下是主要区别: 1. 核心 SQLite 引擎 Qt 的…...
按键长按代码
这些代码都存放在定时器中断中。中断为100ms中断一次。 数据判断,看的懂就看吧...
zk源码—3.单机和集群通信原理一
大纲 1.单机版的zk服务端的启动过程 (1)预启动阶段 (2)初始化阶段 2.集群版的zk服务端的启动过程 (1)预启动阶段 (2)初始化阶段 (3)Leader选举阶段 (4)Leader和Follower启动阶段 1.单机版的zk服务端的启动过程 (1)预启动阶段 (2)初始化阶段 单机版zk服务端的启动&…...
车企数字化转型:从“制造工厂”到“移动科技平台”的升维路径
一、战略重构:政策与产业变革的双重倒逼 中国《智能网联汽车技术路线图2.0》明确要求2030年L4级自动驾驶新车渗透率达20%,而麦肯锡数据显示,全球车企数字化投入占比已从2018年的7%跃升至2025年的18%。当前车企面临三大核心挑战:用…...
C++-Mongoose(2)-https-server-openssl
OpenSSL生成HTTPS自签名证书 - 简书 1.Openssl windowsubuntu下载http://www.openssl.vip/download1.VS2019编译OpenSSL 2.VS2019编译第一个OpenSSL项目 1.ubuntu编译OpenSSL 3.0 2.编写第一个OpenSSL 1.windows下编译OpenSSL 安装vs2019 perl nasm安装activePerl…...
nginx正向代理https
一、需求 公司内部服务器向外访问腾讯接口:https://qyapi.weixin.qq.com/cgi-bin,不能使用http直接访问。并且不支持域名,还需要设置互联网出口-出向白名单ip。 如何在尽量少改动代码的情况下实现应用的出向访问链接,考虑使用正向…...
Flask中的蓝图(Blueprint)浅讲
BluePrint Flask中的蓝图(Blueprint)是一种强大的组织工具,能够将大型应用拆分为可重用的模块化组件 1. 模块化组织 用途:将应用按功能拆分为独立模块,提升代码可维护性。示例: # user/views.py fr…...
虚拟表、TDgpt、JDBC 异步写入…TDengine 3.3.6.0 版本 8 大升级亮点
近日,TDengine 3.3.6.0 版本正式发布。除了此前已亮相的时序数据分析 AI 智能体 TDgpt,本次更新还带来了多个针对性能与易用性的重要增强:虚拟表全面上线,支持更灵活的一设备一表建模;JDBC 写入机制全新升级࿰…...
大型语言模型智能应用Coze、Dify、FastGPT、MaxKB 对比,选择合适自己的LLM工具
大型语言模型智能应用Coze、Dify、FastGPT、MaxKB 对比,选择合适自己的LLM工具 Coze、Dify、FastGPT 和 MaxKB 都是旨在帮助用户构建基于大型语言模型 (LLM) 的智能应用的平台。它们各自拥有独特的功能和侧重点,以下是对它们的简要对比: Coz…...
WEB安全--XSS--DOM破坏
一、前言 继XSS基础篇后,我们知道了三种类型的XSS,这篇文章主要针对DOM型XSS的原理进行深入解析。 二、DOM型XSS原理 2.1、什么是DOM 以一个形象的比喻: 网页就像是一座房子,而 **DOM** 就是这座房子的“蓝图”或者“结构图”。…...
持续集成:GitLab CI/CD 与 Jenkins CI/CD 的全面剖析
一、引言 在当今快速迭代的软件开发领域,持续集成(Continuous Integration,CI)已成为保障软件质量、加速开发流程的关键实践。通过频繁地将代码集成到共享仓库,并自动进行构建和测试,持续集成能够尽早发现并解决代码冲突和缺陷。而 GitLab CI/CD 和 Jenkins CI/CD 作为两…...
Go语言sync.Mutex包源码解读
互斥锁sync.Mutex是在并发程序中对共享资源进行访问控制的主要手段,对此Go语言提供了非常简单易用的机制。sync.Mutex为结构体类型,对外暴露Lock()、Unlock()、TryLock()三种方法,分别用于阻塞加锁、解锁、非阻塞加锁操作(加锁失败…...
FreeRTOS软件定时器
软件定时器就是"闹钟",你可以设置闹钟, 用软件定时器的话USE_TIMER要设置为1 在30分钟后让你起床工作每隔1小时让你例行检查机器运行情况 软件定时器也可以完成两类事情: 在"未来"某个时间点,运行函数周期…...
Selenium三大等待
一、强制等待 1.设置完等待后不管有没有找到元素,都会执行等待,等待结束后才会执行下一步 2.实例: driver webdriver.Chrome()driver.get("https://www.baidu.com")time.sleep(3) # 设置强制等待driver.quit() 二、隐性等待 …...
【Ansible自动化运维】一、初步了解,开启自动化运维之旅
在当今数字化时代,随着企业 IT 基础设施规模的不断扩大,传统的手工运维方式逐渐显得力不从心。自动化运维技术应运而生,其中 Ansible 凭借其简洁易用、功能强大的特点,成为众多运维工程师和开发人员的首选工具。本篇文章将从基础概…...
雪花算法、md5加密
雪花算法生成ID是一个64位长整型(但是也可以通过优化简短位数) 组成部分: 时间戳 机器ID 序列号 用途: 分布式系统唯一ID生成:解决数据库自增ID在分布式环境下的唯一性问题、避免UUID的无序性和性能问题 有序性…...
micro介绍
micro介绍 Micro 的首要特点是易于安装(它只是一个静态的二进制文件,没有任何依赖关系)和易于使用Micro 支持完整的插件系统。插件是用 Lua 编写的,插件管理器可自动为你下载和安装插件。使用简单的 json 格式配置选项࿰…...
电视盒子 刷armbian
参考 中兴电视盒子中兴B860AV3.2-M刷Armbian新手级教程-CSDN博客 1.刷安卓9 带root版本 a. 下载安卓线刷包 链接:https://pan.baidu.com/s/1hz87_ld2lJea0gYjeoHQ8A?pwdd7as 提取码:d7as b.拆机短接 3.安装usbburning工具 使用方法 ,…...
(七)lerobot开源项目so100新版本全流程操作(操作记录)
目录 《项目简介》 一、环境配置 1、创建虚拟环境 2、克隆项目并安装所需包 二、主从臂硬件准备 1、舵机配置 (1)分别查看主从臂的开发板端口号 (2)分别设置主从臂的舵机 2、组装主从臂 3、查看主从臂端口号和相机端…...
智慧景区能源管理解决方案,为旅游“升温”保驾护航
景区能源管理 当下痛点 1 高峰期用电负荷大 节假日和旅游旺季等高峰期用电需求增大,电力供应不足、电网负荷过大; 2 设备维护困难 景区内电力设备多且散,包括发电机组、变电站、配电设备等,维护和管理困难,特别是…...
LCR 056. 两数之和 IV - 输入二叉搜索树
文章目录 题意思路代码 题意 题目链接 思路 代码 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), …...
AI搜索+法律咨询:在「事实重构」与「程序正义」的博弈场
已经写了股票和医疗相关的内容,今天聊一下AI搜索和法律结合的应用场景。AI搜索不替用户做选择,却让我们握住了法律武器的说明书。 一、AI重构事实:技术理想与法律现实的碰撞 1、案例切入:AI能否还原车祸责任比…...
多模态大模型重塑自动驾驶:技术融合与实践路径全解析
目录 1、 引言:AI与自动驾驶的革命性融合 2、五大领先多模态模型解析 2.1 Qwen2.5-Omni:全模态集大成者 2.2. LLaVA:视觉语言理解专家 2.3. Qwen2-VL:长视频理解能手 2.4. X-InstructBLIP:跨模态理解框架 2.5. …...
海阳科技IPO:业务独立性、业绩稳定性、财务规范性存致命缺陷
三角形是最稳定的结构,它既是完美的相互制衡,又是有力的彼此支撑。 ——佚名 引 言 IPO审议指标、要求、规定众多,有无一个直接简单的公式?该公式可以直接将造假等“低劣”IPO项目排除在外? 在《奕泽财经》看来…...
PyTorch 与 Python 装饰器及迭代器的比较与应用
在深度学习和 Stable Diffusion(SD)训练过程中,PyTorch 不仅依赖于 Python 的基础特性,而且通过扩展和封装这些特性,提供了更高效、便捷的训练和推理方式。本文将从装饰器和迭代器两个方面详细解释 Python 中的原生实现…...
大数据(5)(基础概念)Spark从入门到实战:核心原理与大数据处理实战案例
目录 一、背景介绍1. 为什么需要Spark?2. Spark的诞生: 二、Spark核心原理1. 四大核心特性2. 核心架构3. 执行流程 三、Spark实战案例案例1:单词计数(WordCount)案例2:实时流处理&…...
Ubuntu小练习
文章目录 一、远程连接1、通过putty连接2、查看putty运行状态3、通过Puuty远程登录Ubuntu4、添加新用户查看是否添加成功 5、用新用户登录远程Ubuntu6、使用VNC远程登录树莓派 二、虚拟机上talk聊天三、Opencv1、简单安装版(适合新手安装)2、打开VScode特…...
运行Spark会出现恶问题
1. 依赖冲突问题:Spark依赖众多组件,如Scala、Hadoop等。不同版本的依赖之间可能存在兼容性问题,导致Spark无法正常运行。比如,特定版本的Spark可能要求与之匹配的Scala版本,若使用了不兼容的Scala版本,会在…...
uniapp大文件分包
1. 在pages.json中配置 "subPackages":[{"root":pagesUser,"pages":[{"path":mine/xxx,"style":xxx },{"path":mine/xxx,"style":xxx}]},{"root":pagesIndex,"pages":[{"p…...
Git 源码打包、迁移、恢复和备份
介绍 Git 项目打包方式,适用于源码交付、迁移、备份等场景。 一 Git 仓库的两种类型 在实际项目开发与交付中,常接触 的 两种 Git 仓库: 仓库类型是否包含源码适用场景普通仓库是本地开发、运行、构建裸仓库否代码托管、只读交付、备份 普…...
Linux 内核网络协议栈中的 struct packet_type:以 ip_packet_type 为例
在 Linux 内核的网络协议栈中,struct packet_type 是一个核心数据结构,用于注册特定协议类型的数据包处理逻辑。它定义了如何处理特定协议的数据包,并通过协议类型匹配机制实现协议分发。本文将通过分析 ip_packet_type 的定义和作用,深入探讨其在网络协议栈中的重要性。 …...
LeetCodeHot100-第三章:数学
面试经典 150 题 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台 目录 🎈1、双指针:9. 回文数 🎈2、逻辑题 :66. 加一 🎈3、逻辑题:172. 阶乘后的零 🎈4、…...
JavaScript 错误处理:理解和应对异常
在编程中,错误是不可避免的,特别是在进行复杂的逻辑操作、与外部系统交互或处理用户输入时。错误处理是软件开发中非常重要的一部分,它可以帮助开发者提高应用的稳定性和可用性。本文将深入探讨JavaScript中的错误处理机制,如何利…...
LangGraph异步化sqlite checkpoint
安装 pip install langgraph-checkpoint-sqlite异步checkpiont初始化: from langgraph.checkpoint.sqlite.aio import AsyncSqliteSaver conn aiosqlite.connect(":memory:", check_same_threadFalse) memory AsyncSqliteSaver(conn)如果使用异步流式…...
StarRocks 助力首汽约车精细化运营
作者:任智红,首汽约车大数据负责人 更多交流,联系我们:https://wx.focussend.com/weComLink/mobileQrCodeLink/334%201%202/ffbe5 导读: 本文整理自首汽约车大数据负责人任智红在 StarRocks 年度峰会上的演讲…...
Versatile-OCR-Program:可以从复杂的教育材料(如试卷)中提取结构化数据的开源多模态OCR工具
Versatile-OCR-Program 此 OCR 系统专门设计用于以针对机器学习 (ML) 训练优化的格式从复杂的教育材料(如试卷)中提取结构化数据。它支持多语言文本、数学公式、表格、图表和图表,非常适合创建高质量的训练数据集。 主…...
时序数据库 TDengine Cloud 私有连接实战指南:4步实现数据安全传输与成本优化
小T导读:在物联网和工业互联网场景下,企业对高并发、低延迟的数据处理需求愈发迫切。本文将带你深入了解 TDengineCloud 如何通过全托管服务与私有连接,帮助企业实现更安全、更高效、更低成本的数据采集与传输,从架构解析到实际配…...
vue项目本地调试使用https
由于测试环境远程接口,是采用https协议,为了能正常携带cookie访问接口,需要把本地项目也采用https协议访问。前提是后端的cookie设置在二级域名下,且允许固定其他子域名跨域访问(需要在后端设置) 项目框架…...