OI基本算法总结.doc

语言部分一、常用函数与过程:*abs(x):y取x的绝对值,x与y可为整型或实型。*frac(x):y取x的小数部分,x与y均为实型。*int(x):y取x的整数部分,x与y均为实型,常写成trunc(int(x)).*random(x):y在0-x之间的整数中随机找一个整数,x与y均为整型。*sin(x):y;cos(x):y;arctan(x):y;exp(x):y;ln(x):y均与数学运算一致,三角函数返回的均为弧度,转换成角度即乘以Pi除以180.*copy(str,n1,n2):,如果n1大于s的长度,则返回空字符串。如果指定的n2大于第n1个字符后剩下的字符数,则返回剩下的字符串。*pos(substr,str):num查找substr是否为str的子串,若是则返回substr在str中的起始位置,若否则返回0.*val(str,int,code)将字串str转为数值型数据存入int,如果字符串无效,其中非法字符的下标放在Code中;否则,code为零。*str(num,str)将num表达式转成字符串str。*delete(str,n1,n2)从原字符串str中删去一个从n1开始长度为n2的子串,如果Index比s长,不删除任何字符。如果指定的Count大于从第1ndex大到结尾的字符数,删除剩余部分。*Insert(Source:String;VarS:String;Index:Integer)Source是字符串表达式。S是任意长度的字符串变量。Index是整型表达式。过程Insert把字符串Source插入字符串S中第1ndex个字符开始的位置上。如果字符串比255个字符长,则将第255后面的字符截去。.*FileSize(varf:text):longint返回文件字节数。*Flush(f:text)如果正文文件由Rewr比和Append打开用来输出,则对F1ush的调用将腾空文件缓冲区,这保证写向文件的字符实际写到外部文件上。Flush对打开用来输入的文件没有作用。二、('0')=48;ord('A'):=65;ord('a')=97;chr(32)=’‘;chr(33)=’!’;^y:int(exp(y*ln(x))):exp(1/n*ln(x)),其中不能有空格,点等符号。:Lable->Const->type->Var->Procedure(Function)。=0,true=1;,右看齐,实型向小数点看齐。:17位符号位+11位数字与一位小数点+’E+00’数学部分一、(1)=1;A(2)=1;A(n)=A(n-1)+A(n-2);:考虑具有n个结点不同形态的二叉树的个数H(n)H(0)=1;H(n)=H(0)H(n-1)+H(1)H(n-2)+H(2)H(n-3)…+H(n-2)H(1)+H(n-1)H(0);->H(n)=(1/(n+1))*C(n,2n):s(n,k):集合{An}存在,则有s(n-1,k-1);不存在则An和放入k个集合中的任意一个,共k*s(n-1,k)种。0(k=0orn<k)s(n,k)={s(n-1,k-1)+k*s(n-1,k)(n>k>=1)*:求一个集合总的划分数即为sigema(k=1..n)s(n,k).*NOIP2001数的划分将整数n分成k份,且每份不能为空,任意两种分法不能相同(不考虑顺序)。d[0,0]:=1;forp:=1tondofori:=ptondoforj:=kdownto1doinc(d[i,j],d[i-p,j-1]);writeln(d[n,k]);*变形1:考虑顺序d[i,j]:=d[i-k,j-1](k=1..i)*变形2:若分解出来的每个数均有一个上限md[i,j]:=d[i-k,j-1](k=1..m)[1]=0;d[2]=1;d[n]=(n-1)*(d[n-1]+d[n-2])二、:sigemadi=2*E2..三角形面积|x1y11|s=|x2y21|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3|x3y31|*海伦公式:令p=(a+b+c)/2,则S=sqrt(p*(p-a)*(p-b)*(p-c));三、-1串中最多含