【蓝桥每日一题]-倍增（保姆级教程篇1）-CSDN博客

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

今天讲一下倍增

题目忠诚

思路

题目国旗计划

思路

查询迭代类倍增

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

题目忠诚

思路

很明显是一道区间最值的问题也就是著名的RMQRange 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)//RMQRange 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;
}