模板
关注
分享
扫一扫
淼润淽涵
这个作者很懒，什么都没留下…
展开
-
最长回文子串(Manacher算法----时间复杂度O(n) )
简介马拉车算法是一种在O(n)时间内求一个字符串的最长回文子串的算法思路对于最长回文子串,我们可以有很多朴素算法比如穷举所有子串,然后验证这些子串是否是回文的,这样的复杂度是O(n^3) 比如我们遍历数组,对于每一个元素,我们都认为其是某个回文子串的中心,我们同时向两边伸展,然后取其中的最大值,这样的算法的复杂度是O(n^2)马拉车算法就是在方法2的基础上进行了扩展,...原创 2019-10-27 21:21:45 · 1118 阅读 · 0 评论 -
主席树----求静态区间[l,r]第k大数和第k小数
Description给出一个长度为n的序列a，给出m次查询，每次查询区间[l,r]中第k大的数Input第一行两个整数n和m,分别表示序列长度和查询次数，第二行n个整数表示序列a，之后m行每行三个整数l,r和k表示一次查询Output对于每次查询，输出区间[l,r]中第k大的数Sample Input7 21 5 2 6 3 7 41 5 32 7 1...原创 2019-10-20 21:29:30 · 545 阅读 · 0 评论 -
树状数组
对于一个n元素的数组A[n]，可执行如下操作（单点修改，区间查询）：Add(I, d)：让A[i]变成A[i]+d。Query(L, R)：返回A[L]+A[L+1]+…+A[R]。注意：树状数组只能计算A[1]开始的和，A[0]这个元素是不能用的。上面单点修改和区间查询操作复杂度都是O(logn)。其实树状数组还可以处理区间更新，单点查询的问题。如HDU 155...原创 2019-10-05 11:03:14 · 180 阅读 · 0 评论 -
线段树
线段树单点add，区间sum查询的模板#include<cstdio>#include<cstring>using namespace std;const int maxn=50000+5; //线段树需要维护的信息int sum[maxn*4];#define lson i*2, l, m#define rson i*2+1, m+1, r ...原创 2019-09-29 17:31:42 · 171 阅读 · 0 评论 -
RMQ算法
RMQ算法可以解决对于一个整数数组(也可以是其他可比较大小的元素类型)的任意区间[L, R]查询最值问题。 RMQ能在经过O(nlogn)的时间预处理后，做到O(1)时间复杂度的任意区间最大最小值查询。RMQ算法模板 RMQ问题的简单应用。 即给你一个数组，要你输出每次询问区间内的最大值-最小值的差。#include<cstdio>#...原创 2019-09-23 19:01:41 · 291 阅读 · 0 评论 -
KMP算法
对于KMP算法，都会涉及到两个串一个是待匹配串 char T[1000]//待匹配串 待匹配串的长度定为n一个是模板串 char P[100]//模板串 模板串的长度定为m要知道KMP的F[i]数组求得的数值就是串P中的[1,i-1]的后缀与串P中的[0,i-2]前缀的最大匹配长度。对于KMP算法一般会利用到两个函数 v...转载 2019-08-28 15:26:29 · 268 阅读 · 0 评论