常用算法汇总.docx

常用算法汇总.docx

《常用算法汇总.docx》由会员分享，可在线阅读，更多相关《常用算法汇总.docx（28页珍藏版）》请在冰点文库上搜索。

常用算法汇总

常用算法汇总

1.快速排序

procedurequicksort（l,r:

longint）;

vari,j,x:

longint;

begin

i:

=l;

j:

=r;

x:

=a[random（r-l+1）+l];

repeat

whilea[i]

whilea[j]>xdodec（j）;

ifi<=jthen

begin

swap（a[i],a[j]）;

inc（i）;dec（j）;

end;

untili>j;

ifi

ifj>lthenquicksort（l,j）;

end;

2.线段树（附中1505）

procedureinsert1（x,k,l,r,p:

longint）;

varmid:

longint;

begin

if（pr）thenexit;

ifl=rthen

begin

sum[k]:

=x;

exit;

end;

mid:

=（l+r）shr1;

insert1（x,kshl1,l,mid,p）;

insert1（x,kshl1+1,mid+1,r,p）;

sum[k]:

=sum[kshl1]+sum[kshl1+1];

end;

procedureinsert2（x,k,l,r,a,b:

longint）;

varmid:

longint;

begin

if（l>b）or（r

if（l>=a）and（r<=b）then

begin

f[k]:

=true;

sum[k]:

=x*（r-l+1）;

exit;

end;

mid:

=（l+r）shr1;

iff[k]=truethen

begin

f[k]:

=false;

f[kshl1]:

=true;

f[kshl1+1]:

=true;

sum[kshl1]:

=sum[k]div（r-l+1）;

sum[kshl1+1]:

=sum[kshl1]*（r-mid）;

sum[kshl1]:

=sum[kshl1]*（mid-l+1）;

end;

insert2（x,kshl1,l,mid,a,b）;

insert2（x,kshl1+1,mid+1,r,a,b）;

sum[k]:

=sum[kshl1]+sum[kshl1+1];

end;

functionask（k,l,r,a,b:

longint）:

longint;

varmid,o:

longint;

begin

if（l>b）or（r

begin

ask:

=0;

exit;

end;

if（l>=a）and（r<=b）then

begin

ask:

=sum[k];

exit;

end;

mid:

=（l+r）shr1;

iff[k]=truethen

begin

f[k]:

=false;

f[kshl1]:

=true;

f[kshl1+1]:

=true;

sum[kshl1]:

=sum[k]div（r-l+1）;

sum[kshl1+1]:

=sum[kshl1]*（r-mid）;

sum[kshl1]:

=sum[kshl1]*（mid-l+1）;

end;

ask:

=ask（kshl1,l,mid,a,b）+ask（kshl1+1,mid+1,r,a,b）;

end;

3.树状数组

functionlowbit（x:

longint）:

longint;

begin

lowbit:

=xand（-x）;

end;

procedureadd（x:

longint）;

begin

whilex<=ndo

begin

inc（c[x]）;

x:

=x+lowbit（x）;

end;

end;

functionsum（x:

longint）:

longint;

begin

sum:

=0;

whilex>0do

begin

sum:

=sum+c[x];

x:

=x-lowbit（x）;

end;

end;

4.最短路径

（1）单源最短路径dijkstra

proceduredijkstra;

vari,j,w,min:

longint;

begin

fori:

=1ton-1do

begin

min:

=maxlongint;

forj:

=1tondo

ifnot（f[j]）and（dist[j]

begin

min:

=dist[j];

w:

=j;

end;

f[w]:

=true;

forj:

=1tondo

ifnot（f[j]）and（a[w,j]>0）and（dist[w]+a[w,j]

dist[j]:

=a[w,j]+dist[w];

end;

end;

（2）单源最短路径dijkstra+heap

procedureswap（x,y:

longint）;

vart:

longint;

begin

t:

=num[heap[x]];

num[heap[x]]:

=num[heap[y]];

num[heap[y]]:

