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

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...