当前位置: 首页 > 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;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...