信息学竞赛NOIP复习资料

第一章PASCAL函数和技巧一、常用函数与过程：*abs(x):y取x的绝对值，x与y可为整型或实型。*append(f:text)用赋给f的文件名打开存在的外部文件。如果不存在给定的文件，产生错误。如果f已经存在，就先关闭再重新打开它。当前文件指针指向文件尾。*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):substr从字符串str中取从第n1个字符开始长度为n2个字符的子串substr.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对打开用来输入的文件没有作用。*SetTextBuf(Varf：Text；VarBuf[Size：word])f是文本文件变量，Buf是任何变量，Size是可选的Word表达式。每个文本文件变量缺省时有一个128字节的内部缓冲区用于输入输出操作。该缓冲区对大多数程序来说是足够了。然而对于I／O繁多的子程序如复制或转换文件，设置大的缓冲区较有利。因为这样减少了磁盘读写头的移动和系统负荷。本过程使文本文件变量、f使用指定的缓冲区BMf，而不是内部缓冲区。Size指定缓冲区的字节数，如果省略Size，则设成SizeOf(Buf)。也就是说，缺省时，Buf占用的整个内存区域用作缓冲区。直到f赋给下一个文件新的缓冲区之前一直有效。SetTextBuf不能用于一个打开的文件上，即使可以在Reset，Rewr加和Append后立即调用也不行；进行’了I／O操作后立即对打开文件上调用SetTextBuf将会因为更改缓冲区而丢失数据。Buf通常为一个array[1..4096]ofbyte;二、小技巧1.ord('0')=48;ord('A'):=65;ord('a')=97;chr(32)=’‘;chr(33)=’!’;2.求x^y:int(exp(y*ln(x)))3.求x的n次方根：exp(1/n*ln(x))4.标识符不能以数字开头，其中不能有空格，点等符号。5.说明部分顺序：Lable-Const-type-Var-Procedure(Function)6.通常编译器只能识别标识符的前8个字符。7.规定false=0,true=1;8.除实型外其他均为左留空，右看齐，实型向小数点看齐。9．实型默认场宽：17位符号位+11位数字与一位小数点+’E+00’第二章重要定理和公式一、常见递推关系1.Fibonacci数列A(1)=1;A(2)=1;A(n)=A(n-1)+A(n-2);2.Catalan数：考虑具有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)3.第二类Stirling数：s(n,k)表示含n个元素的集合划分为k个集合的情况数A.分类：集合{An}存在，则有s(n-1,k-1);不存在则An和放入k个集合中的任意一个，共k*s(n-1,k)种。0(k=0ornk)s(n,k)={s(n-1,k-1)+k*s(n-1,k)(nk=1)*:求一个集合总的划分数即为sigema(k=1..n)s(n,k).4．数字划分模型*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)5．错位排列d[1]=0;d[2]=1;d[n]=(n-1)*(d[n-1]+d[n-2])6.二、图论与计算几何1．度边定理：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．长度为n的0-1串中最多含k个1的例长度为N(N=31)的01串中1的个数小于等于L的串组成的集合中找出按大小排序后的第I个01串。2给定序列入栈出栈后可形成的情况总数为C(n,2n)–C(n-1,2n)+1.例fjoi2000在一个列车调度站中，2条轨道连接到2条侧轨处，形成2个铁路转轨站，如下图所示。其中左边轨道为车皮入口，右边轨道为出口。编号为1，2，……，n的N个车皮从入口依次进入转轨站，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序a1,a2,……,an。给定正整数N（1=n=300），编程计算右边轨道最多可以得到多少个不同的车皮编序方案。例如当n=3时，最多得到6组不同的编序方案。四、数论公式1．模取幂a^bmodn=(..(amodb)*a)modb)*a..)modb;2．n的约数的个数若n满足n=a1^n1*a2^n2*a3^n3*...*am^nm,则n约数的个数为(n1+1)(n2+1)(n3+1)...(nm+1)3．五、代数1带权中位数我国蒙古大草原上有N（N是不大于100的自然数）个牧民定居点P1（X1，Y1）、P2（X2，Y2）、…Pn（Xn，Yn），相应地有关权重为Wi，现在要求你在大草原上找一点P（Xp，Yp），使P点到任一点Pi的距离Di与Wi之积之和为最小。即求D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn有最小值结论：对x与y两个方向分别求解带权中位数，转化为一维。设最佳点p为点k，则点k满足：令W为点k到其余各点的带权距离之和，则sigema(i=1tok-1)Wi*Di=W/2sigema(i=k+1ton)Wi*Di=W/2同时满足上述两式的点k即为带权中位数。第三章基本算法模块一、数论算法1．求两数的最大公约数functiongcd(a,b:integer):integer;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;2．求两数的最小公倍数functionlcm(a,b:integer):integer;beginifabthenswap(a,b);lcm:=a;whilelcmmodb0doinc(lcm,a);end;3．素数的求法A.小范围内判断一个数是否为质数：functionprime(n:integer):Boolean;varI:integer;beginforI:=2totrunc(sqrt(n))doifnmodI=0thenbeginprime:=false;exit;end;prime:=true;end;B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：proceduregetprime;vari,j:longint;p:array[1..50000]ofboolean;beginfillchar(p,sizeof(p),true);p[1]:=false;i:=2;whilei50000dobeginifp[i]thenbeginj:=i*2;whilej50000dobeginp[j]:=false;inc(j,i);end;end;inc(i);end;l:=0;fori:=1to50000doifp[i]thenbegininc(l);pr[l]:=i;end;end;{getprime}functionprime(x:longint):integer;vari:integer;beginprime:=false;fori:=1toldoifpr[i]=xthenbreakelseifxmodpr[i]=0thenexit;prime:=true;end;{prime}二、图论算法1．最小生成树A.Prim算法：procedureprim(v0:integer);varlowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcost[i]:=cost[v0,i];closest[i]:=v0;end;fori:=1ton-1dobegin{寻找离生成树最近的未加入顶点k}min:=maxlongint;forj:=1tondoif(lowcost[j]min)and(lowcost[j]0)thenbeginmin:=lowcost[j];k:=j;end;lowcost[k]:=0;{将顶点k加入生成树}{生成树中增加一条新的边k到closest[k]}{修正各点的lowcost和closest值}forj:=1tondoifcost[k,j]lwocost[j]thenbeginlowcost[j]:=cost[k,j];closest[j]:=k;end;end;end;{prim}B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。functionfind(v:integer):integer;{返回顶点v所在的集合}vari:integer;begini:=1;while(i=n)and(notvinvset[i])doinc(i);ifi=nthenfind:=ielsefind:=0;end;procedurekruskal;vartot,i,j:integer;beginfori:=1tondovset[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条边的长度}whilep0dobegini:=find(e[q].v1);j:=find(e[q].v2);ifijth