【蓝桥每日一题]-倍增(保姆级教程 篇1)

今天讲一下倍增

目录

题目:忠诚

思路:

题目:国旗计划

 思路: 


       

查询迭代类倍增:

    本质是一个一个选区间使总长度达到 M,类似凑一个数。而我们会经常用不大于它最大的二的次幂,减去之后,再重复这个过程,这样这个数的值会减小得非常快,一共只需要减 log(num) 次就可以凑出。

     

题目:忠诚

     

思路:

       

很明显是一道区间最值的问题:也就是著名的RMQ(Range Minimum/Maximum Query)区间最值查询问题(最好会背啊!)

      

首先设置f[i][j]表示从下标i走2*j长度之间的最值,然后依此创建ST表,最后RMQ查询ST表即可

    

      

#include<bits/stdc++.h>            
using namespace std;
#define maxn 100005
int n,m,l,r,a[maxn],f[maxn][22]; //f[i][j](ST表)表示从下标i走2*j长度之间的最值
int RMQ(int l,int r)//RMQ(Range Minimum/Maximum Query)区间最值查询
{
	int k=log2(r-l+1);
	return min(f[l][k],f[r-(1<<k)+1][k]);
}
void ST_create(){//创建ST表
	for(int i=1;i<=n;i++)	f[i][0]=a[i];//初始化
	int k=log2(n);
	for(int j=1;j<=k;j++){//(0已经初始化过了) j是二进制大小
		for(int i=1;i<=n-(1<<j)+1;i++){//对每个点遍历 ,n要减去j的枚举范围:n-2^j+1
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);//递推公式
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);//账数和问题数
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	ST_create();
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d ",RMQ(l,r));
	}
	return 0;
}

      

     

题目:国旗计划

    

思路: 


  求f[i][0]:即每个区间后选的第一个区间。肯定不能两重循环,那时间复杂度就再次变为 O(N^2),这个时候利用题目中提到的一个性质:
“每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含 ”
则对于单调递增l的, r也单调递增,我们只需要找到满足j.l<=r.i 的最后一个区间即可,因此使用双指针,时间复杂度降为 O(N)。
 

#include<bits/stdc++.h>           //国旗计划(环形线段覆盖)(注意线段不会包含)
using namespace std;
#define ll long long
const int N=2e5+10;
int n,m,ans[N];
int st[20][N<<1],s[20][N<<1];//st[i][j]表示从j点为起点的进行2^i次迭代的起点的下标(自身不算)
struct segment{
	int l,r,id;
	inline friend bool operator<(const segment &a,const segment &b){
		return a.l<b.l; //因为线段不会包含,所以l越大自然r越大,即l单增则r单增 !!!
	}
}a[N<<1]; //把环表转换成两倍周长的线性表
void ST_create(){
	for(int i=1,j=1;i<=2*n;i++){
		while(j<=2*n&&a[j].l<=a[i].r)  j++;//寻找下一个起点
		st[0][i]=j-1; //初始化
	}
	for(int i=1;i<=19;i++) //i是二进制大小
		for(int j=1;j<=2*n;j++) //j是对每个点遍历
			st[i][j]=st[i-1][st[i-1][j]];//状态转移方程
}
void search(){
	for(int i=1;i<=n;i++){  
		int up=a[i].l+m,an=0,p=i;//对每个点拆环范围为链范围
		for(int j=19;j>=0;j--)
			if(st[j][p]&&a[st[j][p]].r<up)  //逼近过程
				an+=1<<j,p=st[j][p]; //从下一个点开始逼近
		ans[a[i].id]=an+2;//因为本来就没算本身,然后也不算入终点,所以加2
	}
}
int main(){
	cin>>n>>m; int l,r; //n是边防战士数,m是边防站数
	for(int i=1;i<=n;i++){
		scanf("%d %d",&l,&r);
		if(l>r) r+=m;//破环成链(对战士的覆盖范围)
		a[i].l=l,a[i].r=r,a[i].id=i;//每个战士的编号
	}
	sort(a+1,a+n+1); //方便初始时找下一个转移点
	for(int i=1;i<=n;i++) {
		a[i+n].l=a[i].l+m,a[i+n].r=a[i].r+m; //破环成链(对链边界上每个边防站士都再点缀一下)
	}
	ST_create(); //创建ST表
	search();	//对每个点进行查询
	for(int i=1;i<=n;i++)
	printf("%d ",ans[i]);
	return 0;
}

 可以总结一下倍增使用的场合:
