当前位置:首页 >> 学科竞赛 >>

noip标程(精华)


标程复习 1.排序(从小到大排序) ①选择排序(效率不高,3000 左右就挂了) for i:=1 to n-1 do for j:=i to n do if a[i]>a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; ②桶排序(小学生排序) 就是 hash 排序,出现就标 hash,输出 ③快速排序(最快是 nlog2(

n)) procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l;j:=r; x:=q[(i+j) div 2]; repeat while q[i]<x do inc(i); while q[j]>x do dec(j); if not(i>j) then begin y:=q[i];q[i]:=q[j];q[j]:=y; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; ④堆排序(最差效率为 nlog2n) type arr=array[1..32767]of integer; var n,i,t:integer; a:arr; procedure heap(var r:arr;nn,ii:integer); //之所以又定义一次参数数组是 为了排不同的数组 var i,j,x:integer; begin i:=ii; x:=r[i]; j:=ii*2; //假设父节点的左儿子大于右儿子 while j<=nn do begin if (j<nn)and(r[j]<r[j+1]) then inc(j); //假设不成立就赋为右儿 子

if x<r[j] then begin r[i]:=r[j];i:=j;j:=2*i;end //使父节点始终大 于子节点 else j:=nn+1; //跳出循环 end; r[i]:=x; //细节 end; begin readln(n); for i:=1 to n do read(a[i]); for i:=n div 2 downto 1 do heap(a,n,i); //初始化,建立大根堆 for i:=n downto 2 do //维护大根堆 begin t:=a[1];a[1]:=a[i];a[i]:=t; heap(a,i-1,1); end; for i:=1 to n do write(a[i],' '); end. ⑤拓扑排序(工程调度) procedure top; var i,t:longint; begin while p1<=p2 do begin t:=way[p1]; for I:= 1 to ss[t] do begin dec(ru[da[t].ss[i]]); if ru[da[t].ss[i]]=0 then begin inc(p2); way[p2]:=da[t].ss[i]; end; end; inc(p1); end; if p2<>n then writeln(f2,'NO') else begin for I:= 1 to p2 do write(f2,way[i],' '); end; end;

begin f1:=input;f2:=output; reset(f1); rewrite(f2); readln(f1,n); while not eof (f1) do begin readln(f1,a,b); inc(ss[a]); da[a].ss[ss[a]]:=b; inc(ru[b]); end; p:=0; for I:= 1 to n do if ru[i]=0 then begin inc(p); way[p]:=i; end; p1:=1;p2:=p; top; close(f2); end. ⑥归并排序(我认为不常用到) {a 为序列表,tmp 为辅助数组} procedure merge(var a:listtype; p,q,r:integer); {将已排序好的子序列 a[p..q]与 a[q+1..r]合并为有序的 tmp[p..r]} var I,j,t:integer; tmp:listtype; begin t:=p;i:=p;j:=q+1;{t 为 tmp 指针,I,j 分别为左右子序列的指针} while (t< =r) do begin if (i< =q){左序列有剩余} and ((j >r) or (a[i]< =a[j])) {满足取左边序列 当前元素的要求} then begin tmp[t]:=a[i]; inc(i); end else begin tmp[t]:=a[j];inc(j); end; inc(t); end; for i:=p to r do a[i]:=tmp[i]; end;{merge}

procedure merge_sort(var a:listtype; p,r: integer); {合并排序 a[p..r]} var q:integer; begin if p< >r then begin q:=(p+r-1) div 2; merge_sort (a,p,q); http://www.nocow.cn/index.php/Pascal_program(第 10/17 页) 2010-10-6 11:18:30 NOCOW - Pascal program merge_sort (a,q+1,r); merge (a,p,q,r); end; end; {main} begin merge_sort(a,1,n); end. ⑦合并排序(丑数) ⑧插入排序(O(n^2)) procedure insert_sort(k,m:word); {k 为当前要插入的数, m 为插入位置的 指针} var i:word; p:0..1; http://www.nocow.cn/index.php/Pascal_program(第 8/17 页) 2010-10-6 11:18:30 NOCOW - Pascal program begin p:=0; for i:=m downto 1 do if k=a[i] then exit; repeat If k >a[m] then begin a[m+1]:=k; p:=1; end else begin a[m+1]:=a[m]; dec(m); end; until p=1; end;{insert_sort} ⑨基数排序(不常用) 思想:对每个元素按从低位到高位对每一位进行一次排序 ⑩冒泡排序 procedure sort; var i,j,k:integer; begin

