网站开发投标文件,wordpress如何创建项目,南山网站建设 信科网络,中国建设协会网站本文摘自清北OI学堂内部笔记#xff0c;作者潘恺璠#xff0c;来自柳铁一中曾参加过清北训练营提高组精英班#xff0c;主要记录的是信息学基础算法。笔记非常详细#xff0c;特分享给大家#xff01; NOIP2019年夏令营正在报名中#xff0c;6大校区10种班型#xff0c;… 本文摘自清北OI学堂内部笔记作者潘恺璠来自柳铁一中曾参加过清北训练营提高组精英班主要记录的是信息学基础算法。笔记非常详细特分享给大家 NOIP2019年夏令营正在报名中6大校区10种班型可前往微信noipnoi报名 一、倍增算法 定义用f[i][j]表示从i位置出发的2j个位置的信息综合状态 一个小小的问题为什么是2j而不是3j,5j,…因为假设为kj整个算法的时间复杂度为(k-1)logk当k2时时间复杂度最小。 这个算法的三个应用 1.倍增ST表 应用这个ST表是用来解决RMQ问题给你n个数m次询问每次询问[l,r]这个区间的最大值当然解决RMQ问题是可以用线段树来做的但是比较麻烦NOIP 80%是不会用线段树来做还是用ST表方便。 定义f[i][j]表示从i到i2j-1这2j个位置的元素最大值 初始化f[i][0]z[i]第i个位置到第i20-1个位置的最大值对应只有一个元素的区间 转移f[i][j]max(f[i][j-1],f[i2(j-1)][j-1]) 把[i,i2j-1]这个区间分治为两个区间这两个区间拼在一起就成了原来一个大的区间两个区间长度都为2j-1 //建立ST表引自P2O5 dalao的bloghttps://zybuluo.com/P2Oileen/note/816892#应用1-st表 for(int a1;an;a) f[a][0]z[a];//z[]为源数据区间数组 for(int j1;jlogn;j) { for(int i1;iz^j-1n;i) f[i][j]max(f[i][j-1],f[i2^(j-1)][j-1]); //乘方是伪代码 } //solve ansmax(f[l][k],f[r-2^k1][k]); 所以就有两种情况 ①假如区间长度(r-l1)正好是2k那么就直接访问f[l][k] ②假如区间长度(r-l1)是2kp(p2k)也就说明2k≤(r-l1)2k1我们可以慢慢地分治下去利用前缀和就形成了树状数组那样的东西一段区间的最大值为 划分成两段区间最大值max1,max2相比取较大 但是这样太慢。 有一种更好的方法其实我们可以用两个长度为2k的区间就一定能把这段[l,r]区间完美覆盖起来会有重复但是对求最大值这件事情没有影响所以 这段区间的最大值max(f[l][k],f[r-2k1][k])。 限制不能用来计算区间和因为中间有重复部分还有就是不支持修改ST表 2.树上倍增LCA最近公共祖先 一般是用线性Tarjan算法来求解这个Tarjan算法和图论中求有向图强连通分量的Tarjan不同都是一个人发明的但是在ZHX十年的信息学奥赛生涯中没有用到这个算法原因有俩①没遇到这样的题目②不会笑哭脸有兴趣可以了解一下。 下面介绍倍增的算法 定义f[i][j]表示从树上编号为i的节点向上走2j步会走到哪个节点。 初始化从j0开始考虑也就是从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-12j-12j。j的范围大概[20,30)≈nlogn只要保证2j节点数目n即可 现在我们构造出来这个f数组下面介绍如何求两个点的LCA 定义数组depth[i]表示i这个节点的深度有以下两种情况 ①depth[p1]depth[p2]具有一个重要的性质两个节点同时向上走同样地步数深度仍然相等也就是说我们让p1,p2一步一步地往上走当走到同一个点时候这个点一定是LCA for(int x19;x0;x--) { if(f[p1][x]!f[p2][x])//如果没有走到同一个点继续往上走 { p1f[p1][x];//p1往上跳 p2f[p2][x];//p2往上跳 } } if(p1!p2)//为什么要加这个判断有可能p1p2么是有可能的这个判断是防止一开始跳之前p1p2这种情况 { p1f[p1][0];//因为上面的循环p1p2只是走到了LCA的下方这个判断只是处理最后一步把p1或p2往上跳到它的父亲就是LCA返回即可 } return p1;//p1为LCA返回 ②depth[p1]!depth[p2]假如p1比较深就让p1往上跳到和p2深度一样的地方。 利用倍增f数组p1往上跳的方法定义往上走步数stepdepth[p1]-depth[p2]再利用二进制转换 举个栗子假如step13转为二进制1101可以得出13841,先走8步再走4步再走1步就好了。 int get_lca(int p1,int p2) { if(dpeth[p1]depth[p2]) swap(p1,p2); for(int x19;x0;x--) { if((2^x)depth[p1]-depth[p2]) p1f[p1][x]; } } 下面是另一种写法思路就不多讲 int x0; while (p1!p2) { if(!x||f[p1][x]!f[p2][x]) { p1f[p1][x]; p2f[p2][x]; x; } else x--; } 3.快速幂 按照一般思路我们要计算ax的话要写一个for循环计算a×a×a×a…这样太™麻烦并且浪费时间 这里运用倍增来实现快速幂这也是运用到了分治的思想。 我们要求出x(x2×k)个a的乘积就可以分解为x/2个a的乘积的平方这样就省去一半计算量如果x是奇数就在原先的基础上×a就可以了。 int ksm(int a,int x)//求a^x的快速幂 时间复杂度O(logx) { int ans1; while(x) { if(x1) ans(ans*a);//位运算x11则x为奇数 aa*a; xx1;//位运算右移一位即将X除以2 } return ans; } 二、分治算法 定义将一个规模为N的问题分解为K个规模较小的子问题这些子问题相互独立且与原问题性质相同。求出子问题的解就可得到原问题的解。 这个算法的三个应用 1.二分查找 定义给定排序数组查询某个数是否在数组中 算法描述在查找所要查找的元素时首先与序列中间的元素进行比较如果大于这个元素就在当前序列的后半部分继续查找如果小于这个元素就在当前序列的前半部分继续查找直到找到相同的元素或者所查找的序列范围为空为止。 bool find(int x)//二分查找x是否在序列z[]中 { left0,rightn; while(left1!right) { middle(leftright)1; if(z[middle]x) rightmiddle; else leftmiddle; } } 还可以用lower_bound和upper_bound函数进行优化用法详见下 #include iostream #include algorithm//必须包含的头文件C特有的库函数 using namespace std; int main() { int point[5]{1,3,7,7,9}; int ans; /*两个函数传入的(数组名数组名数组长度要查找的数字)返回的是一个地址减去数组名即可得到数字在数组中的下标*/ ansupper_bound(point,point5,7)-point;//按从小到大7最多能插入数组point的哪个位置 printf(%d ,ans);//输出数字在数组中的下标 anslower_bound(point,point5,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 转载于:https://www.cnblogs.com/qbxt/p/10984714.html
