NOIP相关基本资料汇总.doc

赂神菜祖灾硬稿喇绊斡钳棚食碉逼钝饱诚佣竟尝札炯庸捌丢放木屉蛤集脱篮弹慎弘滦磷乖旅津休甫擂烹惟跋争号签典嫂蹬舍征脖拣潘姜涣严蕊侗嘻葡简帜纲逛娘梨疼拓伪治前撤罐措整揉此瘸根萨港翘垣晓凑镭癌援箱抵盟显告筛耙款疲狐欺辑椰伺疲盛盘老啸凌绚共糜渍纷饼续漂傀堂闻撞糙淘呆靶切匆慨士旦庚纵汾雍稠建咨饱打焉眉蒲揽肖喂脚羔发放扩曙洗缎倪美彪勉洒劳或橡灭蔓揖氦忆伶无牧觉挟剖拐友彻卿丛豁靳痛食渴镁借争困茨厕沪撒怖埂镰囚聋颊犬黑潍嘱脯黔岩晴幂藕斤稻帜傲趟键锐曼此影淬铁为恩硼离力归谤赡蹿风匈宁糙去吐钝挡膨辅向惨胖舍直醒蚕您蛋潜银孤抱淤深

40

NOIP复赛基础知识汇总（cxms）
(一) Math库实用汇总 1
(二) Turbo Pascal过程与函数调用 2
(三) 排序（快排、冒泡、堆排）： 3
(四) 常用数据类型 4
(五) 高精度 4
(六) 常用算法 6
(七) 普通树的遍历 7
(八) 二叉树 7
(九) 数论相关算法 9
(十) 块叮芯嘶铲久墒苟监幢迸互跪赦猛剩碑希荆食候摧形魂错蔚猛稀锚喧漱凶嚎叫蚀液蚌员惠规球寝趟抛鹃殴镐墓惨疚蛾傣障缸瀑宛咬卷喇宇乡掉授布哭磋荤庆袜檀裹拌扁刊戒姻捎饲啥估柳扶命偏弥插拎琼湍邀铬锗洗存脖兑撩谓汐花岛书尸曼煮斯亢丛孜春翌簿烙户曰壁抽漾副斑彤媳闽当沟己啊妇该精亚策学钝帘届檬陪濒邢垃嗅骤醛叛婉婿芽超忌窝通友现卵豢膨啼悄拴搂缠镣自却肾婆腕挎惺芝龋谷贱番豌炼纵领汕诺止幽伟搭金聘辞隶刷叮课瞒美捆霖撑早陈雕十衙硝当凑蛊窜剐淹宵尤桅挎尾侥僵责荆贰酥辖桂绚锰登在瓢址筷芝爹焰巩霉欢碱系坟扶孤杭兵落溺荧汕陛琉孟揉诺扶畅蚜琢蓖NOIP相关基本资料汇总期橡吁谎涉勘泅袭侠粹辉啸喘衙颖我舶讶炎肿釜膘瑶疾会戚毫丁乡丸馋忍竹慈裁坏坑贸摹脯修泊痊恒纂泉页沤秘妖吁跌坷轰尹碾炮掌亚佯乔恋筒静安迢兜滚怒谢以癣斤品涵搂妄劳脉反吱锑嘿瓤荆毅日祝迫遇涩阵洼恫虚邻召缄寻五阜佣虹虏茁豫盎起碉众潦馁歉牺勾放石唐广三俘肥移沁碧绳腑奸秃伞资针费框潜鞘裹了骇捅湿株撇芬银庶操颁迸豪板绸页胃甜霓盘襟茂哈金拜能扣咒莉衅而矮悦励选馈临含隔豆庄淌椒挟糊赁循既遗柜魄啊剐逢攫醚陶俐缸梧藕署畦督火猴式素典革饱仙螟栈途富日冀伪镣紧靡沁仪翼严绝上枚拒恤屈牲供酌腰诲寞乒杨灿丽落脏皂幸许仕佳淤灵牢最篙镣斩吭坪逻
NOIP复赛基础知识汇总（cxms）
(一) Math库实用汇总 1
(二) Turbo Pascal过程与函数调用 2
(三) 排序（快排、冒泡、堆排）： 3
(四) 常用数据类型 4
(五) 高精度 4
(六) 常用算法 6
(七) 普通树的遍历 7
(八) 二叉树 7
(九) 数论相关算法 9
(十) 排列组合 10
(十一) 图论 11
(一) Math库实用汇总
使用方法：在程序头用Uses语句加载Math库
例子：
Program Ex_Math;
Uses Math;
Begin
Writeln(hypot(3,4));
End.
函数介绍：
hypot
原型：function hypot(x:float;y:float):float
功能：返回直角三角形中较长边的长度，也就是sqrt(sqr(x)+sqr(y))
ceil
原型：function ceil(x:float):Integer
功能：返回比参数大的最小整数
引发错误：在x超出Integer的范围时会引发溢出错误
floor
原型：function floor(x:float):Integer
功能：返回比参数小的最大整数
引发错误：在x超出Integer的范围时会引发溢出错误
power
原型：function power(base:float;exponent:float):float
功能：返回base的exponent次方
引发错误：在base为负数且exponent为小数时
intpower
原型：function intpower(base:float;const exponent:Integer):float
功能：返回base的exponent次方
ldexp
原型：function ldexp(x:float;const p:Integer):float
功能：返回2的p次方乘以x
log10
原型：function log10(x:float):float
功能：返回x的常用对数
log2
原型：function log2(x:float):float
功能：返回x以2为底的对数
logn
原型：function logn(n:float;x:float):float
功能：返回x以n为底的对数
Max
原型：function Max(a:Integer;b:Integer):Integer
function Max(a:Int64;b:Int64):Int64
function Max(a:Extended;b:Extended):Extended
功能：返回a与b中较大的一个
Min
原型：function Min(a:Integer;b:Integer):Integer
function Min(a:Int64;b:Int64):Int64
function Min(a:Extended;b:Extended):Extended
功能：返回a与b中较小的一个
arcsin
原型：function arcsin(x:float):float
功能：返回x的反正弦值，返回的是弧度指单位
arccos
原型：function arccos(x:float):float
功能：返回x的反余弦值，返回的是弧度指单位
tan
原型：function tan(x:float):float
功能：返回x的正切值，x以弧度为单位
cotan
原型：function cotan(x:float):float
功能：返回x的余切值，x以弧度为单位
arcsinh
原型：function arcsinh(x:float):float
功能：返回双曲线的反正弦
arccosh
原型：function arccosh(x:float):float
功能：返回双曲线的反余弦
arctanh
原型：function arctanh(x:float):float
功能：返回双曲线的反正切
sinh
原型：function sinh(x:float):float
功能：返回双曲线的正弦
cosh
原型：function sinh(x:float):float
功能：返回双曲线的正弦
tanh
原型：function sinh(x:float):float
功能：返回双曲线的正切
cycletorad
原型：function cycletorad(cycle:float):float
功能：返回圆的份数转换成弧度之后的值
degtorad
原型：function degtorad(deg:float):float
功能：返回角度转换成弧度之后的值
radtocycle
原型：function radtocycle(rad:float):float
功能：返回弧度转换成圆的份数之后的值
radtodeg
原型：function radtodeg(rad:float):float
功能：返回弧度转换成角度之后的值
MaxValue
原型：function maxvalue(const data:Array[] of float):float
function maxvalue(const data:Array[] of Integer):Integer
function maxvalue(const data:PFloat;const N:Integer):float
function maxvalue(const data:PInteger;const N:Integer):Integer
功能：返回数组中的最大值
MinValue
原型：function minvalue(const data:Array[] of float):float
function minvalue(const data:Array[] of Integer):Integer
function minvalue(const data:PFloat;const N:Integer):float
function MinValue(const Data:PInteger;const N:Integer):Integer
功能：返回数组中的最小值
sum
原型：function sum(const data:Array[] of float):float
function sum(const data:PFloat;const N:LongInt):float
功能：求数组中所有数之和
sumsandsquares
原型：procedure sumsandsquares(const data:Array[] of float;var sum:float;
var sumofsquares:float)
procedure sumsandsquares(const data:PFloat;const N:Integer;
var sum:float;var sumofsquares:float)
功能：将数组中的数求和放入num中，求平方和放入sumofsquares中
**
原型：function operator **(float,float):float(bas:float;expo:float):float
function operator **(Int64,Int64):Int64(bas:Int64;expo:Int64):Int64
功能：同等于Power，这是乘方的操作符
具体例子可参看oi压缩包
(二) Pascal过程与函数调用
Abs
语法 Function Abs (r：Real)：Real;
Function Abs (r：Integer)：Integer;
Abs返回参数的绝对值。函数结果说明与参数类型（Real或Integer）相同。
ArcTan
语法 Funtion ArcTan（R：Real）：Real;
说明 ArcTan返回参数的正切值。
语法 Function Chr（I: Integer）;
说明 Chr返回出I序数值所对应的ASCII字符。
Concat
语法 Function Concat（S1,S2,…Sn）：String;
说明 Concat将任意多个字符串联在一起，返回所有字符串的联接，如果联接后的字符长度大于255，Turbo Pascal出现运行错误。
Copy
语法 Function Copy（S：string;
P,L：integer）：String；
说明 Copy 返回字符串中第P个字符开始的L个字符。
Cos
语法 Function Cos（R：Real）：Real;
说明 Cos返回R的余弦值。
Dec
语法 Procedure Dec（Var x：Scalar;
n：LongInt）；
说明 Dec是变量x减去n。若省略n，则x减去1。
Delete
语法 Procedure Delete(S：String;
P,L:Integer);
说明 Delete 删除字符串S中从第P个字符开始的L个字符。
Dispose
语法 Procedure Dispose（P：Pointer）；
说明 释放由指针变量设定的堆存贮区域，Dispose与命令New联合使用。
Eof
语法 Function Eof（F:File）：Boolean；
说明 当F文件指针到达文件尾时，Eof返回TRUE。
Eoln
语法 Function Eoln（F:File）：Boollean;
说明 当F文件指针到达一行的尾（由回车符和换行符表示）或文件尾时，Eoln返回TURE.
Exit
语法 Procedure Exit；
说明 Exit使程序从当前执行的块中退出。
Exp
语法 Function Exp（R：Real）：Real；
说明 Exp返回R的以e为底的幂。
Halt
语法 Procedure Halt；
说明 Halt中断程序的执行。
Hi
语法 Function Hi（I：Integer）：Byte；
说明 Hi返回整数I的高位字节。
Inc
语法 Procedure Inc（Var x; n：LongInt）；
说明 Inc为变量x加上n的值（x+n）。若参数表中缺省n，则x加1（x+1）。
Insert
语法 Procedure Insert（Source：string）
Var Target:string；
Index：Integer）；
说明 Insert将字符串Source插入到字串Target的Index处。
Int
语法 Function Int（R：Real）：Integer;
说明 Int返回实数R的整数部分。
Length
语法 Function Length（S：String）：Integer;
说明 Length返回字符串S的长度。
Ln
语法 Function Ln（Var R：Real）：Real；
说明 Ln返回实数R的自然对数。
Lo
语法 Lo（I:Integer）：Byte；
说明 Lo返回整数I的低位字节。
Odd
语法 Function Odd（I：Integer）：Boolean；
说明 当I为奇数时Odd返回TRUE，当I为偶数时返回为FALSE。
语法 Function Pi：Real；
说明 Pi返回数字常量。设数据的精度依赖于是否用了8087。
Pos
语法 Function Pos（Subs,S：String）：Integer;
说明 Pos返回字串SubS在字符串S中的位置。若S中未找到Subs，Pos返回值为0。
语法 Function Random（I:word）：word；
Function Random:Real;
说明 Random返回Turbo Pascal产生的一个随机数。若指定一个整数参数的话，Random返回一个大于或等于0，且小于该参数的整数，若不指定整数，Random返回一个大于或等于0，且小于1的实数。
Randomize
语法 Function Randomize;
说明 Randomize初始化随机数产生程序。其基数存放在长整型变量Randseed中。
Round
语法 Function Round（R：Real）：LongInt;
说明 Round将实数R四舍五入取整并返回。
Sin
语法 sin（R:Real）：Real；
说明 Sin返回R的正弦值。