for i:=n downto 1 do for j:=1 to i-1 do if a[j] >a[i] then begin a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]; end; end; 小结:排序很重要,一些基本排序算法一定要掌握牢! 2.最大公约数和最小公倍数 ①最大公约数 var a,b:integer; function find(a,b:integer):integer; begin if b=0 then find:=a else find:=find(b,a mod b); end; begin readln(a,b); writeln(find(a,b)); end. ②最小公倍数(就是两数之积除以他们的最大公约数) var a,b,k:integer; function find(a,b:integer):integer; begin if b=0 then find:=a else find:=find(b,a mod b); end; begin readln(a,b); k:=find(a,b); writeln(a*b div k); end. 3.素数(即质数)(1000000 以内都适用) ①筛选法(这种方法比较快,效率高) readln(n);(读入 N); for i:=2 to n do a[i]:=true;(先将 a 数组全部定义为素数,即用 true 代表素 数,false 合数) for i:=2 to trunc(sqrt(n)) do(1 to n 也可以,不过比较浪费时间) begin if a[i]=true then (如果这个数是素数,则执行.这样比较省时间) begin for j:=2 to n div i do a[i*j]=false;(将一切可以被 2、3、4...整除的数全部定义为合数) end;

素数表建完了,接下来搜索有哪些是素数 for i:=1 to n do if a[i]=true then write(i,' ');(如果这个数等于 true,即为素数,就输出). 同样,判断一个数是不是素数,只需在上面程序中改一下即可: k:=0; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then k:=1; 就是根据素数定义求素数:只能被它本身及 1 整除的数是素数,所以有: for i:=2 to n do begin k:=0; for j:=1 to i do if i mod j=0 then inc(k); if k=2 then i 是素数 end; //这是搜索素数 同样,判断一个数是否是素数,只需: k:=0; for i:=1 to n do if n mod i=0 then inc(k); if k=2 then n 是素数 ③速度最快的! 这是我从一位大牛那得到的,速度比普通的筛选法快接近一倍! var i,j,k,l,m,n,head:longint; prime:array[1..10000000] of boolean; p:array[1..10000000] of longint; procedure start; begin assign(output,'prime.out'); rewrite(output); readln(n); fillchar(prime,sizeof(prime),1); prime[1]:=false; fillchar(p,sizeof(p),0); head:=0; for i:=2 to n do begin if prime[i] then begin inc(head);p[head]:=i;end; for j:=1 to head do begin if p[j]*i>n then break; prime[p[j]*i]:=false; if i mod p[j]=0 then break; end;

