一些常用算法模板 - c++编程基础

集 //***************************************************************** 1.求父亲节点并压缩路径 int par[MAX]; int Get_par(int a) //查找a的父亲节点并压缩路径 { if(par[a]==a) return par[a]; //注意语句的顺序 int pa=par[a]; par[a]=Get_par(par[a]); // return par[a]; } 2.合并 void Merge(int a,int b) //合并a,b { int pa,pb; pa=Get_par(a); pb=Get_par(b); par[pa]=pb; } //***************************************************************** 线段树不带延迟更新的操作 //************************************************************ int da[MAXN]; struct node { int left,right,sum;//sum此处灵活处理 }tree[MAXN*4]; //1.建立以left,right为左右边界,将数组da中元素存储在首地址从1开始的线段树tree的叶节点上 void Build( int id,int left,int right) { tree[id].left=left; tree[id].right=right; if(left==right) { //tree[id].sum=da[left];//此处可以直接初始化为对应da[left] return ; } else { int mid =(left+right)>>1; Build(id<<1,left,mid); Build((id<<1)|1,mid+1,right); //tree[id].sum=tree[(id<<1)].sum+tree[(id<<1)|1].sum; } } //2.在线段树的叶节点pos处加val void Updata(int id,int pos,int val) { tree[id].sum+=val; if(tree[id].left==tree[id].right&&tree[id].left==pos) { return ; } int mid=(tree[id].left+tree[id].right)>>1; if(pos<=mid) Updata(id<<1,pos,val); else Updata((id<<1)|1,pos,val); } //3.查询区间[left,right]上的和 int Query(int id,int left,int right) { if(tree[id].left==left&&tree[id].right==right) { return tree[id].sum; } int mid=(tree[id].left+tree[id].right)>>1; if(right<=mid) return Query(id<<1,left,right); if(left>=mid+1) return Query((id<<1)|1,left,right); return Query(id<<1,left,mid)+Query((id<<1)|1,mid+1,right); } //************************************************************ 线段树的延迟更新 //***************************************************** const int MAXN=100000+100; struct node { int left,right,add; int Max; }tree[MAXN*4]; void build(int id, int left, int right) { tree[id].add=0; tree[id].left=left; tree[id].right=right; tree[id].Max=0; if(left==right) { return ; } else { int mid=(left+right)>>1; build(id<<1,left,mid); build((id<<1)|1,mid+1,right); } } void updata(int id,int left,int right,int adi) { if(tree[id].left==left&&tree[id].right==right) { tree[id].add+=adi; return ; } int mid=(tree[id].left+tree[id].right)>>1; if(right<=mid) updata(id<<1,left,right,adi); else if(left>mid) updata((id<<1)|1,left,right,adi); else { updata(id<<1,left,mid,adi); updata((id<<1)|1,mid+1,right,adi); } tree[id].Max=max(tree[id<<1].Max+tree[id<<1].add,tree[(id<<1)|1].Max+tree[(id<<1)|1].add); } int query(int id,int left,int right) { if(tree[id].left==left&&tree[id].right==right) { return tree[id].Max+tree[id].add; } int mid=(tree[id].left+tree[id].right)>>1; if(tree[id].add!=0) { updata(id<<1,tree[id].left,mid,tree[id].add); updata((id<<1)|1,mid+1,tree[id].right,tree[id].add); tree[id].Max=max(tree[id<<1].Max+tree[id<<1].add,tree[(id<<1)|1].Max+tree[(id<<1)|1].add); tree[id].add=0; } if(right<=mid) return query(id<<1,left,right); else if(left>mid ) return query((id<<1)|1,left,right); else { return max(query(id<<1,left,mid),query((id<<1)|1,mid+1,right)); } } //***************************************************************** RMQ问题的ST算法 //***************************************************************** const int MAXN=50000+100; const int Mpow=16;//保证2^(Mpow)>MAXN即可 int data[MAXN]; int Maxdp[MAXN][Mpow]; int Mindp[MAXN][Mpow]; inline int Min(int a,int b) { return a b a:b; } inline void init(int n) { for(int i=1;i<=n;i++) { Mindp[i][0]=Maxdp[i][0]=data[i]; } } //预处理过程，时间复杂度为O(N*log(N)) //ST算法求区间最值 //dp[i][j]表示区间[i,i+2^j-1]最值 //求dp[i][j]时将其分成dp[i][j-1],dp[i+2^(j-1)][j-1] //[i,i+2^j-1]=[i,i+2^(j-1)-1]+[i+2^(j-1),i+2^(j-1)+2^(j-1)-1] inline void Rmp_ST(int n) { int l,s; for(l=1;l<=16;l++) { for(s=1;s<=n;s++) { if(s+(1< 0) { nSum+=C[p]; p-=Lowbit[p]; } return nSum; } //2.修改+初始化 void Modify(int p,int val) //原数组中下表为p的元素+val，导致C[]数组中部分元素值的改变 { while(p<=MAXN-10) { C[p]+=val; p+=Lowbit[p]; } } //************************************************************ 二维树状数组 //***************************************************************** 1.修改 void Add( int y, int x,int a) //原数组中下表为[y][x]的元素+a，导致C[][]数组中部分元素值的改变 { while( y <= s ) { int tmpx = x; while( tmpx <= s ) { C[y][tmpx] += a; tmpx += Lowbit[tmpx]; } y += Lowbit[y]; } } 2.查询 int QuerySum( int y, int x) //查询第1行到第y行，第1列到第x列的和 { int nSum = 0; while( y >

