《OI基本算法总结》由会员分享，可在线阅读，更多相关《OI基本算法总结（19页珍藏版）》请在金锄头文库上搜索。
1、语言部分语言部分 一、常用函数与过程：一、常用函数与过程： * abs(x):yabs(x):y 取 x 的绝对值，x 与 y 可为整型或实型。 * frac(x):yfrac(x):y 取 x 的小数部分，x 与 y 均为实型。 * int(x):yint(x):y 取 x 的整数部分，x 与 y 均为实型，常写成 trunc(int(x). * random(x):yrandom(x):y 在 0-x 之间的整数中随机找一个整数，x 与 y 均为整型。 * sin(x):y;sin(x):y; cos(x):y;cos(x):y; arctan(x):y;arctan(x):y; exp(
2、x):y;exp(x):y; ln(x):yln(x):y 均与数学运算一致,三角函数返回的均为弧度,转换成角度即乘以 Pi 除以 180. * copy(str,n1,n2):substrcopy(str,n1,n2):substr 从字符串 str 中取从第 n1 个字符开始长度为 n2 个字符的子串 substr.n1 和 n2 是整型表达式，如果 n1 大于 s 的长度，则返回空字符串。如果指定的 n2 大于第 n1 个字符后剩下的字符数，则返回剩下的字符串。 * pos(substr,str):numpos(substr,str):num 查找 substr 是否为 str 的子串，
3、若是则返回 substr 在 str 中的起始位置，若否则返回 0. * val(str,int,code)val(str,int,code) 将字串 str 转为数值型数据存入 int, 如果字符串无效，其中非法字符的下标放在 Code 中；否则，code 为零。* str(num,str)str(num,str) 将 num 表达式转成字符串 str。 * delete(delete( str,n1,n2)str,n1,n2) 从原字符串 str 中删去一个从 n1 开始长度为 n2 的子串，如果 Index 比 s 长，不删除任何字符。如果指定的 Count 大于从第 1ndex 大到结
4、尾的字符数，删除剩余部分。 * Insert(SourceInsert(Source：StringString；VarVar S S：StringString；IndexIndex：Integer)Integer) Source 是字符串表达式。S 是任意长度的字符串变量。Index 是整型表达式。过程 Insert 把字符串 Source 插入字符串 S 中第 1ndex 个字符开始的位置上。如果字符串比 255 个字符长，则将第 255 后面的字符截去。* FileSize(varFileSize(var f:text):longintf:text):longint 返回文件字节数。 *
5、Flush(f:text)Flush(f:text) 如果正文文件由 Rewr 比和 Append 打开用来输出，则对 F1ush 的调用将腾空文件缓冲区，这保证写向文件的 字符实际写到外部文件上。Flush 对打开用来输入的文件没有作用。 二、小技巧 1.ord(0)=48; ord(A):=65; ord(a)=97; chr(32)= ; chr(33)=!; 2.求 xy: int(exp(y*ln(x) 3.求 x 的 n 次方根：exp(1/n*ln(x) 4.标识符不能以数字开头，其中不能有空格，点等符号。 5.说明部分顺序： Lable - Const - type - Var
6、 - Procedure (Function) 6.通常编译器只能识别标识符的前 8 个字符。 7.规定 false=0,true=1; 8.除实型外其他均为左留空，右看齐，实型向小数点看齐。 9实型默认场宽：17 位 符号位+11 位数字与一位小数点+E+00 数学部分数学部分一、常见递推关系 1.Fibonacci 数列 A(1)=1;A(1)=1; A(2)=1;A(2)=1; A(n)=A(n-1)A(n)=A(n-1) + + A(n-2);A(n-2); 2.Catalan 数： 考虑具有 n 个结点不同形态的二叉树的个数 H(n) H (0) = 1; H(n) = H(0) H
7、(n-1) + H(1) H(n-2) + H(2) H(n-3) + H(n-2) H(1) + H(n-1) H(0) ; - H(n)H(n) = = (1/(1/ (n+1)(n+1) * * C C (n,(n, 2n)2n) 3. 第二类 Stirling 数： s(n,k)表示含 n 个元素的集合划分为 k 个集合的情况数 A.分类：集合An存在，则有 s(n-1,k-1); 不存在则 An 和放入 k 个集合中的任意一个，共 k*s(n-1,k)种。 0 0 (k=0(k=0 oror nk=1)(nk=1) *:求一个集合总的划分数即为 sigema(k=1.n) s(n,k
8、) . 4数字划分模型 *NOIP2001 数的划分 将整数 n 分成 k 份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。 d0,0:=1; for p:=1 to n do for i:=p to n do for j:=k downto 1 do inc(di,j,di-p,j-1); writeln(dn,k); *变形 1：考虑顺序 d i, j : = d i-k, j-1 (k=1.i) *变形 2：若分解出来的每个数均有一个上限 m d i, j : = d i-k, j-1 (k=1.m) 5错位排列 d1 = 0; d2 = 1; dn = (n-1) * (dn-
9、1 + dn-2) 二、图论与计算几何 1度边定理： sigema di = 2*E 2.三角形面积 |x1 y1 1| s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3 |x3 y3 1| *海伦公式： 令 p=(a+b+c)/2, 则 S=sqrt(p*(p-a)*(p-b)*(p-c); 三、组合公式 1长度为 n 的 0-1 串中最多含 k 个 1 的 例 长度为 N (N0 do inc(lcm,a); end; 3素数的求法 A.小范围内判断一个数是否为质数： function prime (n: integer): Boolean; var I:
10、 integer; begin for I:=2 to trunc(sqrt(n) do if n mod I=0 then begin prime:=false; exit; end; prime:=true; end; B.判断 longint 范围内的数是否为素数（包含求 50000 以内的素数表）： procedure getprime; var i,j:longint; p:array1.50000 of boolean; begin fillchar(p,sizeof(p),true); p1:=false; i:=2; while i=x then break else if x
11、 mod pri=0 then exit; prime:=true; end;prime 二、图论算法 1最小生成树 A.PrimA.Prim 算法： procedure prim(v0:integer); var lowcost,closest:array1.maxn of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcosti:=costv0,i; closesti:=v0; end; for i:=1 to n-1 do begin 寻找离生成树最近的未加入顶点 k min:=maxlongint; for j:
12、=1 to n do if (lowcostj0) then begin min:=lowcostj; k:=j; end; lowcostk:=0; 将顶点 k 加入生成树 生成树中增加一条新的边 k 到 closestk 修正各点的 lowcost 和 closest 值 for j:=1 to n do if costk,j0 do begin i:=find(eq.v1);j:=find(eq.v2); if i0) then if (best=0) or (bi+ai,j0 then begin bbest_j:=best；markbest_j:=true; end; until b
13、est=0; end;bhf B.FloyedB.Floyed 算法求解所有顶点对之间的最短路径： procedure floyed; begin for I:=1 to n do for j:=1 to n do if aI,j0 then pI,j:=I else pI,j:=0; pI,j表示 I 到 j 的最短路径上 j 的前驱结点 for k:=1 to n do 枚举中间结点 for i:=1 to n do for j:=1 to n do if ai,k+aj,k0 then prei:=v0 else prei:=0; end; markv0:=true; repeat 每循
14、环一次加入一个离 1 集合最近的结点并调整其他结点的参数 min:=maxint; u:=0; u 记录离 1 集合最近的结点 for i:=1 to n do if (not marki) and (di0 then begin marku:=true; for i:=1 to n do if (not marki) and (au,i+du表示，则 EeI = Vej; d. 边活动最晚开始时间 ElI, 若边 I 由表示，则 ElI = Vlk wj,k; 若 Eej = Elj ，则活动 j 为关键活动，由关键活动组成的路径为关键路径。 求解方法： a. 从源点起 topsort,判断
15、是否有回路并计算 Ve; b. 从汇点起 topsort,求 Vl; c. 算 Ee 和 El; 6拓扑排序 找入度为 0 的点，删去与其相连的所有边，不断重复这一过程。 例寻找一数列，其中任意连续 p 项之和为正，任意 q 项之和为负，若不存在则输出 NO. 7.回路问题 EulerEuler 回路(DFS)(DFS) 定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点） HamiltonHamilton 回路 定义：经过图的每个顶点仅一次的回路。 一笔画 充要条件：图连通且奇点个数为 0 个或 2 个。 9判断图中是否有负权回路 Bellman-ford 算法 xI,yI,tI分别表示第 I 条边的起点，终点和权。共 n 个结点和 m 条边。 procedure bellman-ford begin for I:=0 to n-1 do dI:=+infinitive; d0:=0; for I:=1 to
