Noip常用算法大全

Noip 常用算法大全一、数论算法1求两数的最大公约数functiongcd(a,b:integer):integer;beginifb=0thengcd:=aelsegcd:=gcd(b.amodb);end;2求两数的最小公倍数functionlcm(a,b:integer):integer;beginifa0doinc(lcm,a);end;3素数的求法A.小范围内判断一个数是否为质数：functionprime(n:integer):Boolean;varI:integer;beginforI:=2totrunc(sqrt(n)doifnmodI=0thenbeginprime:=false;exit;end;prime:=true;end;B.判断longint范围内的数是否为素数(包含求50000以内的素数表):proceduregetprime;vari,j:longint;p:array1.50000ofboolean;beginfillchar(p,sizeof(p),true);p1:=false;i:=2;whilei50000dobeginifpithenbeginj:=i*2;whilej=xthenbreakelseifxmodpri=0thenexit;prime:=true;end;prime二、图论算法1最小生成树A.Prim算法：procedureprim(v0:integer);varlowcost,closest:array1.maxnofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcost:=costv0,i;closest:=v0;end;fori:=1ton-1dobegin寻找离生成树最近的未加入顶点kmin:=maxlongint;forj:=1tondoif(lowcostjmin)and(lowcostj0)thenbeginmin:=lowcostj;k:=j;end;lowcostk:=0;将顶点k加入生成树生成树中增加一条新的边k到closestk修正各点的lowcost和closest值forj:=1tondoifcostk,jlwocostjthenbeginlowcostj:=costk,j;closestj:=k;end;end;end;primB.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。functionfind(v:integer):integer;返回顶点v所在的集合vari:integer;begini:=1;while(i=n)and(notvinvset)doinc(i);ifi0dobegini:=find(eq.v1);j:=find(eq.v2);ifijthenbegininc(tot,eq.len);vset:=vset+vsetj;vsetj:=;dec(p);end;inc(q);end;writeln(tot);end;2.最短路径A.标号法求解单源点最短路径:vara:array1.maxn,1.maxnofinteger;b:array1.maxnofinteger;b指顶点i到源点的最短路径mark:array1.maxnofboolean;procedurebhf;varbest,best_j:integer;beginfillchar(mark,sizeof(mark),false);mark1:=true;b1:=0;1为源点repeatbest:=0;fori:=1tondoIfmarkthen对每一个已计算出最短路径的点forj:=1tondoif(notmarkj)and(ai,j0)thenif(best=0)or(b+ai,j0thenbeginbbest_j:=best；markbest_j:=true;end;untilbest=0;end;bhfB.Floyed算法求解所有顶点对之间的最短路径:procedurefloyed;beginforI:=1tondoforj:=1tondoifaI,j0thenpI,j:=IelsepI,j:=O;pI,j表示I到j的最短路径上j的前驱结点fork:=1tondo枚举中间结点fori:=1tondoforj:=1tondoifai,k+aj,kai,jthenbeginai,j:=ai,k+ak,j;pI,j:=pk,j;end;end;C.Dijkstra算法:vara:array1.maxn,1.maxnofinteger;b,pre:array1.maxnofinteger;pre指 最 短 路 径 上I的 前 驱 结 点mark:array1.maxnofboolean;proceduredijkstra(v0:integer);beginfillchar(mark,sizeof(mark),false);fori:=1tondobegind:=av0,i;ifd0thenpre:=v0elsepre:=0;end;markv0:=true;repeat每循环一次加入一个离1集合最近的结点并调整其他结点的参数min:=maxint;u:=0;u记录离1集合最近的结点fori:=1tondoif(notmark)and(dmin)thenbeginu:=i;min:=d;end;ifu0thenbeginmarku:=true;fori:=1tondoif(notmark)and(au,i+dud)thenbegind:=au,i+du;pre:=u;end;end;untilu=0;end;3.计算图的传递闭包ProcedureLonglink;VarT:array1.maxn,1.maxnofboolean;BeginFillchar(t,sizeof(t),false);Fork:=1tondoForI:=1tondoForj:=1tondoTI,j:=tI,jor(tI,kandtk,j);End;4无向图的连通分量A.深度优先proceduredfs(now,color:integer);beginfori:=1tondoifanow,iandc=0thenbegin对结点I染色c:=color;dfs(I,color);end;end;B宽度优先(种子染色法)5关键路径几个定义：顶点1为源点，n为汇点。a.顶点事件最早发生时间Vej,Vej=maxVej+wI,j，其中Ve(1)=0;b.顶点事件最晚发生时间Vlj,VIj=minVlj-wI,j，其中Vl(n)=Ve(n);c.边活动最早开始时间Ee,若边I由j,k表示，则Ee=Vej;d.边活动最晚开始时间El,若边I由j,k表示，则El=Vlk-wj,k;若Eej=Elj，则活动j为关键活动，由关键活动组成的路径为关键路径。求解方法：a.从源点起topsort，判断是否有回路并计算Ve;b.从汇点起topsort，求Vl;c.算Ee和El;6拓扑排序找入度为0的点，删去与其相连的所有边，不断重复这一过程。例寻找一数列，其中任意连续p项之和为正，任意q项之和为负，若不存在则输出NO.7.回路问题Euler回路(DFS)定义：经过图的每条边仅一次的回路。(充要条件：图连同且无奇点)Hamilton回路定义：经过图的每个顶点仅一次的回路。一笔画充要条件：图连通且奇点个数为0个或2个。9判断图中是否有负权回路Bellman-ford算法x,y,t分别表示第I条边的起点，终点和权。共n个结点和m条边。procedurebellman-fordbeginforI:=0ton-1dod:=+infinitive;d0:=0;forI:=1ton-1doforj:=1tomdo枚举每一条边ifdxj+tjdyjthendyj:=dxj+tj;forI:=1tomdoifdxj+tjdyjthenreturnfalseelsereturntrue;end;10第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。三、背包问题*部分背包问题可有贪心法求解：计算Pi/Wi数据结构：w:第i个背包的重量；P：第i个背包的价值；10-1背包：每个背包只能使用一次或有限次(可转化为一次)：A.求最多可放入的重量。NOIP2001装箱问题有一个箱子容量为v(正整数，oWvW20000),同时有n个物品(oWnW30),每个物品有一个体积(正整数)。要求从n个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。l搜索方法proceduresearch(k,v:integer);搜索第k个物品，剩余空间为vvari,j:integer;beginifv=bestthenexit;sn为前n个物品的重量和ifkwkthensearch(k+l,v-wk);search(k+l,v);end;end;lDPFI,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现:将最优化问题转化为判定性问题fI,j=fi-l,j-w(w=j0thenifj+now=ntheninc(cj+now,aj);a:=c;end;2可重复背包A求最多可放入的重量。FI,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。状态转移方程为fI,j=fI-1,j一w*k(k=1.jdivw)B.求可以放入的最大价值。USACO1.2ScoreInflation进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti(解答此题所需的时间)和一个si(解答此题所得的分数)，现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。*易想到：fi,j=maxfi-k*wj,j-1+k*pj(0=k=0ThenBegint:=problemj.point+fi-problemj.time;IftfThenf:=t;End;Writeln(fM);End.C.求恰好装满的情况数。Ahoi2001Problem2求自然数n本质不同的质数和的表达式的数目。思路一，生成每个质数的系数的排列，在一一测试，这是通法proceduretry(dep:integer);vari,j:integer;begincal;此过程计算当前系数的计算结果，now为结果ifnownthenexit;剪枝ifdep=l+1thenbegin生成所有系数cal;ifnow=ntheninc(tot);exit;end;fori:=0tondivprdepdobeginxsdep:=i;try(dep+1);xsdep:=0;end;end;思路二，递归搜索效率较高proceduretry(dep,rest:integer);vari,j,x:integer;beginif(rest0thenfork:=1tondivnowdoifj+now*k=ntheninc(cj+now*k,aj);a:=c;end;mainbeginread(now);读入第一个物品的重量i:=0;a为背包容量为i时的放法总数whilei=ndobegina:=1;inc(i,now);end;定义第一个物品重的整数倍的重量a值为1，作为初值fori:=2tovdobeginread(now);update;动态更新end;writeln(an);四、排序算法1.快速排序：procedureqsort(l,r:integer);vari,j,mid:integer;begini:=l;j:=r;mid:=a(l+r)div2;将当前序列在中间位置的数定义为中间数repeatwhileaimiddodec(j);在右半部分寻找比中间数小的数ifij;ifljthenqsort(l,j);若未到两个数的边界，则递归搜索左右区间ifirthenqsort(i,r);end;sortB.插入排序：思路：当前al.ai-l已排好序了，现要插入a使a1.a有序。procedureinsert_sort;vari,j:integer;beginfori:=2tondobegina0:=a;j:=i-1;whilea0ajthenswap(a,aj);end;D.冒泡排序procedurebubble_sort;vari,j,k:integer;beginfori:=1ton-1doforj:=ndowntoi+1doifajaj-1thenswap(aj,aj-1);每次比较相邻元素的关系end;E.堆排序：proceduresift(i,m:integer);调整以i为根的子树成为堆,m为结点总数vark:integer;begina0:=a;k:=2*i;在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+lwhilek=mdobeginif(km)and(akak+1)theninc(k);找出ak与ak+1中较大值ifa0akthenbegina:=ak;i:=k;k:=2*i;endelsek:=m+1;end;a:=a0;将根放在合适的位置end;procedureheapsort;varj:integer;beginforj:=ndiv2downto1dosift(j,n);forj:=ndownto2dobeginswap(a1,aj);sift(1,j-1);end;end;F.归并排序a为序列表，tmp为辅助数组proceduremerge(vara:listtype;p,q,r:integer);将已排序好的子序列ap.q与aq+l.r合并为有序的tmpp.rvarI,j,t:integer;tmp:listtype;begint:=p;i:=p;j:=q+l;t为tmp指针，I,j分别为左右子序列的指针while(tr)or(a=aj)满足取左边序列当前元素的要求thenbegintmpt:=a;inc(i);endelsebegintmpt:=aj;inc(j);end;inc(t);end;fori:=ptordoa:=tmp;end;mergeproceduremerge_sort(vara:listtype;p,r:integer);合并排序ap.rvarq:integer;beginifprthenbeginq:=(p+r-l)div2;merge_sort(a,p,q);merge_sort(a,q+l,r);merge(a,p,q,r);end;end;mainbeginmerge_sort(a,1,n);end.G.基数排序思想：对每个元素按从低位到高位对每一位进行一次排序五、高精度计算高精度数的定义：typehp=array1.maxlenofinteger;1高精度加法procedureplus(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa0b0thenlen:=a0elselen:=b0;fori:=1tolendobegininc(c,a+b);ifc10thenbegindec(c,10);inc(ci+1);end;进位end;ifclen+10theninc(len);c0:=len;end;plus2高精度减法proceduresubstract(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa0b0thenlen:=a0elselen:=b0;fori:=1tolendobegininc(c,a-b);ifc1)and(clen=0)dodec(len);c0:=len;end;3高精度乘以低精度proceduremultiply(a:hp;b:longint;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);len:=a0;fori:=1tolendobegininc(c,a*b);inc(ci+1,(a*b)div10);c:=cmod10;end;inc(len);while(clen=10)dobegin处理最高位的进位clen+1:=clendiv10;clen:=clenmod10;inc(len);end;while(len1)and(clen=0)dodec(len);若不需进位则调整lenc0:=len;end;multiply4高精度乘以高精度procedurehigh_multiply(a,b:hp;varc:hpvari,j,len:integer;beginfillchar(c,sizeof(c),0);fori:=1toa0doforj:=1tob0dobegininc(ci+j-1,a*bj);inc(ci+j,ci+j-1div10);ci+j-1:=ci+j-1mod10;end;len:=a0+b0+1;while(len1)and(clen=0)dodec(len);c0:=len;end;5高精度除以低精度proceduredevide(a:hp;b:longint;varc:hp;vard:longint);c:=adivb;d:=amodbvari,len:integer;beginfillchar(c,sizeof(c),0);len:=a0;d:=0;fori:=lendownto1dobegind:=d*10+a;c:=ddivb;d:=dmodb;end;while(len1)and(clen=0)thendec(len);c0:=len;end;6高精度除以高精度procedurehigh_devide(a,b:hp;varc,d:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);fillchar(d,sizeof(d),0);len:=a0;d0:=1;fori:=lendownto1dobeginmultiply(d,10,d);d1:=a;while(compare(d,b)=0)do即d=bbeginSubtract(d,b,d);inc(c);end;end;while(len1)and(c.slen=0)dodec(len);c.len:=len;end;六、树的遍历1已知前序中序求后序procedureSolve(pre,mid:string);vari:integer;beginif(pre=)or(mid=)thenexit;i:=pos(pre1,mid);solve(copy(pre,2,i),copy(mid,1,i-1);solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i);post:=post+pre1;加上根，递归结束后post即为后序遍历end;2已知中序后序求前序procedureSolve(mid,post:string);vari:integer;beginif(mid=)or(post=)thenexit;i:=pos(postlength(post),mid);pre:=pre+postlength(post);加 上 根，递 归 结 束 后pre即 为 前 序 遍 历solve(copy(mid,1,I-1),copy(post,1,I-1);solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i);end;3已知前序后序求中序的一种functionok(s1,s2:string):boolean;vari,l:integer;p:boolean;beginok:=true;l:=length(s1);fori:=1toldobeginp:=false;forj:=1toldoifs1=s2jthenp:=true;ifnotpthenbeginok:=false;exit;end;end;end;proceduresolve(pre,post:string);vari:integer;beginif(pre=)or(post=)thenexit;i:=0;repeatinc(i);untilok(copy(pre,2,i),copy(post,1,i);solve(copy(pre,2,i),copy(post,1,i);midstr:=midstr+pre1;solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1);end;七进制转换1任意正整数进制间的互化除n取余2实数任意正整数进制间的互化乘n取整3负数进制：设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负进制下的数：-RW-2,-3,-4,.-20八全排列与组合的生成1排列的生成：(1.n)proceduresolve(dep:integer);vari:integer;beginifdep=n+1thenbeginwriteln(s);exit;end;fori:=1tondoifnotusedthenbegins:=s+chr(i+ord(0);used:=true;solve(dep+1);s:=copy(s,1,length(s)-1);used:=false;end;end;2组合的生成(1.n中选取k个数的所有方案)proceduresolve(dep,pre:integer);vari:integer;beginifdep=k+1thenbeginwriteln(s);exit;end;fori:=1tondoif(notused)and(ipre)thenbegins:=s+chr(i+ord(0);used:=true;solve(dep+1,i);s:=copy(s,1,length(s)-1);used:=false;end;end;九.查找算法1折半查找functionbinsearch(k:keytype):integer;varlow,hig,mid:integer;beginlow:=1;hig:=n;mid:=(low+hig)div2;while(amid.keyk)and(lowkthenhig:=mid-1elselow:=mid+1;mid:=(low+hig)div2;end;iflowhigthenmid:=0;binsearch:=mid;end;2树形查找二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值查找functiontreesrh(k:keytype):pointer;varq:pointer;beginq:=root;while(qvnil)and(qkeyvk)doifkvqkeythenq:=qA.leftelseq:=qA.right;treesrh:=q;end;十、贪心*会议问题(1)n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。解：按每项活动的结束时间进行排序，排在前面的优先满足。(2)会议室空闲时间最少。3)每个客户有一个愿付的租金，求最大利润。(4)共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。十一、回溯法框架1.n皇后问题proceduretry(i:byte);varj:byte;beginifi=n+1thenbeginprint;exit;end;forj:=1tondoifaandbj+iandcj-ithenbeginx:=j;aj:=false;bj+i:=false;cj-i:=false;try(i+1);aj:=true;bi+j:=true;cj-i:=true;end;end;2.HanoiTowerh(n)=2*h(n-1)+1h(1)=1初始所有铜片都在a柱上procedurehanoi(n,a,b,c:byte);将第n块铜片从a柱通过b柱移到c柱上beginifn=0thenexit;hanoi(n-1,a,c,b);将上面的n-1块从a柱通过c柱移到b柱上write(n,movedfrom,a,to,c);hanoi(n-1,b,a,c);将b上的n-1块从b柱通过a柱移到c柱上end;初始铜片分布在3个柱上，给定目标柱goalh1.3,0.n存放三个柱的状态，now与nowp存最大的不到位的铜片的柱号和编号,hI,0存第I个柱上的个数。Proceduremove(k,goal:integer);将最大不到位的k移到目标柱goal上BeginIfk=0thenexit;ForI:=1to3doForj:=1tohanI,0doIfhI,j=kthenbeginnow:=I;nowp:=j;end;找到k的位置Ifnowgoalthenbegin若未移到目标Move(k-1,6-now-goal);剩下的先移到没用的柱上Writeln(kmovedfromnowtogoal);Hgoal,hgoal,0+1:=hnow,nowp;hnow,nowp:=0;Inc(hgoal,0);dec(hnow,0);Move(k-1,goal);剩下的移到目标上End;十二、DFS框架NOIP2001数的划分procedurework(dep,pre,s:longint);入口为work(1,1,n)dep为当前试放的第dep个数,pre为前一次试放的数,s为当前剩余可分的总数varj:longint;beginifdep=nthenbeginifs=pretheninc(r);exit;end;forj:=pretosdiv2dowork(dep+1,j,s-j);end;类似：proceduretry(dep:integer);vari:integer;beginifdep=kthenbeginiftot=adep-1theninc(sum);exit;end;fori:=adep-1tototdiv2dobeginadep:=i;dec(tot,i);try(dep+1);inc(tot,i);end;end;try十三、BFS框架IOI94房间问题head:=1;tail:=0;whiletail=1)and(I=L.len)thenwhilejvIdobeginp:=pnext;inc(j);end;loc:=p;end;2单链表的插入操作procedureinsert(L:linklist;I:integer;x:datatype);varp,q:pointer;beginp:=loc(L,I);new(q);qA.data:=x;qA.next:=pA.next;pA.next:=q;inc(L.len);end;3单链表的删除操作proceduredelete(L:linklist;I:integer);varp,q:pointer;beginp:=loc(L,I-1);q:=pnext;pnext:=qnext;