好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

pascal省选模板.doc

39页
  • 卖家[上传人]:夏**
  • 文档编号:456958849
  • 上传时间:2022-08-09
  • 文档格式:DOC
  • 文档大小:220.50KB
  • / 39 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 算法线段树 1平衡二叉树 3匈牙利算法 8Km算法 9Sap算法 10Rmq问题的St算法 12树状数组 13最小费用最大流 15Tarjan算法 17根堆 21并查集 22Prim算法 23计算几何 26A*算法 31矩阵乘法 34快速幂 38线段树{线段树示范程序}Program IntervalTree; Const Inf='Input.txt'; Ouf='Output.txt'; Maxn=10000; Type TreeNode=Record //a,b:区间左右边界,left,right:左右儿子,cover:是否被覆盖 a,b,Left,Right,Cover:Longint; End; Var Tree:array [1..Maxn] of TreeNode; Number,Tot,c,d:Longint; //tot:线段树节点总数Procedure MakeTree(a,b:Longint); //建树Var Now:Longint; //now必须为局部变量!(dfs中枚举变量一样的道理)Begin Inc(Tot); //节点总数+1 Now:=Tot; Tree[Now].a:=a; Tree[Now].b:=b; Tree[Now].Cover:=0; //把[a,b]数据写入到tree[tot]; If a+1(Tree[Num].a+Tree[Num].b) div 2 then Insert(Tree[Num].Right); End; End; Procedure Delete(Num:Longint);//段树第num个节点区间中删除线段[c,d]Begin If (c<=Tree[Num].a) and (Tree[Num].b<=d) then //若当前区间被[c,d]覆盖,则cover-1 Dec(Tree[Num].Cover) Else begin //否则将区间[c,d]在左右子树中删除 If c<(Tree[Num].a+Tree[Num].b) div 2 then Delete(Tree[Num].Left); If d>(Tree[Num].a+Tree[Num].b) div 2 then Delete(Tree[Num].Right); End; End; Procedure Count(Num:longint); //计算整个线段树的测度(被覆盖区间的总长度)Begin If Tree[Num].Cover>0 then //若当前区间被完全覆盖,则累加到number全局变量中 Number:=Number+(Tree[Num].b-Tree[Num].a) Else begin //否则,若为部分覆盖,则累加左右子树的测度 If Tree[Num].Left>0 then Count(Tree[Num].Left); If Tree[Num].Right>0 then Count(Tree[Num].Right); End; End; Begin Assign(Input,Inf);Reset(Input); Assign(Output,ouf);Rewrite(Output); Readln(c,d); //读入总区间大小 MakeTree(c,d); //建树 While not eof do Begin Readln(c,d); //向线段树中插入线段[c,d] Insert(1); End; Count(1); //计算线段树的测度 Writeln(Number); Close(Output); Close(Input); End.平衡二叉树{treap示范代码:标准的代码缩进风格,优美的算法实现。

      经典标程,完全掌握后水平会提高很多不改变bst的性质(在bst所有子树中均满足:左子树的所有节点<=根<=右子树的所有节点)通过旋转操作,使根的hr最小(即所有的hr构成堆的关系)}{$inline on}var //l[i],r[i],v[i]:i号结点的左儿子、右儿子,关键值 //hr[i]:i号节点的优先值(treap所有子树中,根的hr必须是最小的) //s[i]:i号节点为根的子树节点总数 l,r,hr,s,v:array[0..2000000]of longint; n,root,m:longint; procedure init;//初始化begin readln(n); m:=0; //randomize; //考试要求程序每次运行结果必须一致,慎用确实要用:randomize 100; fillchar(s,sizeof(s),0); fillchar(l,sizeof(l),0); fillchar(r,sizeof(r),0); root:=0;end;//旋转是平衡二叉树的精髓,它不会改变bst的性质(左子树<=根<=右子树)//左旋使树的左子树深度+1,右子树深度-1//右旋使树的右子树深度+1,左子树深度-1procedure l_rotate(var x:longint);inline;//左旋以x为根的子树(注意var参数及意义)var y:longint;begin y:=r[x]; //保存x的右儿子到y中 r[x]:=l[y]; //将y的左儿子作为x的右儿子 l[y]:=x; //x作为y的左儿子 s[y]:=s[x]; //维护旋转后的子树大小 s[x]:=s[l[x]]+s[r[x]]+1; x:=y; //y为根end;procedure r_rotate(var x:longint);inline;//右旋以x为根的子树var y:longint;begin y:=l[x]; l[x]:=r[y]; r[y]:=x; s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1; x:=y;end;//插入(递归,if key<=root,则插入到左子树,否则到右子树,直到尽头再新建节点)procedure insert(var k,key:longint);inline;begin if k=0 then//已到尽头,新建节点并写入key及随机值hr begin inc(m); v[m]:=key; s[m]:=1; hr[m]:=random(maxlongint); k:=m;//修改k,使父节点指向当前节点(修改前从父节点指向0) exit; end; inc(s[k]); if key<=v[k] then//若key<=根则插入到左子树,否则到右子树 begin insert(l[k],key);//若l[k]=0,到下层则新建节点并修改l[k]=m if hr[l[k]]>hr[k] then //旋转 r_rotate(k); exit; end; if key>v[k] then begin insert(r[k],key); if hr[r[k]]>hr[k] then l_rotate(k); exit; end;end;(删除:在k号节点为根的子树中删除key基本方法:由于是静态结构,为了提高效率,并没真正删除若找到则删除,若没找到,则删除查找尽头的节点主程序中需判断返回值,若不等于key,重新插入key即可找到后的处理: 若为叶节点,直接删除,否则,将要删除的节点左子树的最右节点(思考:为什么?)代替它)function delete(var k:longint;key:longint):longint;inline;begin dec(s[k]);//维护节点总数 //如果找到,或已到尽头 if (key=v[k])or(l[k]=0)and(key<=v[k])or(r[k]=0)and(key>v[k]) then begin delete:=v[k];//返回要删除的节点(不一定=key) if (l[k]=0)or(r[k]=0) then //若左右子树只有一个,则让儿子代替根即可 begin k:=l[k]+r[k];//用儿子替换当前要删除的节点 exit; end; v[k]:=delete(l[k],key+1);//k左右子树都有,则用左子树的最右节点替换k exit; end; if key<=v[k] then//若k<=v[k],则在左子树中删,否则,在右子树中删 exit(delete(l[k],key)); if key>v[k] then exit(delete(r[k],key));end;function find(var k,key:longint):boolean;inline;//查找begin if k=0 then//递归边界 exit(false); if key>v[k] then find:=find(r[k],key) else find:=(v[k]=key)or find(l[k],key);end;//key的排名(key排在第几,按从小到大的顺序)function rank(var t,key:longi。

      点击阅读更多内容
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.