0 ) { int tmpx = x; while( tmpx > 0) { nSum += C[y][tmpx]; tmpx -= Lowbit[tmpx]; } y -= Lowbit[y]; } return nSum; } //***************************************************************** 划分树 //***************************************************************** const int MAXN=100010; int tree[30][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序的数 int toleft[30][MAXN];//toleft[p][i]表示第p层从1到i有多少个数分入左边 //创建划分树 //时间复杂度为O(N*log(N)) void build(int l,int r,int dep) { int i; if(l==r)return; int mid=(l+r)>>1; int same=mid-l+1;//表示等于中间值而且被分入左边的个数 for(i=l;i<=r;i++) if(tree[dep][i] 0) { tree[dep+1][lpos++]=tree[dep][i]; same--; } else //比中间值大分入右边 tree[dep+1][rpos++]=tree[dep][i]; toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数 } build(l,mid,dep+1); build(mid+1,r,dep+1); } //查询区间第k小的数，[L,R]是大区间，[l,r]是要查询的小区间 //时间复杂度为O(log(N)) int query(int L,int R,int l,int r,int dep,int k) { if(l==r)return tree[dep][l]; int mid=(L+R)>>1; int cnt=toleft[dep][r]-toleft[dep][l-1];//[l,r]中位于左边的个数 if(cnt>=k) { //L+要查询的区间前被放在左边的个数 int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; //左端点加上查询区间会被放在左边的个数 int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else { int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } Init() { memset(toleft,0,sizeof(toleft)); for(i=1;i<=n;i++) { scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); } //***************************************************************** 字符串匹配 Manacher算法求最长回文子串 //***************************************************************** const int MAXN=1000000+100; char str1[MAXN*2],str2[MAXN*2];//待处理字符串 int num[MAXN*2]; //将str1变成str2,如abab变成$#a#b#a#b# void init() { int i,id; str2[0]='$'; str2[1]='#'; for(i=0,id=2;str1[i];i++,id+=2) { str2[id]=str1[i]; str2[id+1]='#'; } str2[id]=0; } //Manacher算法求最长回文子串,时间复杂度为O(N) int Manacher() { int i,ans=0,MxR=0,pos=1; for(i=1;str2[i];i++) { if(MxR>i)num[i]=num[pos*2-i]<(MxR-i) num[pos*2-i]:(MxR-i); else num[i]=1; while(str2[i+num[i]]==str2[i-num[i]]) num[i]++; if(num[i]+i>MxR) { MxR=num[i]+i; pos=i; } if(ans 0&&T[i]!=W[j]) j=next[j]; if(W[j]==T[i])j++; if(j==wlen) { ans++; j=next[j]; } } return ans; } //返回模式串T在主串S中首次出现的位置 //返回的位置是从0开始的,若没有找到返回-1。 int KMP_Index(char *W,char *T) { int i=0, j=0,wlen=strlen(W),tlen=strlen(T); getNext(W); while(i str[(j+k)%len]) i=i+k+1; else j=j+k+1; if(i==j)j++; k=0; } } return ++i<++j i:j; } //***************************************************************** 字典树 //************************************************************ //定义字典树结构体 struct Trie { Trie* next[26]; int flag; }; Trie *root; //初始化root void init() { root=new Trie; memset(root,0,sizeof(Trie)); } //2.插入 //将str插入以root为根节点的字典树中 void insert(char *str) { int len = strlen(str); Trie *s = root; for (int i = 0; i < len; i++) { if (s->next[str[i] - 'a']) s = s->next[str[i] - 'a']; else { Trie* t = new Trie; memset(t, 0, sizeof (Trie)); s->next[str[i] - 'a'] = t; s = t; } } s->flag = 1; } //3.查找 //查找字典树中是否有元素str int find(char *str) { int len = strlen(str); Trie *s = root; for (int i = 0; i < len; i++) { if (s->next[str[i] - 'a']) s = s->next[str[i] - 'a']; else return 0; } return s->flag;/////////////////////flag可能不标志为单词结尾 } //5.释放内存空间 //释放以root为根节点的字典树内存空间 void del(Trie *root) { Trie *s = root; for (int i =

一些常用算法模板(二)