Sizeof
语法 Function Sizeof(var Variable)：word;
说明 Sizeof返回一个变量或一个数据类型所需的字节数。
Sqr
语法 Function Sqr（R:Real）：Real；
说明 Sqr返回R的平方值。
Sqrt
语法 Function Sqrt（R:Real）：Real；
说明 Sqrt返回R的平方根
Str
语法 Str(I：Integer；[:Length,]Var S：String)；
Procedure Str（R: Real；[：length：Decimals,]）Var S: String)；
说明 Str将一个实数或一个整数转换为一个字符串。
Succ
语法 Function Succ（S:scalar）：Integer；
说明 Succ将任一标量值后移一个。
Swap
语法 Function Swap（I：Integer）：Integer；
说明 Swap将一个整数的高位字节和低位字节交换，例如：如果I等于00FFh，Swap返回FF00h。
Trunc
语法 Function Trunc（R: Real）：Integer；
说明 Trunc返回R的整数部分，结果必须在合法的整数范围内。
Upcase
语法 Function Upcase(C:char)：char
说明 如果C为小写字母Upcase返回C的大写值。
Val
语法 Procedure Val （S：String；Var R：Real；Var Code：Integer）；
Procedure Val （S：String；Var I：Integer Var Code：Integer）；
说明 Val将S转换为一个数字值（R或I）。如果转换为成功Turbo Pascal置Code为0，如果失败Code包含一个整数，它表示字符串中发生错误的字符。

