noip复赛冲刺资料集锦10

《noip复赛冲刺资料集锦10》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ABCAmberCHMConverterTrialversion,http://www.processtext.com/abcchm.html数论算法顶级?下一页1．求两数的最大公约数functiongcd(a,b:integer):integer;beginifb=0thengcd:=a?elsegcd:=gcd(b,amodb);end;2．求两数的最小公倍数functionlcm(a,b:integer):integer;beginifa0doinc(lcm,a);end;3．素数的求法A.小范

2、围内判断一个数是否为质数：functionprime(n:integer):Boolean;varI:integer;begin?forI:=2totrunc(sqrt(n))do?ifnmodI=0thenbegin??prime:=false;exit;?end;??prime:=true;end;B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：proceduregetprime;?var?i,j:longint;?p:array[1..50000]ofboolean;?begin??fillchar(p,sizeof(p),true);p

3、[1]:=false;i:=2;whilei<50000dobeginifpthenbegin?j:=i*2;?whilej<50000dobegin?p[j]:=false;?inc(j,i);?end;end;inc(i);end;l:=0;fori:=1to50000doifpthenbegin?inc(l);pr[l]:=i;end;end;{getprime}functionprime(x:longint):integer;?vari:integer;?begin??prime:=false;fori:=1toldoifpr>=xthenbreak?elseif

4、xmodpr=0thenexit;prime:=true;end;{prime}Page1ABCAmberCHMConverterTrialversion,http://www.processtext.com/abcchm.html图论算法顶级?上一页?下一页1．最小生成树A.Prim算法：procedureprim(v0:integer);?var??lowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;?begin??fori:=1tondobeginlowcost:=cost[v0,i];closest:

5、=v0;end;fori:=1ton-1dobegin{寻找离生成树最近的未加入顶点k}min:=maxlongint;forj:=1tondo?if(lowcost[j]0)thenbegin?min:=lowcost[j];?k:=j;?end;lowcost[k]:=0;{将顶点k加入生成树}?{生成树中增加一条新的边k到closest[k]}{修正各点的lowcost和closest值}forj:=1tondo?ifcost[k,j]

6、losest[j]:=k;?end;end;end;{prim}B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。functionfind(v:integer):integer;{返回顶点v所在的集合}vari:integer;begini:=1;while(i<=n)and(notvinvset)doinc(i);ifi<=nthenfind:=ielsefind:=0;end;procedurekruskal;vartot,i,j:integer;beginfori:=1tondovset:=;{初始化定义n个集合，第I个

7、集合包含一个元素I}p:=n-1;q:=1;tot:=0;{p为尚待加入的边数，q为边集指针}sort;{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}whilep>0dobegin?i:=find(e[q].v1);j:=find(e[q].v2);?ifi<>jthenbegin?inc(tot,e[q].len);?vset:=vset+vset[j];vset[j]:=[];?dec(p);?end;?inc(q);end;writ