end; for i:=1 to head do writeln(p[i]); end; begin start; end. 只是稍微有点烦而已! 小结:实在没法就打表! 4.树的遍历 ①已知前序中序求后序 procedure Solve(pre,mid:string); var i:integer; begin if (pre=) or (mid=) then exit; i:=pos(pre[1],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+pre[1]; {加上根,递归结束后 post 即为后序遍历} end; ②已知中序后序求前序 procedure Solve(mid,post:string); var i:integer; begin if (mid=) or (post=) then exit; i:=pos(post[length(post)],mid); pre:=pre+post[length(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; ③已知前序后序求中序 function ok(s1,s2:string):boolean; var i,l:integer; p:boolean; begin ok:=true; l:=length(s1); for i:=1 to l do begin p:=false; for j:=1 to l do if s1[i]=s2[j] then p:=true; if not p then begin ok:=false;exit;end; end; end;

procedure solve(pre,post:string); var i:integer; begin if (pre=) or (post=) then exit; i:=0; repeat inc(i); until ok(copy(pre,2,i),copy(post,1,i)); solve(copy(pre,2,i),copy(post,1,i)); midstr:=midstr+pre[1]; solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1) ); end; 5.求图的弱连通子图(DFS) procedure dfs ( now,color: integer); begin for i:=1 to n do if a[now,i] and c[i]=0 then begin c[i]:=color; dfs(I,color); end; end; 6.链表 ①链表的定位函数 loc(I:integer):pointer; {寻找链表中的第 I 个结点的指针} procedure loc(L:linklist; I:integer):pointer; var p:pointer; j:integer; begin p:=L.head; j:=0; if (I >=1) and (I< =L.len) then while j< I do begin p:=p^.next; inc(j); end; loc:=p; end; ②单链表的插入操作 procedure insert(L:linklist; I:integer; x:datatype); var p,q:pointer; begin p:=loc(L,I); new(q); q^.data:=x; q^.next:=p^.next; p^.next:=q;

inc(L.len); end; ③单链表的删除操作 procedure delete(L:linklist; I:integer); var p,q:pointer; begin p:=loc(L,I-1); q:=p^.next; p^.next:=q^.next; dispose(q); dec(L.len); end; ④双链表的插入操作(插入新结点 q) p:=loc(L,I); new(q); q^.data:=x; q^.pre:=p; q^.next:=p^.next; p^.next:=q; q^.next^.pre:=q; ⑤双链表的删除操作 p:=loc(L,I); {p 为要删除的结点} p^.pre^.next:=p^.next; dispose(p); 7.查找算法 ①折半查找(二分查找) function binsearch(k:keytype):integer; var low,hig,mid:integer; begin low:=1;hig:=n; mid:=(low+hig) div 2; while (a[mid].key< >k) and (low< =hig) do begin if a[mid].key >k then hig:=mid-1 else low:=mid+1; mid:=(low+hig) div 2; end; if low >hig then mid:=0; binsearch:=mid; end; ②树形查找 二叉排序树:每个结点的值都大于其左子树任一结点的值而小于其右子树任一 结点的值。 查找

function treesrh(k:keytype):pointer; var q:pointer; begin q:=root; while (q< >nil) and (q^.key< >k) do if k< q^.key then q:=q^.left else q:=q^.right; treesrh:=q; end; 8.排列组合 ①排列的生成: (1..n) procedure solve(dep:integer); var i:integer; begin if dep=n+1 then begin writeln(s);exit; end; for i:=1 to n do if not used[i] then begin s:=s+chr(i+ord('0'));used[i]:=true; solve(dep+1); s:=copy(s,1,length(s)-1); used[i]:=false; end; end; ②组合的生成(1..n 中选取 k 个数的所有方案) procedure solve(dep,pre:integer); var i:integer; begin if dep=k+1 then begin writeln(s);exit; end; for i:=1 to n do if (not used[i]) and (i >pre) then begin s:=s+chr(i+ord('0'));used[i]:=true; solve(dep+1,i); s:=copy(s,1,length(s)-1); used[i]:=false; end; end; 9.高精 ①高精加 function add(a,b:arr):arr; var len,i:longint; begin len:=max(a[0],b[0]);

for i:= 1 to len do begin a[i]:=a[i]+b[i]; if a[i]>9 then begin a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; end; end; if a[len+1]<>0 then inc(len); a[0]:=len; exit(a); end; ②高精乘 function time(a,b:arr):arr; var len,i,j:longint;c:arr; begin fillchar(c,sizeof(c),0); for i:= 1 to a[0] do for j:= 1 to b[0] do begin c[i+j-1]:=a[i]*b[j]+c[i+j-1]; if c[i+j-1]>9 then begin c[i+j]:=c[i+j]+c[i+j-1] div 10; c[i+j-1]:=c[i+j-1] mod 10; end; end; len:=a[0]+b[0]+1; while c[len]=0 do dec(len); c[0]:=len; exit(c); end; ③高精减 procedure del; var len,i:longint; begin for I:= 1 to a[-1] do begin if a[i]<b[i] then begin a[i]:=a[i]+10; dec(a[i+1]); end;

a[i]:=a[i]-b[i]; end; len:=a[0]; while a[len]=0 then dec(len); a[0]:=len; end; ④低精除 procedure cf(b:int64); var d,i:longint;c:array [0..2100] of longint; begin fillchar(c,sizeof(c),0); c[0]:=a[0];d:=0; for i:=a[0] downto 1 do begin d:=d*10+a[i]; c[i]:=d div b; d:=d mod b; end; a:=c; while (a[0]>1)and(a[a[0]]=0) do dec(a[0]); end; 10. 最小生成树 ①Prim 算法 procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcost[i]:=cost[v0,i]; closest[i]:=v0; end; for i:=1 to n-1 do begin {寻找离生成树最近的未加入顶点 k} min:=maxlongint; for j:=1 to n do if (lowcost[j]< min) and (lowcost[j]< >0) then begin min:=lowcost[j]; k:=j; end; lowcost[k]:=0; {将顶点 k 加入生成树} {生成树中增加一条新的边 k 到 closest[k]} {修正各点的 lowcost 和 closest 值}

for j:=1 to n do if cost[k,j]< lwocost[j] then begin lowcost[j]:=cost[k,j]; closest[j]:=k; end; end; end;{prim} ②Kruskal 算法:(贪心) 按权值递增顺序删去图中的边,若不形成回路则将此 边加入最小生成树。 function find(v:integer):integer; {返回顶点 v 所在的集合} var i:integer; begin i:=1; while (i< =n) and (not v in vset[i]) do inc(i); if i< =n then find:=i else find:=0; end; procedure kruskal; var tot,i,j:integer; begin for i:=1 to n do vset[i]:=[i];{初始化定义 n 个集合,第 I 个集合包含一个元 素 I} p:=n-1; q:=1; tot:=0; {p 为尚待加入的边数,q 为边集指针} sort; {对所有边按权值递增排序,存于 e[I]中,e[I].v1 与 e[I].v2 为边 I 所连接的 两个顶点的序号,e[I].len 为第 I 条边的长度} while p >0 do begin i:=find(e[q].v1);j:=find(e[q].v2); if i< >j then begin inc(tot,e[q].len); vset[i]:=vset[i]+vset[j];vset[j]:=[]; dec(p); end; inc(q); end; writeln(tot); end; 11.最短路径 ①Dijkstra 以下是我做的一个求坐标系内两点最短路线的程序,任意两点之间的路径为 坐标的点距离: var i,j,n,m,x,y,s,t:integer; d:array[1..100]of integer;

a:array[1..100,1..2]of integer; b:array[1..100,1..100]of real; c:array[1..100]of real; w:real; begin readln(n); for i:=1 to n do begin readln(a[i,1],a[i,2]); c[i]:=327670; end; readln(m); for i:=1 to m do begin readln(x,y); b[x,y]:=sqrt(sqr(a[x,1]-a[y,1])+sqr(a[x,2]-a[y,2])); //求坐标 间距离 b[y,x]:=b[x,y]; end; readln(s,t);d[s]:=1; for i:=1 to n do if b[s,i]>0 then c[i]:=b[s,i]; //主程序 c[s]:=0; m:=s; for i:=1 to n-3 do begin w:=327670; for j:=1 to n do if (c[j]<w)and(d[j]=0) then begin w:=c[j];x:=j;end; for j:=1 to n do if b[x,j]>0 then if c[x]+b[x,j]<c[j] then c[j]:=c[x]+b[x,j]; d[x]:=1; end; writeln(c[t]:0:2); end. 其实会了 spfa 就不用再用 Dijkstra(spfa 效率更高,更好)! 但是,堆优化后的 Dijkstra 效率最高!如下: procedure change(var a,b:rec); var c:rec; begin c:=a;a:=b;b:=c;end; procedure zl(a:longint); var sel:longint; begin if a*2>size then exit;

sel:=a*2; if (sel+1<=size)and(dui[sel+1].s<dui[sel].s) then inc(sel); if dui[sel].s<dui[a].s then begin change(dui[sel],dui[a]); zl(sel); end; end; procedure zl1(a:longint); var sel:longint; begin if a=1 then exit; sel:=a div 2; if dui[sel].s>dui[a].s then begin change(dui[sel],dui[a]); zl1(sel); end; end; function getnum:longint; var p:longint; begin p:=dui[1].v; while (used[p]<>0)and(size>0) do begin change(dui[1],dui[size]); dec(size); zl(1); p:=dui[1].v; end; if size=0 then exit(0); change(dui[1],dui[size]); dec(size); zl(1); exit(p); end; procedure update(a:longint); var t:longint; begin t:=head[a]; while t<>0 do begin

if (used[da[t].v]=0) then if (dis[da[t].v]=-1)or(dis[da[t].v]>dis[a]+da[t].s) then begin dis[da[t].v]:=dis[a]+da[t].s; inc(size); dui[size].v:=da[t].v; dui[size].s:=dis[da[t].v]; zl1(size); end; t:=da[t].q; end; end; begin read(n,m); p:=0; for i:=1 to m do begin read(a,b,c); inc(p); da[p].v:=b; da[p].s:=c; da[p].q:=head[a]; head[a]:=p; end; fillchar(dis,sizeof(dis),255); fillchar(used,sizeof(used),0); dis[1]:=0; size:=1; dui[1].v:=1; dui[1].s:=0; for i:=1 to n-1 do begin sel:=getnum; if (sel=0)or(sel=n) then break; used[sel]:=1; update(sel); end; writeln(dis[n]); end. ②floyed for k:=1 to n do for i:=1 to n do for j:=1 to n do

if (i<>j) and (i<>k) and (j<>k) and (g[i,k]+g[k,j]<g[i,j]) then g[i,j]:=g[i,k]+g[k,j]; //floyed 用来求任意两点间的最短距离, 程序易打, 但效率极低 (O (n^3) ) ! ③SPFA spfa 的实质是模拟宽搜,其前身是 bellman-ford,中国的一位牛人(忘记名 字了) 改进了 bellman-ford (鼓掌! ) , 就我个人而言, 我从未打过 bellman-ford, 因为它的效率太低了,不过 bellman-ford 程序体简单,易打! const maxp=10000; {最大结点数} var {变量定义} p,c,s,t:longint; {p,结点数;c,边数;s:起点;t:终点} a,b:array[1..maxp,0..maxp] of longint; {a[x,y]存 x,y 之间边的 权;b[x,c]存与 x 相连的第 c 个边的另一个结点 y} d:array[1..2*maxp] of integer; {队列} v:array[1..maxp] of boolean; {是否入队的标记} dist:array[1..maxp] of longint; {到起点的最短路} head,tail:longint; {队首/队尾指针} procedure init; var i,x,y,z:longint; begin read(p,c); for i := 1 to c do begin readln(x,y,z); {x,y:一条边的两个结点;z:这条边的权值} inc(b[x,0]); b[x,b[x,0]] := y; a[x,y] := z; {b[x,0]:以 x 为一个结点 的边的条数} inc(b[y,0]); b[y,b[y,0]] := x; a[y,x] := z;{若为有向图,此句删去.(不 删去无法处理负边)} end; readln(s,t); {读入起点与终点} end; procedure spfa(s:longint); {SPFA} var i,j,now,sum:longint; begin fillchar(v,sizeof(v),false); for j := 1 to p do dist[j]:=maxlongint; dist[s]:=0; v[s]:=true;now:=s;{队列的初始状态,s 为起点} head:=1;tail:= 1; d[head]:=s; while head<=tail do {队列不空} begin now:=d[head mod maxp]; {取队首元素} for i:=1 to b[now,0] do if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then

begin dist[b[now,i]]:= dist[now]+a[now,b[now,i]]; {修改最短路} if not v[b[now,i]] then {扩展结点入队} begin tail:=tail+1; d[tail mod maxp] := b[now,i]; v[b[now,i]] := true; end; end; v[now] := false; {释放结点} head:=head+1;{出队} end; end; procedure print; begin writeln(dist[t]); end; begin init; spfa(s); print; end. ④bellman-ford

虽然我为用过 bellman-ford,但还是给个程序吧! ⑤标号法求解单源点最短路径 var a:array[1..maxn,1..maxn] of integer; b:array[1..maxn] of integer; {b[i]指顶点 i 到源点的最短路径} mark:array[1..maxn] of boolean; procedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark[1]:=true; b[1]:=0;{1 为源点} repeat best:=0; for i:=1 to n do If mark[i] then {对每一个已计算出最短路径的点} for j:=1 to n do if (not mark[j]) and (a[i,j] >0) then if (best=0) or (b[i]+a[i,j]< best) then begin best:=b[i]+a[i,j]; best_j:=j; end; if best >0 then begin b[best_j]:=best;mark[best_j]:=true;

end; until best=0; end;{bhf} 12.背包(动规) ①01 背包 ⑤标号法求解单源点最短路径 var a:array[1..maxn,1..maxn] of integer; b:array[1..maxn] of integer; {b[i]指顶点 i 到源点的最短路径} mark:array[1..maxn] of boolean; procedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark[1]:=true; b[1]:=0;{1 为源点} repeat best:=0; for i:=1 to n do If mark[i] then {对每一个已计算出最短路径的点} for j:=1 to n do if (not mark[j]) and (a[i,j] >0) then if (best=0) or (b[i]+a[i,j]< best) then begin best:=b[i]+a[i,j]; best_j:=j; end; if best >0 then begin b[best_j]:=best;mark[best_j]:=true; end; until best=0; end;{bhf} 12.背包(动规) ①01 背包 二维:(之所以把二维的放在前边是因为二维的好填表,做动规题最好的方法 就是填表了) var t,m,i,j,k:longint; a:array[1..1000,1..2]of longint; b:array[0..100,0..1000]of longint;function max(x,y:longint):longint; begin if x>y then max:=x else max:=y; end;begin readln(t,m); for i:=1 to m do readln(a[i,1],a[i,2]); k:=t; for i:=1 to m do for j:=1 to t do begin if j<a[i,1] then b[i,j]:=b[i-1,j] else b[i,j]:=max(b[i-1,j],b[i-1,j-a[i,1]]+a[i,2]); end; writeln(b[m,t]);end. 一维的省空间,优化了一下! 一维: var t,m,i,j,k,x,y:longint; b:array[0..1000]of longint;

function max(p,q:longint):longint; begin if p>q then max:=p else max:=q; end; begin readln(t,m); for i:=1 to m do begin readln(x,y); for j:=t downto x do begin b[j]:=max(b[j],b[j-x]+y); end; end; writeln(b[t]); end. 采药是经典的 01 背包,可以试试! ②多维背包 begin read(n,m); p:=0; for I:= 1 to n do begin read(a,b,c); t:=0;x:=1; while t+x<=a do begin inc(p); dd[p].w:=x*b; dd[p].v:=x*c; t:=t+x; x:=x*2; end; if t<a then begin if (a-t)*b<=m then begin inc(p); dd[p].w:=(a-t)*b; dd[p].v:=(a-t)*c; end; end; end; q:=0;

for i:=1 to p do begin for j:=0 to m do begin f[q,j]:=f[q xor 1,j]; if (j-dd[i].w>=0)and(f[q xor 1,j-dd[i].w]+dd[i].v>f[q,j])then f[q,j]:=f[q xor 1,j-dd[i].w]+dd[i].v; end; q:=q xor 1; end; writeln(f[q xor 1,m]:0:1); end. ③另外,还有无限背包,完全背包...... ④建议看看背包九讲 13.强联通分量 procedure find1(a:longint); var t:longint; begin used[a]:=true; t:=hout[a]; while t<>0 do begin if not used[da[t].z] then find1(da[t].z); t:=da[t].f; end; inc(p); way[p]:=a; end; procedure find2(a:longint); var t:longint; begin used[a]:=true; t:=hin[a]; while t<>0 do begin if not used[da[t].z] then find2(da[t].z); t:=da[t].f; end; end; begin

assign(f1,'ltfl.in'); assign(f2,'ltfl.out'); reset(f1); rewrite(f2); readln(f1,n,m); for i:= 1 to m do begin readln(f1,a,b); inc(p); da[p].z:=b; da[p].f:=hout[a]; hout[a]:=p; inc(p); da[p].z:=a; da[p].f:=hin[b]; hin[b]:=p; end; p:=0; for I:= 1 to n do if not used[i] then find1(i); for I:= 1 to n do used[i]:=false; for I:=p downto 1 do if not used[way[i]] then begin inc(tot); find2(way[i]); end; writeln(f2,tot); close(f2); end. 14.线段树 传说中最长的程序,感兴趣的试试吧! procedure make(v,a,b:longint); var mid:longint; begin if a=b then begin da[v].a:=a; da[v].b:=b; da[v].z:=-maxlongint; exit; end;

da[v].a:=a; da[v].b:=b; da[v].l:=v*2; da[v].r:=v*2+1; da[v].z:=-maxlongint; mid:=(a+b) div 2; make(v*2,a,mid); make(v*2+1,mid+1,b); end; function insert(v,a,b:longint):longint; var t1,t2,t:longint; begin if (da[v].b<a)or(da[v].a>a) then exit(da[v].z); if da[v].a=da[v].b then begin if da[v].a=a then da[v].z:=b; exit(da[v].z); end; t:=max(insert(da[v].l,a,b),insert(da[v].r,a,b)); da[v].z:=t; exit(t); end; function find(v,a,b:longint):longint; begin if (da[v].a>b)or(da[v].b<a) then exit(-maxlongint); if (da[v].a>=a)and(da[v].b<=b) then exit(da[v].z); exit(max(find(da[v].l,a,b),find(da[v].r,a,b))); end; begin f1:=input;f2:=output; readln(f1,n,m); da[0].z:=-maxlongint; make(1,1,n); for I:= 1 to m do begin readln(f1,a,x,y); if a=0 then insert(1,x,y) else begin ans:=find(1,x,y);

if ans=-maxlongint then writeln(f2,'None') else writeln(f2,ans); end; end; end. 啊,终于完了!当然,这仅仅是整理,要想把所有内容彻底的掌握还得 任重而道远啊!


相关文章:
noip标程(精华)
noip标程(精华)_学科竞赛_高中教育_教育专区。各类标程汇总标程复习 1.排序(从小到大排序) ①选择排序(效率不高,3000 左右就挂了) for i:=1 to n-1 do...
NOIP NOI知识点与部分标程
NOIP NOI知识点与部分标程_IT/计算机_专业资料。NOIP NOI知识点与部分标程目录...noip标程(精华) 25页 2下载券 NOIP标程算法库 12页 1下载券 NOIP2009提高组...
NOIP标程算法库
NOIP标程算法库_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 NOIP标程算法库_IT/计算机_专业资料。今日推荐 78份文档 ...
NOIP2005提高组解题报告带标程(天津南开中学 薛原)
​解​题​报​告​带​标​​(​天​津​南​开​...NOIP2005 提高组解题报告 天津南开中学 薛原 谁拿了最多奖学金(scholar) 题目...
NOIP2009提高组-标程
noip2009官方公布的标程,保证正确,供大家学习之用。noip2009官方公布的标程,保证正确,供大家学习之用。隐藏>> 1,潜伏者 program spy; var v: array['A'..'...
排列生成
这一个是前年 NOIP 初赛中《火星人》标程的算法,其中 dat 初始存一个排列,算法执行 后 dat 中将给出按字典序的下一个排列 (当然如果 dat 一开始就是最后一...
高斯消去法
喜欢此文档的还喜欢 NOIP NOI知识点与部分标程 38页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...
2009NOIP复赛满分-标准程序
NOIP2009提高组-标程 8页 免费 NOIP2009提高组解题报告 16页 免费 NOIP2009普及...NOIP2009提高组复赛题解 12页 1财富值如要投诉违规内容,请到百度文库投诉中心;...
NOIP2015普及组复赛试题解题报告word版第一二题满分程序
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 NOIP2015 普及组复赛试题解题报告 word 版 第一二题满分程序 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组一...
NOIP模拟试题2解题报告
因为我们水平有限,而一些题目是原创的,所以也许“标程”并不是最优的算法,也许...也预祝大家在四天 后的 NOIP2008 中 RP++,多多一等! 分享到: X 分享...
更多相关标签:
noip2016魔法阵标程 | noip2014解方程 | noip解方程 | 同余方程 noip | noip2016选手程序 | noip2012同余方程 | noip选手程序 | noip2016复赛选手程序 |