=t;

t:

=heap[x];

heap[x]:

=heap[y];

heap[y]:

=t;

end;

procedureinsert（x,s:

longint）;

varp:

longint;

begin

heap[s+1]:

=x;

p:

=s+1;

num[x]:

=p;

whilep>1do

begin

ifdis[heap[pdiv2]]>dis[heap[p]]thenswap（pdiv2,p）elsebreak;

p:

=pdiv2;

end;

end;

proceduredui（x,s:

longint）;

varl,r,min:

longint;

begin

l:

=2*x;

r:

=2*x+1;

if（l

=lelsemin:

=x;

if（r

=r;

ifmin<>xthen

begin

swap（x,min）;

dui（min,s）;

end;

end;

procedurechange（x:

longint）;

varp:

longint;

begin

p:

=x;

whilep>1do

begin

ifdis[heap[pdiv2]]>dis[heap[p]]thenswap（pdiv2,p）elsebreak;

p:

=pdiv2;

end;

end;

proceduremain;

begin

fori:

=2tondoinsert（i,i-2）;

fori:

=ndownto2do

begin

w:

=heap[1];

num[heap[i]]:

=1;

heap[1]:

=heap[i];

dui（1,i）;

f[w]:

=true;

forj:

=1toa[w,0]do

ifnot（f[a[w,j]]）and（dis[w]+b[w,a[w,j]]

begin

dis[a[w,j]]:

=dis[w]+b[w,a[w,j]];

change（num[a[w,j]]）;

end;

end;

end;

（3）每对顶点间的最短路径floyed

procedurefloyed;

begin

fori:

=1tondo

forj:

=1tondo

ifi<>jthen

fork:

=1tondo

if（i<>k）and（j<>k）and（a[i,k]+a[j,k]

a[i,j]:

=a[i,k]+a[j,k];

end;

（4）单源最短路径SPFA

functionspfa（s:

longint）:

boolean;

varx,y,i,p,q:

longint;

b,num:

array[0..7000]oflongint;

c:

array[1..1000]ofboolean;

begin

x:

=0;

y:

=0;

b[0]:

=s;

fori:

=1tondo

begin

b[i]:

=0;

c[i]:

=false;

num[i]:

=0;

end;

dis[s]:

=0;

repeat

p:

=b[x];

c[p]:

=false;

fori:

=1tot[p,0]do

begin

q:

=t[p,i];

ifdis[p]+a[p,q]

begin

dis[q]:

=dis[p]+a[p,q];

ifnot（c[q]）then

begin

inc（num[q]）;

ifnum[q]>nthenexit（false）;

c[q]:

=true;

y:

=ymodn+1;

b[y]:

=q;

end;

end;

end;

x:

=xmodn+1;

untilx>y;

spfa:

=true;

end;

5.最小生成树

（1）prim

procedureprim;

begin

fori:

=1ton-1do

begin

b[i,1]:

=1;

b[i,2]:

=i+1;

b[i,3]:

=a[1,i+1];

end;

fork:

=1ton-1do

begin

min:

=maxlongint;

m:

=k;

forj:

=kton-1do

ifb[j,3]

begin

min:

=b[j,3];

m:

=j;

end;

s:

=s+min;

ifk<>mthen

begin

b[n+1]:

=b[k];

b[k]:

=b[m];

b[m]:

=b[n+1];

end;

j:

=b[k,2];

fori:

=k+1ton-1do

begin

d:

=b[i,2];

o:

=a[d,j];

ifo

begin

b[i,1]:

=j;

b[i,3]:

=o;

end;

end;

end;

end;

（2）kruskal

procedurekruskal;

vari,o,x,y:

longint;

begin

o:

=0;

s:

=0;

fori:

=1tomdo

begin

x:

=bcj（a[i,1]）;

y:

=bcj（a[i,2]）;

ifx<>ythen

begin

inc（o）;

f[x]:

=y;

ifs

=a[i,3];

end;

ifo=n-1thenbreak;