1.(最值类)RMQ区间最值
2.(迭代类)同一件事完成多次。且当“一次做一件事”可以优化为“一次做多件事”。(快速幂也是这个道理)
双指针扫描的应用:
两个指针代表的内容均只增不减
 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/115829.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ubuntu22.04安装公司安全VPN的方案

公司为了安全设置VPN,但是liunxVPN工具不好用&#xff0c;今天找了一个好用的VPN工具 https://www.leagsoft.com/doc/article/103107.html 有各种版本&#xff0c;支持IOS和android等系统。 安装步骤 1/下载安装程序 https://www.leagsoft.com/doc/article/103107.html 2 …

vim三种模式,文本操作(操作字符/光标,列出行号可视化块模式/多文件查看)

目录 vim--文本编辑器 功能 基本概念 命令/默认模式 插入模式 底行模式 文本操作 引入 移动光标位置 删除字符 -- x/dd 复制/粘贴字符 -- yw/yyp 替换文本 -- r / %s 底行模式 全局替换 -- /g 撤销操作 -- u / ctrlr 修改字符 -- cw 示例 跳行 -- ctrlg 底行…

Vue的虚拟dom和diff算法

一、是什么 diff算法是一种通过同层级的树节点进行比较的高效算法 diff算法是为了进行精细化比对&#xff0c;最小量更新的 特点&#xff1a; 1.同级比较&#xff1a;比较只在同层级进行 2.首尾指针法&#xff1a;从两边向组件比较 比较方式/策略&#xff1a;深度优先&#xff…

家政APP开发服务同城预约维修接单管理系统软件小程序

家政服务小程序是一个基于移动端的家政服务平台&#xff0c;为用户提供方便快捷的家政服务。以下是小程序的主要功能&#xff1a; 1. 家政服务内容展示&#xff1a;商家可以在小程序中展示各种家政服务项目&#xff0c;如清洁、保洁、保姆、月嫂、钟点工等。用户可以浏览服务信…

Ubuntu下安装vscode,并解决终端打不开vscode的问题

Visual Studio Code安装 1&#xff0c;使用 apt 安装 Visual Studio Code 在官方的微软 Apt 源仓库中可用。按照下面的步骤进行即可&#xff1a; 以 sudo 用户身份运行下面的命令&#xff0c;更新软件包索引&#xff0c;并且安装依赖软件&#xff1a; sudo apt update sud…

[自定义 Vue 组件] 小尾巴下拉菜单组件(2.0) TailDropDown

文章归档&#xff1a;https://www.yuque.com/u27599042/coding_star/kcoem6dgyn8drglb [自定义 Vue 组件] 下拉菜单(1.0) DropDownMenu&#xff1a;https://www.yuque.com/u27599042/coding_star/llltv52tchmatwg4 组件效果示例 组件所依赖的常量 在 src 目录下&#xff0c;创…

Redis中Hash类型的命令

目录 哈希类型的命令 hset hget hexists hdel hkeys hvals hgetall hmget hlen hsetnx hincrby hincrbyfloat 内部编码 Hash类型的应用场景 作为缓存 哈希类型和关系型数据库的两点不同之处 缓存方式对比 Redis自身已经是键值对的结构了,Redis自身的键值对就…

顺序栈练习

顺序栈练习 相关内容&#xff1a; 1.判断顺序栈栈满的两种方式 2.一张图理解栈顶指针加加减减的问题 3.栈的顺序存储结构&#xff08;顺序栈&#xff09; //顺序栈的初始化、判空、入栈、出栈、读取栈顶元素 //顺序栈的结构&#xff1a;数组、栈顶指针(本质是下标) #include&…

【k8s】pod详解

一、Pod介绍 1、Pod的基础概念 Pod是kubernetes中最小的资源管理组件&#xff0c;Pod也是最小化运行容器化应用的资源对象&#xff0c;一个pod代表着集群中运行的一个进程。kubernetes中其它大多数组件都是围绕着pod来进行支持和扩展pod功能的。 例如&#xff0c;用于管理po…