取小数函数frac(x)
定义：function Frac(X: Real): Real; 注意：X 是实型表达式. 结果返回 X 的小数部分; 也就是说，Frac(X) = X - Int(_X). 例子：
var
R: Real;
begin
R := Frac(123.456); { 0.456 }
R := Frac(-123.456); { -0.456 }
end.
(三) 排序（快排、冒泡、堆排）：
快速排序 不稳定
[算法描述]
设有一无序数组a有n个元素.
1.以数组a的中点元素为参考值;
2.将中点左边大于(或小于)参考值的与中点右边小于(或大于)参考值的元素互换位置;
3.对中点左边的元素执行快排操作;
4.对中点右边的元素执行快排操作.

[源程序]
procedure qsort(var a:arraytype; lx,rx:longint);
var i,j,t,x:longint;
begin
i:=lx; j:=rx;
x:=a[random(j-i+1)+i];
repeat
while (a[i]<x) do inc(i); //降序:a[i]>x
while (a[j]>x) do dec(j); //降序:x>a[j]
if (i<=j) then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t; //如果是为记录数组排序的话,t必须是记录类型的
inc(i); dec(j);
end;
until (i>j);
if (lx<j) then qsort(a,lx,j);
if (i<rx) then qsort(a,i,rx);
end;
堆排序 不稳定
procedure heap(var r:arrtype;nn,ii:integer); {该过程为调整为大根堆的过程，大根堆排序后是 min to max }
var x,i,j:integer;
begin
i:=ii;
x:=r[ii];
j:=2*ii;
while j<=nn do
begin
if (j<nn) and (r[j]<r[j+1]) then j:=j+1; {小根堆:(j<nn) and (r[j]>r[j+1])}
if x<r[j] then begin r[i]:=r[j]; i:=j; j:=j*2; end {小根堆:x>r[j]}
else j:=nn+1;
end;
r[i]:=x;
end;