end;

writeln（s）;

end;

6.网络流

（1）最大流

functionfind:

boolean;

varf:

array[1..111]ofboolean;

b:

array[0..111]oflongint;

u,i,x,y:

longint;

begin

fillchar（f,sizeof（f）,false）;

fillchar（b,sizeof（b）,0）;

fillchar（fa,sizeof（fa）,0）;

b[0]:

=1;

f[1]:

=true;

x:

=0;

y:

=0;

repeat

u:

=b[x];

fori:

=1tondo

if（a[u,i]>0）and（not（f[i]））then

begin

inc（y）;

b[y]:

=i;

f[i]:

=true;

fa[i]:

=u;

ifi=nthenexit（true）;

end;

inc（x）;

untilx>y;

exit（false）;

end;

procedureadd;

varflow,x,y:

longint;

begin

x:

=n;

flow:

=big;

repeat

y:

=fa[x];

ifflow>a[y,x]thenflow:

=a[y,x];

x:

=y;

untilx=1;

x:

=n;

repeat

y:

=fa[x];

a[y,x]:

=a[y,x]-flow;

a[x,y]:

=a[x,y]+flow;

x:

=y;

untilx=1;

ans:

=ans+flow;

end;

（2）最小费用最大流

functionfind:

boolean;

varx,y,u,i:

longint;

d:

array[1..1000]oflongint;

c:

array[1..100]ofboolean;

begin

filldword（dis,sizeof（dis）shr2,big）;

filldword（mf,sizeof（mf）shr2,big）;

fillchar（d,sizeof（d）,0）;

fillchar（fa,sizeof（fa）,0）;

fillchar（c,sizeof（c）,false）;

d[0]:

=1;

dis[1]:

=0;

x:

=0;

y:

=0;

repeat

u:

=d[x];

c[u]:

=false;

fori:

=1tondo

iff[u,i]>0then

begin

ifdis[u]+a[u,i]

begin

dis[i]:

=dis[u]+a[u,i];

fa[i]:

=u;

ifmf[u]>f[u,i]thenmf[i]:

=f[u,i]elsemf[i]:

=mf[u];

ifnot（c[i]）then

begin

c[i]:

=true;

y:

=（y+1）mod1000;

d[y]:

=i;

end;

end;

end;

x:

=（x+1）mod1000;

untilx>y;

exit（dis[n]

end;

procedureadd;

varx,y:

longint;

begin

x:

=n;

repeat

y:

=fa[x];

f[y,x]:

=f[y,x]-mf[n];

f[x,y]:

=f[x,y]+mf[n];

ans:

=ans+a[y,x]*mf[n];

x:

=y;

untilx=1;

end;

7.二分图最大匹配Hungary

functionzgl（x:

longint）:

boolean;

vari:

longint;

begin

ifx=0thenexit（true）;

fori:

=1tomdo

ifnot（b[i]）and（a[x,i]）then

begin

b[i]:

=true;

ifzgl（f[i]）then

begin

f[i]:

=x;

exit（true）;

end;

end;

exit（false）;

end;

functionhungary:

longint;

vari:

longint;

begin

hungary:

=0;

fori:

=1tondo

begin

fillchar（b,sizeof（b）,false）;

ifzgl（i）theninc（hungary）;

end;

end;

8.欧拉回路

proceduredfs（x:

longint）;

vari:

longint;

begin

fori:

=1tondo

ifa[x,i]>0then

begin

dec（a[x,i]）;

dec（a[i,x]）;

dec（b[x]）;

dec（b[i]）;

dfs（i）;

end;

inc（ans）;

c[ans]:

=x;

d2[x]:

=true;

end;

9.平衡树

procedurelx（varx:

longint）;

vary:

longint;

begin

y:

=l[x];

l[x]:

=r[y];

r[y]:

=x;

v[y]:

=v[x];

v[x]:

=v[l[x]]+v[r[x]]+1;

x:

=y;

end;

procedurerx（varx:

longint）;

vary:

longint;

begin

y:

=r[x];

r[x]:

=l[y];

l[y]:

=x;

v[y]:

=v[x];

v[x]:

=v[l[x]]+v[r[x]]+1;

x:

=y;

end;

procedureinsert（varx:

longint;k:

longint）;

begin

ifx=0then

begin

inc（tot）;

v[tot]:

=1;

x:

=tot;

t[tot]:

=k;

p[tot]:

=random（maxlongint）;

end

else

begin

inc（v[x]）;

ifk<=t[x]then

begin

insert（l[x],k）;

ifp[x]

end

else

begin

insert（r[x],k）;

ifp[x]

end;

end;

end;

functionfind（x,k:

longint）:

longint;

begin

ifv[l[x]]+1=kthenexit（t[x]）

else

begin

ifv[l[x]]+1>kthenfind:

=find（l[x],k）

elsefind:

=find（r[x],k-v[l[x]]-1）;

end;

end;

10.并查集

functionbcj（x:

longint）:

longint;

begin

iff[x]=0thenexit（x）;

f[x]:

=bcj（f[x]）;

exit（f[x]）;

end;

11.堆

proceduredui（x,s:

longint）;

varl,r,min:

longint;

begin

l:

=2*x;

r:

=2*x+1;

if（l

=lelsemin:

=x;

if（r

=r;

ifmin<>xthen

begin

swap（x,min）;

dui（min,s）;

end;

end;

12.字符串匹配KMP

procedureget_next（t:

string）;

varj,k:

integer;

begin

j:

=1;k:

=0;

whilej

begin

if（k=0）or（t[j]=t[k]）then

begin

j:

=j+1;k:

=k+1;

next[j]:

=k;

end

elsek:

=next[k];

end;

end;

functionKMP（s:

string;t:

string）:

integer;

vari,j:

integer;

begin

get_next（t）;

index:

=0;

i:

=1;j:

=1;

while（i<=Length（s））and（j<=Length（t））do

begin

if（j=0）or（s[i]=t[j]）then

begini:

=i+1;j:

=j+1;end

elsej:

=next[j];

ifj>Length（t）thenindex:

=i-Length（t）;

end;

end;

13.高精度计算

（1）高精度比大小

functioncompare（a,b:

arr）:

longint;

vari:

longint;

begin

fori:

=101downto1do

begin

ifa[i]>b[i]thenexit

（1）;

ifa[i]

end;

exit（0）;

end;

（2）高精度+单精度

functionjia1（a:

arr;x:

longint）:

arr;

vari:

longint;

begin

a[1]:

=a[1]+x;

i:

=1;

whilea[i]>=10do

begin

a[i+1]:

=a[i+1]+a[i]div10;

a[i]:

=a[i]mod10;

inc（i）;

end;

exit（a）

end;

（3）高精度+高精度

functionjia2（a,b:

arr）:

arr;

vari:

longint;

c:

arr;

begin

fillchar（c,sizeof（c）,0）;

fori:

=1to101do

begin

c[i]:

=c[i]+a[i]+b[i];

c[i+1]:

=c[i+1]+c[i]div10;

c[i]:

=c[i]mod10;

end;

exit（c）;

end;

（4）高精度-单精度

functionjian1（a:

arr;x:

longint）:

arr;

vari:

longint;

begin

a[1]:

=a[1]-x;

i:

=1;

repeat

ifa[i]<0then

begin

a[i]:

=a[i]+10;

a[i+1]:

=a[i+1]-1;

end;

inc（i）;

untila[i]>=0;

exit（a）;

end;

（5）高精度-高精度

functionjian2（a,b:

arr）:

arr;

vari:

longint;

begin

fori:

=1to101do

begin

ifa[i]

begin

a[i]:

=a[i]+10;

a[i+1]:

=a[i+1]-1;

end;

a[i]:

=a[i]-b[i];

end;

exit（a）;

end;

（6）高精度*单精度

functioncheng1