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

【蓝桥杯每日一题】二分算法

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙我与杀戮之中绽放,亦如黎明的花朵🌙
🍉一起加油,去追寻、去成为更好的自己!

蓝桥杯倒计时 43天

文章目录

  • 🍎、二分
  • 🍎、例题分析
        • 🍇、(AcWing)数的范围
        • 🍇、(AcWing)四平方和
        • 🍇、(AcWing)分巧克力
        • 🍇、(AcWing)我在哪?
  • 🍎、总结

提示:以下是本篇文章正文内容,下面案例可供参考


🍎、二分

🍉、二分的简单定义

二分法(Bisection method) 即一分为二的方法. 设[a,b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的中点.

🍉、二分的基本逻辑

算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。
基本思想:假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较,
如果当前位置arr[k]值等于key,则查找成功;
若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low,mid-1];
若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid+1,high],
直到找到为止,时间复杂度:O(log(n)) 。(来源百度百科)

🍉、二分的算法模板(y总)

//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; else l = mid + 1; }   return l;
}
//查找右边界 SearchRight 简写SR 
int SR(int l, int r) 
{while (l < r){                   int mid = l + r + 1 >> 1; //需要+1 防止死循环if (check(mid)) l = mid;else r = mid - 1; }return r;
}

🔥博主对于在做题时该选择哪种模板时的看法:

    首先我们在考虑使用哪个模板时,其实就是考虑mid, R,和 L的取值,我们肯定要先分析题目的意思,如果我们的答案在mid的右边,那么我们优先使用枚举区间右端点的模板,也就是选择mid = l + r + 1 >> 1往上取整的模板,同理,我们如果要的答案在mid的左边,择选择第一种mid = l + r >> 1的模板。还有,我们在考虑这道题能不能使用二分时,其实对于这道题是否具有单调性并不看重,如果具有二段性,就能使用二分。

🔥二分的几个应用场景

1:找大于等于数的第一个位置 (满足某个条件的第一个数)
2:找小于等于数的最后一个数 (满足某个条件的最后一个数)
3.查找最大值 (满足该边界的右边界)、
4.查找最小值 (满足该边界的左边界)


🍎、例题分析

🍇、(AcWing)数的范围

本题链接: 数的范围
在这里插入图片描述
简单分析题意:先输入一个长度为n的数组,然后进行q次询问,每次询问如果这个数组存在值=x,就把这个值在x的起始位置和终止位置返回,若不存在就输出 -1 -1;

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int s[N];
int n, q;
int main ()
{cin >> n >> q;for(int i = 0; i < n; i++) cin >> s[i];while(q --){int x;cin >> x;int l = 0, r = n - 1;while(l < r)//枚举左端点{int mid = l + r >> 1;if(s[mid] >= x) r = mid;else l = mid + 1;}if(s[r] == x){cout << r << " ";l = 0, r = n - 1;while(l < r)//z枚举右端点{int mid = l + r + 1 >> 1;//此时mid在右区间, mid要向上取整,所以要+1if(s[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}else cout << "-1 -1" << endl;}return 0;
}

🍇、(AcWing)四平方和

本题链接: 四平方和
在这里插入图片描述
简单分析题意: 由于 5 * 10^6的数据范围,所以不能枚举四个数,只能枚举两个数,把时间复杂度降到nlogn左右。
在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 5000010;
int n;int h[N], m[N];
int main ()
{cin >> n;memset(h, -1,sizeof h ); //把h数组内的值全初始化为-1,标记为未用过for(int c = 0; c * c <= n; c++)for(int d = c; d * d + c * c <= n; d++){int s = c * c + d * d;if(h[s] == -1)h[s] = c, m[s] = d;}for(int a = 0; a * a <= n; a++)for(int b = a; b * b + a * a <= n; b++){int s = n - a * a - b * b;if(h[s] != -1){printf("%d %d %d %d\n",a , b, h[s], m[s]);return 0;}}return 0;
}

🍇、(AcWing)分巧克力

本题链接: 分巧克力
在这里插入图片描述
解题思路:
在这里插入图片描述
代码示例:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
int h[N], w[N];//横竖边长
bool cheak(int mid)
{LL res = 0;for(int i = 0; i < n; i++){res += (LL)h[i]/mid *(w[i] / mid);if(res >= k) return true;}return false;
}
int main ()
{cin >> n >> k;for(int i = 0; i < n; i++) cin >> h[i] >> w[i];int l = 1, r = 1e5;while(l < r){int mid = l + r + 1 >> 1;if(cheak(mid)) l = mid;else r = mid - 1;}cout << r << endl;return 0;
}

🍇、(AcWing)我在哪?

本题链接: 我在哪?
在这里插入图片描述
简单分析题意:本道题的题意还是比较难理解的,题目又长,核心就是这一句:例如,假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3,因为如果他看到了 ABC,则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4,因为如果他查看任意连续 4 个邮箱,那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
本意等价于:在一个连续的字符串中找到最短的能判断是在这串字符串中唯一出现,这个字符串的长度就是k值。

解题思路:因为这道题的数据量只有100,所以可以直接暴力,也可以二分最小的mid值,两种做法。

暴力代码示例:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;int n;
string str;
int main ()
{cin >> n >> str;for(int k = 1; k <= n; k++){bool flag = false; //判断两个串是不是相同for(int i = 0; i + k - 1 <= n; i++)//i + k - 1是这个串的长度{for(int j = i + 1; j + k -1 <= n; j++)//j的枚举要从i + 1开始{bool Same = true;//判断两个串是不是相同for(int u = 0; u < k; u++)if(str[i + u] != str[j + u]){Same = false;break;}if(Same) {flag = true;break;}}}if(!flag) {cout << k << endl;break;}}return 0;
}

二分代码示例:

#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_set>
using namespace std;int n;
string str;
bool cheak(int mid)
{unordered_set<string> hash;for(int i = 0; i +  mid  -1 <= n; i++){string s = str.substr(i, mid);if(hash.count(s)) return false; //如果s已经在哈希表中存在过了,返回falsehash.insert(s);//哈希表中再插入s}return true;
}
int main ()
{cin >> n >> str;int l = 1, r = n;while(l < r){int mid = l + r >> 1;if(cheak(mid)) r = mid;else l = mid + 1;}cout << r << endl;return 0;
}

🍎、总结

    本文简要介绍了二分的简要概念和应用场景和经典的二分模板和几道二分的经典例题,希望大家读后能有所收获!

相关文章:

【蓝桥杯每日一题】二分算法

&#x1f34e; 博客主页&#xff1a;&#x1f319;披星戴月的贾维斯 &#x1f34e; 欢迎关注&#xff1a;&#x1f44d;点赞&#x1f343;收藏&#x1f525;留言 &#x1f347;系列专栏&#xff1a;&#x1f319; 蓝桥杯 &#x1f319;我与杀戮之中绽放&#xff0c;亦如黎明的花…...

Spring Batch 高级篇-并行步骤

目录 引言 概念 案例 转视频版 引言 接着上篇&#xff1a;Spring Batch 高级篇-多线程步骤&#xff0c;了解Spring Batch多线程步骤后&#xff0c;接下来一起学习一下Spring Batch 高级功能-并行步骤 概念 并行步骤&#xff0c;指的是某2个或者多个步骤同时执行。比如下…...

对spring的@Cacheable缓存理解

1 什么是缓存第一个问题&#xff0c;首先要搞明白什么是缓存&#xff0c;缓存的意义是什么。对于普通业务&#xff0c;如果要查询一个数据&#xff0c;一般直接select数据库进行查找。但是在高流量的情况下&#xff0c;直接查找数据库就会成为性能的瓶颈。因为数据库查找的流程…...

力扣-市场分析

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;1158. 市场分析二、解题1.错误示范①提交SQL运行结果2.正确示范①提交SQL运行结果3.错误示范②提交SQL运行结果4.正确示范②提交SQL运行结果5.其他总结前…...

【2357. 使数组中所有元素都等于零】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个非负整数数组 nums 。在一步操作中&#xff0c;你必须&#xff1a; 选出一个正整数 x &#xff0c;x 需要小于或等于 nums 中 最小 的 非零 元素。nums 中的每个正整数都减去 x。 返回使 n…...

什么品牌的游戏蓝牙耳机比较好?玩游戏延迟低的蓝牙耳机推荐

游戏耳机的出现其实最主要的作用就是让玩家能够更专注的沉浸在游戏世界内&#xff0c;在声音层面去享受游戏的沉浸感&#xff0c;游戏最重要的就是操作灵敏&#xff0c;需要快速通过声音来判断敌人走向&#xff0c;所以小编特意整理了一期玩游戏延迟低的蓝牙耳机。 一、南卡小…...

day 33 状态压缩dp

二维状态压缩dp对于解决哈密顿回路问题的状态压缩dp只能计算固定起点到其他点的总方案数或最小路径等回路计数小蓝现在在第一栋教学楼&#xff0c;他想要访问每栋教学楼正好一次&#xff0c;最终回到第一栋教学楼&#xff08;即走一条哈密尔顿回路&#xff09;可看做&#xff1…...

扬帆优配|超3600股飘绿,人民币贬值近300点!外资净卖近38亿

今天早盘&#xff0c;A股整体震动调整&#xff0c;白马蓝筹股体现较弱&#xff0c;上证50、沪深300指数均跌超1%。 盘面上&#xff0c;国防军工、造纸、数字钱银、IT设备等板块逆势活跃&#xff0c;酿酒、酒店餐饮、钙钛矿电池、有色等板块跌幅居前。两市半日成交4577亿&#x…...

【编程基础之Python】6、Python基础知识

【编程基础之Python】6、Python基础知识Python基础知识Python的基本要素模块语句表达式注释Python的代码格式Python基础知识 Python 是一种高级的、动态的、解释型的编程语言&#xff0c;具有简单易学、开发效率高、可读性强等特点&#xff0c;广泛应用于数据科学、Web 开发、…...

selenium基本操作

爬虫与反爬虫之间的斗争爬虫&#xff1a;对某个网站数据或图片感兴趣&#xff0c;开始抓取网站信息&#xff1b;网站&#xff1a;请求次数频繁&#xff0c;并且访问ip固定&#xff0c;user_agent也是python&#xff0c;开始限制访问&#xff1b;爬虫&#xff1a;通过设置user_a…...

思科设备命令讲解(超基础二)

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…...

HTML基础(3)

HTML基础单选框、复选框、下拉框文本框< script >标签属性< script >基本使用单选框、复选框、下拉框 文本框 < script >标签属性 type属性定义script元素包含或src引用的脚本语言。属性值是MIME类型&#xff0c;包括text/javascript,text/ecmascript, appl…...

鸿蒙3.0 APP混合开发闪退问题笔记

APP采用cordova混合开发&#xff0c; 鸿蒙2.0以及安卓操作系统正常使用&#xff0c;但是在鸿蒙3.0中出现APP闪退&#xff0c;对APP进行真机调试发现&#xff0c;鸿蒙3.0系统对crosswork插件存在兼容问题&#xff0c;这些问题会导致APP页面加载失败&#xff0c;进而导致App闪退测…...

批量操作文件功能-课后程序(JAVA基础案例教程-黑马程序员编著-第七章-课后作业)

【实验7-1】 批量操作文件功能 任务介绍 1&#xff0e;任务描述 在日常工作中&#xff0c;经常会遇到批量操作系统文件的事情&#xff0c;通常情况下&#xff0c;只能手动重复的完成批量文件的操作&#xff0c;这样很是费时费力。本案例要求编写一个文件管理器&#xff0c;…...

Hadoop3.3.1完全分布式部署

Hadoop目录Hadoop3.3.1完全分布式部署(一)1、HDFS一、安装1、基础安装1.1、配置JDK-181.2、下载并解压hadoop安装包本地运行模式测试 eg:2、完全分布式运行模式1、概要&#xff1a;2、编写集群分发脚本&#xff0c;把1~4步安装的同步到其他服务器&#xff1a;2.1、创建脚本vim …...

SpringMVC中的注解

SpringMVC中的注解 文章目录SpringMVC中的注解RequestMapping注解RequestMapping中的value属性RequestMapping中的method属性派生类PathVariable注解RequestParam注解RequestMapping注解 RequestMapping中的value属性 RequestMapping&#xff1a;既可以标识在方法上也可以标识…...

python+Vue学生作业系统 django课程在线学习网站系统

系统分为学生&#xff0c;教师&#xff0c;管理员三个角色&#xff1a; 学生功能&#xff1a; 1.学生注册登录系统 2.学生查看个人信息&#xff0c;修改个人信息 3.学生查看主页综合评价&#xff0c;查看今日值班信息 4.学生在线申请请假信息&#xff0c;查看请假的审核结果和请…...

CSS 美化网页元素【快速掌握知识点】

目录 一、为什么使用CSS 二、字体样式 三、文本样式 color属性 四、排版文本段落 五、文本修饰和垂直对齐 1、文本装饰 2、垂直对齐方式 六、文本阴影 七、超链接伪类 1、语法 2、示例 3、访问时&#xff0c;蓝色&#xff1b;访问后&#xff0c;紫色&#xff1b; …...

Tableau连接openGauss实践

目录 一、摘要 二、什么是Tableau&#xff1f; 三、安装Tableau 四、安装ODBC驱动 1、openGauss数据库 2、连接前置条件 3、Tableau连接openGauss方式一 4、Tableau连接openGauss方式二 一、摘要 Tableau可以连接到多种数据库&#xff0c;包括关系型数据库&#xff0…...

RabbitMQ 实现延迟队列

业务场景&#xff1a;1.生成订单30分钟未支付&#xff0c;则自动取消&#xff0c;我们该怎么实现呢&#xff1f;2.生成订单60秒后,给用户发短信1 安装rabbitMqwindows安装ubuntu中安装2 添加maven依赖<!-- https://mvnrepository.com/artifact/org.springframework.boot/spr…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...