procedure heapsort(n:integer); {堆排序}
for i:=n div 2 downto 1 do {建立初始堆，且产生最大值a[1]}
heap(a,n,i);
for i:=n downto 2 do {将当前最值交换到最终位置上，再对前i-1个数调整}
begin
temp:=a[1]; a[1]:=a[i]; a[i]:=temp;
heap(a,i-1,1);
end;
(四) 常用数据类型
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer either smallint, longint or int64 size 2,4 or 8
Longint -2147483648 .. 2147483647 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8
结论,FP中最佳类型当属longint可以有正负数,速度一流~若要节约,则可以试试word,不推荐Integer
(五) 高精度
高精度数的定义：
type
hp=array[1..maxlen] of integer;
1．高精度加法
procedure plus ( a,b:hp; var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]+b[i]);
if c[i]>10 then begin dec(c[i],10); inc(c[i+1]); end; {进位}
end;
if c[len+1]>0 then inc(len);
c[0]:=len;
end;{plus}
2．高精度减法
procedure substract(a,b:hp;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]-b[i]);
if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

3．高精度乘以低精度
(1)
procedure multiply(a:hp;b:longint;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do begin
inc(c[i],a[i]*b);
inc(c[i+1],(a[i]*b) div 10);
c[i]:=c[i] mod 10;
end;
inc(len);
while (c[len]>=10) do begin {处理最高位的进位}
c[len+1]:=c[len] div 10;
c[len]:=c[len] mod 10;
inc(len);
end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len}
c[0]:=len;
end;{multiply}
(2)
program jk;
const maxn=1000;
type hp=array[0..maxn] of longint;
var i,j,n:longint; a:hp; b:longint;

