倍增算法例题,数学倍增算法

首页 > 上门服务 > 作者:YD1662023-06-24 10:36:13

本文作者为潘恺璠,来自柳铁一中曾参加过清北信息学NOIP2017训练营提高组精英班,笔记非常详细。特分享给大家!本文主要记录的是信息学基础算法。

倍增算法例题,数学倍增算法(1)

NOIP2019年冬令营正在报名中,寒假和元旦都会开课,欢迎大家咨询报名!

基础算法

一、倍增算法:

定义:用f[i][j]表示从i位置出发的2j个位置的信息综合(状态)

一个小小的问题:为什么是2j而不是3j,5j,…?因为,假设为kj,整个算法的时间复杂度为(k-1)logk,当k=2时,时间复杂度最小。

这个算法的三个应用:

1.倍增ST表:

应用:这个ST表是用来解决RMQ问题(给你n个数,m次询问,每次询问[l,r]这个区间的最大值),当然,解决RMQ问题是可以用线段树来做的,但是比较麻烦,NOIP 80%是不会用线段树来做,还是用ST表方便。

定义:f[i][j]表示:从i到i 2j-1这2j个位置的元素最大值

初始化:f[i][0]=z[i](第i个位置到第i 20-1个位置的最大值,对应只有一个元素的区间)