最新ChatGPT商业运营系统源码+支持GPT4/支持ai绘画+支持Midjourney绘画

一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…

2023年【山东省安全员C证】考试内容及山东省安全员C证复审考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 山东省安全员C证考试内容是安全生产模拟考试一点通总题库中生成的一套山东省安全员C证复审考试&#xff0c;安全生产模拟考试一点通上山东省安全员C证作业手机同步练习。2023年【山东省安全员C证】考试内容及山东省安…

MYSQL体系结构总结

&#xff08;笔记整理自b站马士兵教育课程&#xff09; MYSQL总体分为服务层和存储引擎层。 一、服务层 功能&#xff1a; 1、连接&#xff1a;管理连接&#xff0c;权限验证。 2、解析器&#xff1a;词法分析&#xff0c;语法分析。 3、优化器&#xff1a;执行计划生成…

【漏洞复现】fastjson_1.2.24_unserializer_rce

感谢互联网提供分享知识与智慧&#xff0c;在法治的社会里&#xff0c;请遵守有关法律法规 文章目录 1.1、漏洞描述1.2、漏洞等级1.3、影响版本1.4、漏洞复现1、基础环境2、漏洞检测3、漏洞验证 1.5、深度利用1、GetShell 说明内容漏洞编号漏洞名称fastjson 1.2.24 反序列化导致…

归并排序--C语言实现

1. 简述 归并排序的原理是将&#xff0c;两个较大的数组分为大小几乎一致的两个数组。 再将两个数组进行合并成新的有序数组。 合并两个数组的时候需要额外的一个数组的空间。 2. 实现 上图说明过程 代码 #include <stdio.h>void Merge(int *arr, int *tmp, int …

【漏洞复现】Apache_HTTPD_未知后缀名解析

感谢互联网提供分享知识与智慧&#xff0c;在法治的社会里&#xff0c;请遵守有关法律法规 upload-labs/Pass-07 上传1.php文件 <?php eval($_REQUEST[6868]);phpinfo();?>访问/upload/1.php.jaychou 蚁剑连接

Git https方式拉的代码IDEA推送代码报错

报错信息 fatal: could not read Username for ‘https://codehub-cn-south-1.devcloud.huaweicloud.com’: No such file or directory 18:18:39.885: [recovery_pattern] git -c credential.helper -c core.quotepathfalse -c log.showSignaturefalse push --progress --porc…

docker compose实现容器编排

Compose 使用的三个步骤&#xff1a; 使用 Dockerfile 定义应用程序的环境 使用 compose.yml 定义构成应用程序的服务&#xff0c;这样它们可以在隔离环境中一起运行 最后&#xff0c;执行 docker compose up 命令来启动并运行整个应用程序 为什么需要docker compose Dock…

【C++】多态 ⑫ ( 多继承 “ 弊端 “ | 多继承被禁用的场景 | 菱形继承结构的二义性 | 使用虚继承解决菱形继承结构的二义性 )

文章目录 一、多继承 " 弊端 "1、多继承被禁用的场景2、多继承弊端 二、代码示例 - 多继承弊端1、错误示例 - 菱形继承结构的二义性2、代码示例 - 使用虚继承解决菱形继承结构的二义性 一、多继承 " 弊端 " 1、多继承被禁用的场景 禁止使用多继承的场景 : …

C++ Qt 学习(二):常用控件使用与界面布局

1. Qt 布局详解 ui 设计器设计界面很方便&#xff0c;为什么还要手写代码&#xff1f; 更好的控制布局更好的设置 qss代码复用 完全不会写 Qt 布局&#xff0c;很麻烦&#xff0c;怎么学会手写布局&#xff1f; 看 Qt 自己怎么写改良 Qt 的布局写法 1.1 水平布局 #include …

C++笔记之vector的成员函数swap()和data()

C笔记之vector的成员函数swap()和data() 标准C中的std::vector类确实有swap()和data()这两个成员函数。下面是它们的简要描述&#xff1a; swap(): std::vector的swap()成员函数用于交换两个向量的内容&#xff0c;实现了高效的交换操作&#xff0c;不需要复制向量的元素。这…