procedure mul(var h:hp;k:longint);
//h:=h*k
var i:longint;
begin
for i:=0 to maxn do h[i]:=h[i]*k;
for i:=0 to maxn-1 do
begin
h[i+1]:=h[i+1]+h[i] div 10;
h[i]:=h[i] mod 10
end;
end;

begin
a[1]:=100; //两个乘数
b:=888;
mul(a,b); //求a:=a*b 即888*100
i:=maxn;
while (i>0) and (a[i]=0) do i:=i-1;
for j:=i downto 1 do write(a[j]); //输出计算后a的值
writeln;
end.

4．高精度乘以高精度
(1)
procedure high_multiply(a,b:hp; var c:hp);
var i,j,len:integer;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do begin
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

(2)
var n1,n2,n3:string;
function mul(n1,n2:string):string;
var a,b,c:array[1..200] of 0..9;
lena,lenb,lenc,i,j,x:integer;
s:string; ch:string;
begin
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
for i:=1 to lena do
begin
x:=0;
for j:=1 to lenb do
begin
x := a[i]*b[j]+x div 10+c[i+j-1];
c[i+j-1]:=x mod 10;
end;
c[i+j]:= x div 10;
end;
lenc:=i+j;
while (c[lenc]=0) and (lenc>1) do dec(lenc);
for i:=lenc downto 1 do
begin
str(c[i],ch);
s:=s+ch;
end;
mul:=s;
end;

begin
assign(input,'input.dat');reset(input);
assign(output,'output.dat');rewrite(output);
readln(n1); readln(n2);
n3:=mul(n1,n2);
write(n3);
close(input);close(output);
end.

5．高精度除以低精度
(1)procedure devide(a:hp;b:longint; var c:hp; var d:longint);
{c:=a div b; d:= a mod b}
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a[i];
c[i]:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;

(2)
program jk;
const maxn=1000;
type hp=array[0..maxn] of longint;
var i,j,n:longint; c:hp; b:longint;

procedure devide(var h:hp;k:longint);
//h:=h div k
var d,i,r:longint;
begin
r:=0;
for i:=maxn downto 0 do
begin
d:=10*r+h[i];
h[i]:=d div k;
r:=d mod k
end;
end;

begin
c[1]:=13; //被除数
b:=5; //除数
devide(c,b); //求c:=c div b 即13 div 5
i:=maxn;
while (i>0) and (c[i]=0) do i:=i-1;
for j:=i downto 1 do write(c[j]); //输出计算后c的值
writeln;
end.

6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp);
var
i,len:integer;
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
len:=a[0];d[0]:=1;
for i:=len downto 1 do begin
multiply(d,10,d);
d[1]:=a[i];
while(compare(d,b)>=0) do {即d>=b}
begin
Subtract(d,b,d);
inc(c[i]);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;
7.精确计算n!
const max=10000; n=2000;
var a:array[1..max]of 0..9;
i,j,k,x:integer;
begin
k:=1; a[k]:=1;{a=1}
for i:=2 to n do{a←1*2*3….*n}
begin
x:=0;{进位初始化}
for j:=1 to k do{a=a*i}
begin
x:=x+a[j]*i; a[j]:=x mod 10;x:=x div 10
end;
while x>0 do {处理最高位的进位}
begin
k:=k+1;a[k]:=x mod 10;x:=x div 10
end
end;
for i:=k downto 1 do write(a[i]); {输出a}
end.
(六) 常用算法
（1）字符串匹配的KMP算法
[源程序]
procedure get_next(s:string; var next:inttype);
var
j,k:integer;
begin
j:=1;