转移:f[i][j]=max(f[i][j-1],f[i 2(j-1)][j-1]) (把[i,i 2j-1]这个区间分治为两个区间,这两个区间拼在一起就成了原来一个大的区间,两个区间长度都为2j-1

//建立ST表,引自P2O5 dalao的blog:https://zybuluo.com/P2Oileen/note/816892#应用1-st表

for(int a=1;a<=n;a ) f[a][0]=z[a];//z[]为源数据区间数组

for(int j=1;j<=logn;j )

{

for(int i=1;i z^j-1<=n;i )

f[i][j]=max(f[i][j-1],f[i 2^(j-1)][j-1]);

//乘方是伪代码!

}

//solve

ans=max(f[l][k],f[r-2^k 1][k]);

所以就有两种情况:

①假如区间长度(r-l 1)正好是2k,那么就直接访问f[l][k];

②假如区间长度(r-l 1)是2k p(p<2k),也就说明2k≤(r-l 1)<2k 1,我们可以慢慢地分治下去,利用前缀和,就形成了树状数组那样的东西,一段区间的最大值为 划分成两段区间最大值max1,max2相比取较大 ,但是这样太慢。

有一种更好的方法:其实我们可以用两个长度为2k的区间就一定能把这段[l,r]区间完美覆盖起来,会有重复,但是对求最大值这件事情没有影响,所以 这段区间的最大值=max(f[l][k],f[r-2k 1][k])。

限制:不能用来计算区间和,因为中间有重复部分,还有就是:不支持修改ST表!

2.树上倍增LCA(最近公共祖先):

一般是用线性Tarjan算法来求解(这个Tarjan算法和图论中求有向图强连通分量的Tarjan不同,都是一个人发明的),但是在ZHX十年的信息学奥赛生涯中没有用到这个算法,原因有俩:①没遇到这样的题目②不会!(笑哭脸),有兴趣可以了解一下。

下面介绍倍增的算法:

定义:f[i][j]表示:从树上编号为i的节点向上走2j步会走到哪个节点。

初始化:从j=0开始考虑,也就是从i号节点向上走1步到达的节点,就是i节点的父亲,所以:f[i][0]=father[i]。

转移:f[i][j]=f[f[i][j-1]][j-1],表示:从i节点往上走2j-1步后,再往上走2j-1步到达的点,等价于向上走2j步,因为2j-1 2j-1=2j。(j的范围大概[20,30)≈nlogn,只要保证2j>节点数目n即可)

现在我们构造出来这个f数组,下面介绍如何求两个点的LCA:

定义数组depth[i]表示i这个节点的深度,有以下两种情况:

①depth[p1]==depth[p2],具有一个重要的性质:两个节点同时向上走同样地步数,深度仍然相等,也就是说,我们让p1,p2一步一步地往上走,当走到同一个点时候,这个点一定是LCA!

for(int x=19;x>=0;x--)

{

if(f[p1][x]!=f[p2][x])//如果没有走到同一个点,继续往上走

{

p1=f[p1][x];//p1往上跳

p2=f[p2][x];//p2往上跳

}

}

if(p1!=p2)//为什么要加这个判断?有可能p1=p2么?是有可能的!这个判断是防止一开始跳之前p1=p2这种情况

{

p1=f[p1][0];//因为上面的循环p1,p2只是走到了LCA的下方,这个判断只是处理最后一步:把p1或p2往上跳到它的父亲,就是LCA,返回即可

}

return p1;//p1为LCA,返回

②depth[p1]!=depth[p2],假如p1比较深,就让p1往上跳到和p2深度一样的地方。

利用倍增f数组p1往上跳的方法:定义往上走步数step=depth[p1]-depth[p2],再利用二进制转换!

举个栗子:假如step=13,转为二进制=1101,可以得出13=8 4 1,:先走8步,再走4步,再走1步就好了。

int get_lca(int p1,int p2)

{

if(dpeth[p1]<depth[p2]) swap(p1,p2);

for(int x=19;x>=0;x--)

{

if((2^x)<=depth[p1]-depth[p2]) p1=f[p1][x];

}

}

下面是另一种写法思路就不多讲

int x=0;

while (p1!=p2)

{

if(!x||f[p1][x]!=f[p2][x])

{

p1=f[p1][x];

p2=f[p2][x];

x ;

}

else x--;

}

3.快速幂:

按照一般思路,我们要计算ax的话,要写一个for循环,计算a×a×a×a…这样太™麻烦并且浪费时间!

这里运用倍增来实现快速幂,这也是运用到了分治的思想。

我们要求出x(x=2×k)个a的乘积,就可以分解为x/2个a的乘积的平方,这样就省去一半计算量,如果x是奇数,就在原先的基础上×a就可以了。

int ksm(int a,int x)//求a^x的快速幂 时间复杂度:O(logx)

{

int ans=1;

while(x)

{

if(x&1) ans=(ans*a);//位运算:x&1==1则x为奇数

a=a*a;

x=x>>1;//位运算:右移一位,即将X除以2

}

return ans;

}

二、分治算法:

定义:将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。

这个算法的三个应用:

1.二分查找:

定义:给定排序数组,查询某个数是否在数组中

算法描述:在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止。

bool find(int x)//二分查找x是否在序列z[]中

{

left=0,right=n;

while(left 1!=right)

{

middle=(left right)>>1;

if(z[middle]>=x) right=middle;

else left=middle;

}

}

还可以用lower_bound和upper_bound函数进行优化,用法详见下:

#include <iostream>

#include <algorithm>//必须包含的头文件,C 特有的库函数

using namespace std;

int main()

{

int point[5]={1,3,7,7,9};

int ans;

/*两个函数传入的:(数组名,数组名 数组长度,要查找的数字),返回的是一个地址,减去数组名即可得到数字在数组中的下标*/

ans=upper_bound(point,point 5,7)-point;//按从小到大,7最多能插入数组point的哪个位置

printf("%d ",ans);//输出数字在数组中的下标

ans=lower_bound(point,point 5,7)-point;////按从小到大,7最少能插入数组point的哪个位置

printf("%d\n",ans);//输出数字在数组中的下标

return 0;

}

/*

output:

4 2

*/

2.归并排序(nlogn):

是分治法的典型应用。

归并过程:

比较a[i]和b[j]的大小,若a[i]≤b[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;

否则,将第二个有序表中的元素b[j]复制到r[k]中,并令j和k分别加上1。

如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元

归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

3.快速排序(nlogn):

一般在使用时候直接调用快排函数。

sort(快速排序,是C#特有的,不会退化为n2,比下面三个都要快,一般使用这个)

qsort(最坏情况下为n2,最好是n,期望为nlogn)

merge_sort(归并排序,稳定为nlongn)

heap_sort(堆排序,稳定为nlongn)

倍增算法例题,数学倍增算法(2)

倍增算法例题,数学倍增算法(3)

咨询方式:

司老师 18610112920 赵老师 18610112915 高老师18611056259 老师 18611083835 张老师 18610150289

定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的wx公众平台noipnoi

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.