noip2010 基础算法整理

《noip2010 基础算法整理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP2010基础算法整理（Pascal版）IKoala.Guan2010-10-7修正I.排序算法A.快速排序(Quicksort)procedureqs(p,q:longint);vari,j,k,mid:longint;Beginmid:=a[(p+q)div2];i:=p;j:=q;repeatwhilea[i]{!}middodec(j);ifi<=j{!}thenbegink:=a[i];a[i]:=a[j];a[j]:=k;inc(i);dec(j);end;u

2、ntili>j;ifp

3、k:=2*i;end{Exchange.}elsek:=m+1;{Break.}NOIP2010基础算法整理-1-end;a[i]:=a[0];{Placethecorrectleaf.}end;Beginreadln(n);fori:=1tondoread(a[i]);forj:=ndiv2downto1dosift(j,n);{Arrangethetree.}forj:=ndownto2dobeginswap(1,j);{Makeeveryleafintotheroot.}sift(1,j-1);{Arrangethetre

4、e.}end;fori:=1ton-1dowrite(a[i],'');writeln(a[n]);end.II.数论算法A.最大公约数和最小公倍数functiongcd(a,b:integer):integer;beginifb=0thengcd:=aelsegcd:=gcd(b,amodB);end;functionlcm(a,b:integer):integer;beginifa0doinc(lcm,a);end;NOIP2010基础算法整理-2-II

5、I.图论算法A.最小生成树——Prim算法procedureprim(v0:integer);varlowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcost[i]:=cost[v0,i];closest[i]:=v0;end;fori:=1ton-1dobegin{寻找离生成树最近的未加入顶点k}min:=maxlongint;forj:=1tondoif(lowcost[j]

6、]<>0)thenbeginmin:=lowcost[j];k:=j;end;lowcost[k]:=0;{将顶点k加入生成树}{生成树中增加一条新的边k到closest[k]}{修正各点的lowcost和closest值}forj:=1tondoifcost[k,j]

7、边加入最小生成树。functionfind(v:integer):integer;{返回顶点v所在的集合}vari:integer;begini:=1;while(i<=n)and(notvinvset[i])doinc(i);ifi<=nthenfind:=ielsefind:=0;end;procedurekruskal;vartot,i,j:integer;beginfori:=1tondovset[i]:=[i];{初始化定义n个集合，第i个集合包含一个元素i}p:=n-1;q:=1;tot:=0;{p为尚待加入的边数，

8、q为边集指针}sort;{对所有边按权值递增排序，存于e[i]中，e[i].v1与e[i].v2为边i所连接的两个顶点的序号，e[i].len为第i条边的长度}whilep>0dobegini:=find(e[q].v1);j:=find(e[q].v2);if