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

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...