当前位置:首页 >> 学科竞赛 >>

NOIP复习手册


NOIP 复习手册                                                         

崔晨

莒县一中

一、Pascal语言基础知识?
1.基

本数据类型 Type byte shortint word integer longint longword int64 qword real single double comp extended 2.标准过程与函数 函数 abs(x) sqr(x) sqrt(x) exp(x) ln(x) trunc(x) round(x) ord(x) chr(x) pred(x) succ(x) odd(x)
第 1 页

Range 整型 0..255 -128 .. 127 0 .. 65535 -32768 .. 32767 -2^31..2^31-1 0..2^32-1 -2^63..2^63-1 0..2^64-1 实型 2.9E-39 .. 1.7E38 1.5E-45 .. 3.4E38 5.0E-324 .. 1.7E308 -2^63+1..2^63-1 3.4E-4932 .. 1.1E4932 功能 绝对值 平方 平方根 指数 自然对数 截尾 舍入 序号 字符 前驱 后继 奇函数 自变量类型 算术函数 整型/实型 整型/实型 非负整型/非负实型 整型/实型 整型/实型 转换函数 实型 实型 整型/字符型/布尔型 整型 顺序函数 整型/字符型/布尔型 整型/字符型/布尔型 逻辑判断函数 整型 布尔型 整型 整型 整型 字符型 同自变量 同自变量 非负实数 实型 实型 结果类型

Size in bytes 1 1 2 2 4 4 8 8 6 4 8 8 10 说明 求 x 的绝对值 求 x 的平方 求 x 的算数平方根 e^x 求 x 的自然对数 取 x 的整数部分 对 x 的十分位进行四 舍五入 求 x 对应的序号 求序号 x 对应的字符 求 x 的前驱 求 x 的后继 判断 x 是否为奇数

整型/字符型/布尔型 整型/字符型/布尔型

NOIP 复习手册                                                         

崔晨

莒县一中

3.字符串的常用操作 操作 length(s) copy(s,w,k) 类型 函数 函数 作用 求字符串 s 的长度 复制 s 中从 w 开始的 k 位 返回值 整型 字符串 例子 s:='123456789'; l:=length(s);{l 的值为 9} s:='123456789'; s1:=copy(s,3,5);{s1 的值是'34567'} var s:string;k,code:integer; s:='1234'; val(s,k,code); write(k);{k=1234} i:=1234; str(i,s); write(s);{s='1234'} s := 'Honest Abe Lincoln'; Delete(s,8,4); Writeln(s); { 'Honest Lincoln' } S := 'Honest Lincoln'; Insert('Abe ', S, 8); { 'Honest Abe Lincoln' } S := ' 123.5'; i :=Pos(' ', S);{i 的值为 1} s1:='1234'; s2:='5678'; s:=s1+s2;{'12345678'} 6.Pascal 常见错误含义 错误代码 含义 4.记录类型 type 类型标识符=record 字段名1:类型1; 字段名2:类型2; ... 字段名n:类型n; end; 1 2 102 103 104 105 106 5.文件类型 assign(input,'filename.in'); reset(input); assign(output,'filename.out'); rewrite(output); close(input); close(output); 200 201 202 203 204 205 206 207
第 2 页

val(s,k,code)

过程

将字符串 s 转为数值,存 在 k 中; code 是错误代码



str(i,s)

过程

将数值 i 转为字符串 s



Delete(s,w,k)

过程

在 s 中删除从第 w 位开始 的 k 个字符 将 s1 插到 s 中第 w 位 求字符 c 在 s 中的位置



Insert(s1,S,w) Pos(c,S)

过程 函数 运 算 符

无 整型

+

将两个字符串连接起来



无效 DoS 功能号 文件末找到 文件变量末赋值 文件未打开 文件未用输入方式打开 文件末用输出方式打开 无效数字格式 被零除 范围检查错 堆栈溢出错 堆溢出错 无效指针操作 浮点上溢出 浮点下溢出 无效浮点运算 集合下标越界 集合溢出 算术上溢错误

213 214 215

NOIP 复习手册                                                         

崔晨

莒县一中

7.Math 库实用汇总 程序开头用 uses Math;来加载 Math 库 函数名称 ceil floor power intpower ldexp log10 log2 logn Max 原型 function ceil(x:float):Integer function floor(x:float):Integer function power(base:float;exponent:float):float function intpower(base:float;const exponent:Integer):float function ldexp(x:float;const p:Integer):float function log10(x:float):float function log2(x:float):float function logn(n:float;x:float):float function Max(a:Integer;b:Integer):Integer function Max(a:Int64;b:Int64):Int64 function Max(a:Extended;b:Extended):Extended function Min(a:Integer;b:Integer):Integer function Min(a:Int64;b:Int64):Int64 function Min(a:Extended;b:Extended):Extended function arcsin(x:float):float function arccos(x:float):float function tan(x:float):float function cotan(x:float):float function function function function function function function function maxvalue(const data:Array[] of float):float maxvalue(const data:Array[] of Integer):Integer maxvalue(const data:PFloat;const N:Integer):float maxvalue(const data:PInteger;const N:Integer):Integer minvalue(const data:Array[] of float):float minvalue(const data:Array[] of Integer):Integer minvalue(const data:PFloat;const N:Integer):float MinValue(const Data:PInteger;const N:Integer):Integer 功能 返回比参数大的最小整数 返回比参数小的最大整数 返回 base 的 exponent 次方 返回 base 的 exponent 次方 返回 2 的 p 次方乘以 x 返回 x 的常用对数 返回 x 以 2 为底的对数 返回 x 以 n 为底的对数 返回 a 与 b 中较大的一个

Min arcsin arccos tan cotan

返回 a 与 b 中较小的一个 返回 x 的反正弦值(弧度制) 返回 x 的反余弦值(弧度制) 返回 x 的正切值(弧度制) 返回 x 的余切值(弧度制)

MaxValue

返回数组中的最大值

MinValue

返回数组中的最小值

sum **

function sum(const data:Array[] of float):float function sum(const data:PFloat;const N:LongInt):float operator **(float,float):float(bas:float;expo:float):float operator **(Int64,Int64):Int64(bas:Int64;expo:Int64):Int64

求数组中所有数之和 同等于 Power,乘方的操作符

第 3 页

NOIP 复习手册                                                         

崔晨

莒县一中

二、常用算法和策略?
数论算法?
1.最大公因数

function gcd(a,b:longint):longint; begin if b=0 then exit(a) else exit(gcd(b,a mod b)); end;
2.最小公倍数

function lcm(a,b:longint):longint; begin lcm:=a div gcd(a,b)*b;//notice:要先除后乘,避免溢出 end;
3.快速幂算法pow

function pow(x,n:longint):longint;overload; begin if n=0 then exit(1); pow:=pow(x,n div 2); pow:=pow*pow; if (n and 1)=1 then pow:=pow*x; end;
4.快速幂算法pow(mod p)

function pow(x,n,p:longint):longint; begin if n=0 then exit(1); pow:=pow(x,n div 2,p); pow:=int64(pow)*pow mod p;//注意小心溢出 if (n and 1)=1 then pow:=int64(pow)*x mod p; end;
5.快速幂非递归

function pow(x,n:longint):longint; var result:longint; begin result:=1; while n<>0 do begin if (n and 1)=1 then result:=result*x; x:=x*x;
第 4 页

NOIP 复习手册                                                         

崔晨

莒县一中

n:=n >> 1; end; exit(result); end;
6.朴素判断素数

function is_prime(x:longint):boolean; var i:longint; begin for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(false); exit(true); end;
7.素数的筛法

procedure prime; begin fillchar(bool,sizeof(bool),true); for i:=2 to trunc(sqrt(n)) do if bool[i] then begin j:=i; while j+i<=n do begin j:=j+i; bool[j]:=false; end; end; for i:=2 to n do if bool[i] then writeln(i); end;
8.分解质因数

procedure deal; begin i:=2; sum:=0; while i<=n do begin if n mod i=0 then begin inc(sum); f[sum]:=i; while n mod i=0 do n:=n div i; end; inc(i); end; for i:=1 to sum do write(f[i],' '); end;

第 5 页

NOIP 复习手册                                                         

崔晨

莒县一中

排序算法?
1.选择排序(优化版) (时间复杂度 O(n^2)) (空间复杂度 O(1) )(不稳定)

program selectsort; const mx=10000; var d:array[1..max]of longint; n,i,j,k:longint; begin readln(n); for i:=1 to n do read(d[i]); for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if d[j]<d[k] then k:=j; if k<>i then begin j:=d[k]; d[k]:=d[i]; d[i]:=j; end; end; for i:=1 to n do writeln(d[i]); end.
2.冒泡排序(优化版) (时间复杂度 O(n^2)) (空间复杂度 O(1) )(稳定)

program bubble; const mx=10000; var d:array[1..mx]of longint; n,i,j,k:longint; sorted:boolean; begin readln(n); for i:=1 to n do read(d[i]); sorted:=false; i:=1; while not sorted do begin sorted:=true; for j:=n-1 downto i do if d[j+1]<d[j] then begin sorted:=false; k:=d[j]; d[j]:=d[j+1]; d[j+1]:=k; end; i:=i+1; end; for i:=1 to n do writeln(d[i]); end.
3.插入排序(二分优化版) (时间复杂度 O(n^2)) (空间复杂度 O(1) )(稳定)

procedure insert_sort;
第 6 页

NOIP 复习手册                                                         

崔晨

莒县一中

var i,j,mid,l,r:longint; begin for i:=2 to n do begin l:=1;r:=i; a[0]:=a[i]; while l<r do begin mid:=(l+r) >> 1; if a[mid]>=a[0] then r:=mid else l:=mid+1; end; for j:=i downto l+1 do a[j]:=a[j-1]; a[l]:=a[0]; end; end;
4.快速排序(时间复杂度 O(nlogn)) (空间复杂度 O(logn)~O(n))(不稳定) 取首快排

procedure qsort(head,tail:longint); var x,i,j:longint; begin x:=d[head]; i:=head; j:=tail; while i<j do begin while(i<j)and(d[j]>=x)do j:=j-1; d[i]:=d[j]; while(i<j)and(d[i]<=x)do i:=i+1; d[j]:=d[i]; end; d[i]:=x; if head<j-1 then qsort(head,j-1); if i+1<tail then qsort(i+1,tail); end;
随机快排(随机算法使快速排序的时间复杂度退化的概率大大降低)

procedure qsort(head,tail:longint); var i,j,x,t:longint; begin i:=head;j:=tail; x:=a[random(tail-head+1)+head]; while i<j do begin while a[i]<x do inc(i); while x<a[j] do dec(j); if (i<=j) then begin t:=a[i];a[i]:=a[j];a[j]:=t;
第 7 页

NOIP 复习手册                                                         

崔晨

莒县一中

inc(i);dec(j); end; end; if head<j then qsort(head,j); if i<tail then qsort(i,tail); end;
取中快排

procedure qsort(head,tail:longint); var i,j,x,t:longint; begin i:=head;j:=tail; x:=a[(tail+head) div 2]; while i<j do begin while a[i]<x do inc(i); while x<a[j] do dec(j); if (i<=j) then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; end; if head<j then qsort(head,j); if i<tail then qsort(i,tail); end;
5.归并排序(时间复杂度 O(nlogn)) (空间复杂度 O(n) )(稳定)

procedure msort(s,t:longint); var m,i,j,k:longint; begin if s=t then exit; m:=(s+t)>>1; msort(s,m); msort(m+1,t); i:=s;j:=m+1;k:=s; while (i<=m) and (j<=t) do begin if a[i]<a[j] then begin r[k]:=a[i];inc(i);inc(k); //ans:=ans+t-k+1;{应用:加这一句话就可以求逆序对的个数} end else begin r[k]:=a[j];inc(j);inc(k);end; end; while i<=m do begin r[k]:=a[i];inc(i);inc(k);end; while j<=t do begin r[k]:=a[j];inc(j);inc(k);end;
第 8 页

NOIP 复习手册                                                         

崔晨

莒县一中

for i:=s to t do a[i]:=r[i]; end;
应用:求逆序对的个数 6.桶排序(时间复杂度 O(n),注:也与数据的规模有关)(稳定)

var b:array[0..100] of integer; k:0..100; i,j:integer; Begin readln(n); for i:=0 to 100 do b[i]:=0; for i:=1 to n do begin read(k);b[k]:=b[k]+1;end; for i:=0 to 100 do for j:=1 to a[i] do writeln(i,’ ’); end.
7.堆排序(时间复杂度 O(nlogn)) (空间复杂度 O(1) )(不稳定)

program heapsort; const max=10000; var d:array[1..max]of longint; n,i,total,tmp:longint; procedure down(i:integer); var t,j:longint; begin while i<=(total>>1) do begin j:=2*i; if(j<total)and(d[j+1]<d[j])then j:=j+1; if d[i]>d[j] then begin t:=d[i];d[i]:=d[j];d[j]:=t;i:=j;end else break; end; end; begin readln(n); for i:=1 to n do read(d[i]); total:=n; for i:=(n>>1) downto 1 do down(i); for i:=1 to n do begin tmp:=d[1];d[1]:=d[total];d[total]:=tmp; total:=total-1; down(1); end; for i:=n downto 1 do writeln(d[i]); end.

第 9 页

NOIP 复习手册                                                         

崔晨

莒县一中

高精度运算
高精度数定义:

type hp=array[0..maxlen] of integer;
输入字符串转化为数组存储:

procedure convert(var a:hp;s:ansistring); var i:longint; begin a[0]:=length(s); for i:= a[0] downto 1 do a[a[0]-i+1]:=ord(s[i])-ord('0'); end;
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; for i:=c[0] downto 1 do write(c[i]); end;
2.高精度减法 正负号问题:

procedure sign(var sa,sb:ansistring); var t:ansistring; begin if sa=sb then begin writeln('0');halt;end; if (length(sa)<length(sb))or((length(sa)=length(sb))and(sa<sb)) then begin f:='-'; t:=sa; sa:=sb; sb:=t; end; end; procedure subtract(a,b:hp;var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a[0];
第 10 页

NOIP 复习手册                                                         

崔晨

莒县一中

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; end; while (len>1) and (c[len]=0) do dec(len); c[0]:=len; if f='-' then write(f); for i:=c[0] downto 1 do write(c[i]); end;
3.高精度乘法 高精度*单精度(有很多细节方面的问题,因此本程序给出完整可运行版)

const max=200; var sa:string; i,la:integer; b,c:longint; a:array[1..max+8] of longint; begin readln(sa); readln(b); if (sa='0')or(b=0) then begin writeln(0);halt;end; la:=length(sa); fillchar(a,sizeof(a),0); for i:= la downto 1 do a[la-i+1]:=ord(sa[i])-ord('0'); for i:=1 to la do a[i]:=a[i]*b; for i:=1 to la do begin a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; end; c:=a[la+1]; while c<>0 do begin inc(la); a[la]:=c mod 10; c:=c div 10; end; for i:=la downto 1 do write(a[i]); end.

第 11 页

NOIP 复习手册                                                         

崔晨

莒县一中

高精度*高精度(有很多细节方面的问题,因此本程序给出完整可运行版)

const max=200; var sa,sb:ansistring; x:longint;a,b:array[1..max] of integer; c:array[1..2*max] of integer; i,j,la,lb,len:integer; begin readln(sa); readln(sb); if (sa='0')or(sb='0') then begin writeln(0);halt;end; fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); la:=length(sa);lb:=length(sb); for i:= la downto 1 do a[la-i+1]:=ord(sa[i])-ord('0'); for i:= lb downto 1 do b[lb-i+1]:=ord(sb[i])-ord('0'); for i:=1 to la do for j:=1 to lb do c[i+j-1]:=c[i+j-1]+a[i]*b[j]; len:=la+lb; for i:=1 to len do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10; end; while c[len]=0 do dec(len); x:=c[len]; while x>0 do begin c[len]:=x mod 10; x:=x div 10; inc(len); end; for i:=len-1 downto 1 do write(c[i]); end.
4.高精度除法(了解即可,因此代码不再给出,有兴趣的可以自行上网搜索) 高精度除以单精度 高精度除以高精度

第 12 页

NOIP 复习手册                                                         

崔晨

莒县一中

常用策略?
本节以例题为主,主要回顾并体会这些策略的思想,例题大多是在很多地方反复出现的,具有一定代表性。

回溯法
N 皇后问题

var a:array [1..100] of integer; n,p:integer; function find(k,i:integer):boolean; var j:integer;yes:boolean; begin yes:=true; for j:=1 to k-1 do if (abs(a[j]-i)=abs(j-k))or(i=a[j])then yes:=false; find:=yes; end; procedure print; var i:integer; begin p:=1; for i:=1 to n do write(a[i]:5); writeln; end; procedure try(k:integer); var i:integer; begin if k>n then print else for i:=1 to n do if find(k,i) then begin a[k]:=i; try(k+1); end; if (p=0)and(k=1)and(a[k]=3) then writeln('no solute!') end; begin p:=0; readln(n); try(1); end.
第 13 页

NOIP 复习手册                                                         

崔晨

莒县一中

递推法
实数数列

第 14 页

NOIP 复习手册                                                         

崔晨

莒县一中

第 15 页

NOIP 复习手册                                                         

崔晨

莒县一中

(参考代码)

const maxn=60; var n,m,i:integer; d:real; list:array[1..maxn]of real; s:array[1..maxn,1..3]of longint; procedure init; begin readln(n,m,d,list[1],list[n]); end; procedure solve; begin s[1,1]:=0;s[1,2]:=0;s[1,3]:=1; s[2,1]:=1;s[2,2]:=0;s[2,3]:=0; for i:=3 to n do begin s[i,1]:=s[i-2,1]-2*s[i-1,1]; s[i,2]:=s[i-2,2]-2*s[i-1,2]+2; s[i,3]:=s[i-2,3]-2*s[i-1,3]; end; end; procedure main; begin solve; for i:=2 to m do list[i]:=(list[n]-s[n-i+2,2]*d-s[n-i+2,3]*list[i-1])/s[n-i+2,1]; writeln(list[m]:40:20); end; begin init; main; end.

第 16 页

NOIP 复习手册                                                         

崔晨

莒县一中

第 17 页

NOIP 复习手册                                                         

崔晨

莒县一中

第 18 页

NOIP 复习手册                                                         

崔晨

莒县一中

(参考代码)

var k,i:integer; d,d1:real; dis,oil:array[0..100] of real; begin k:=1; d:=500; dis[1]:=500; oil[1]:=500; repeat k:=k+1; d:=d+500/(2*k-1); dis[k]:=d; oil[k]:=oil[k-1]+500; until d>=1000; dis[k]:=1000; d1:=1000-dis[k-1]; oil[k]:=d1*(2*k+1)+oil[k-1]; writeln(' No. Distance oil'); for i:=0 to k do writeln(i:4,1000-dis[k-i]:20:10,oil[k-i]:20:10); end.

第 19 页

NOIP 复习手册                                                         

崔晨

莒县一中

贪心法

第 20 页

NOIP 复习手册                                                         

崔晨

莒县一中

第 21 页

NOIP 复习手册                                                         

崔晨

莒县一中

第 22 页

NOIP 复习手册                                                         

崔晨

莒县一中

第 23 页

NOIP 复习手册                                                         

崔晨

莒县一中

递归法

第 24 页

NOIP 复习手册                                                         

崔晨

莒县一中

分治法
分治法的例子有很多,比如上面提到的快速排序和归并排序,都是运用了分治的思想。 分治法最常见的形式就是二分法:

function binsearch(k:keytype):integer; var low,hig,mid:integer; begin low:=1;hig:=n; mid:=(low+hig)>>1; while (a[mid].key<>k) and(low<=hig) do begin if a[mid].key>k then hig:=mid-1 else low:=mid+1; mid:=(low+hig) div 2; end; if low>hig then mid:=0; binsearch:=mid; end;
第 25 页

NOIP 复习手册                                                         

崔晨

莒县一中

三、数据结构及相关算法?
栈的基本操作?
(1)栈的初始化操作(栈置空) top:=0 (2)判断栈空函数 function sempty(stack:arraytype):boolean; begin sempty:=(top=0); end; (3)判断栈满函数 function sfull(stack:arraytype):boolean; begin sfull:=(top=n); end; (4)进栈的操作过程(压栈push) procedure push(var tack:arraytype;x:integer); begin if sfull(stack)then writeln(‘Stack full!’) else begin top:=top+1; stack[top]:=x; end end; (5)读栈函数 function reads(stack:arraytype):integer; begin if sempty(stack) then writeln(‘Stack empty!’) else reads:=stack[top]; end; (6)出栈操作过程(pop) procedure pop(var stack:arraytype;var x:integer); begin if sempty(stack)then writeln(‘Stack empty!’) else begin x:=stack[top]; top:=top-1; end; end;
第 26 页

NOIP 复习手册                                                         

崔晨

莒县一中

队列的基本操作?
(1)初始化队列 procedure qini (var q:queue); begin f:=0; r:=0; end; (2)判断队列是否为空 function qempty(q:queue):boolean; begin qempty:=(r=f); end; (3)判断队列是否为满 function qfull(q:queue):boolean; begin qfull:=(r=m); end; (4)入队 procedure qadd(var q:queue;x:elemtype); begin if qfull(q)then writeln (‘overflow’) else begin r:=r+1; q[r]:=x; end; end; (5)出队 procedure qdel(var q:queue;var x:elemtype); begin if qempty(q)then writeln(‘underflow’) else begin f:=f+1; x:=q[f]; end; end;

循环队列:
初始化:f=r=m 队空:f=r 队满:f=(rmodm)+1 进队:r=rmodm+1 出队:f=fmodm+1

第 27 页

NOIP 复习手册                                                         

崔晨

莒县一中


二叉树的性质:? ①:在非空二叉树的第 i 层上至多有 2i-1 个顶点(i>=1) ②:深度为 k 的二叉树至多有 2k-1 个结点(k>=1) ③:对任何一棵非空二叉树 T,如果叶结点个数为 n0,度为 2 的结点个数为 n2,则 n0=n2+1 ④:具有 n 个结点的完全二叉树的深度为?log2n?+1 ⑤:对一棵有 n 个结点的完全二叉树(其深度为?log2n?+1)的结点按层序编号(从第一层到第?log2n?+1 层,每 层从左到右) ,则对任一结点 i(1<=i<=n) ,有: (1)如果 i=1,则结点 i 是二叉树的根,无双亲;如果 i>1,则其双亲序号是结点?i/2?。 (2)如果 2*i>n,则结点 i 无左孩子(当然也无右孩子,即结点 i 为叶结点);否则其左孩子序号是结点 2*i。 (3)如果 2*i+1>n,则结点无右孩子;否则其右孩子序号是结点 2*i+1。

前序序列:abdehicfg  中序序列:dbheiafcg  后序序列:dhiebfgca

前序遍历:

procedure preorder(i:integer); begin if i<>0 then begin 访问处理tree[i].data; preorder(tree[i].lch); preorder(tree[i].rch); end; end;

第 28 页

NOIP 复习手册                                                         

崔晨

莒县一中

中序遍历:

procedure inorder(i:integer); begin if i<>0 then begin inorder(tree[i].lch); 访问处理tree[i].data; inorder(tree[i].rch); end; end;
后序遍历:

procedure postorder(i:integer); begin if i<>0 then begin postorder(tree[i].lch); postorder(tree[i].rch); 访问处理tree[i].data; end; end;
已知前序中序求后序:

procedure Solve(pre,mid:string); var i:integer; begin if (pre='')or (mid='')then exit; i:=pos(pre[1],mid); solve(copy(pre,2,i),copy(mid,1,i-1)); solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i)); post:=post+pre[1]; {加上根,递归结束后post即为后序遍历} end;
已知中序后序求前序:

procedure Solve(mid,post:string); var i:integer; begin if (mid='') or (post='')thenexit; i:=pos(post[length(post)],mid); pre:=pre+post[length(post)]; {加上根,递归结束后pre即为前序遍历} solve(copy(mid,1,I-1),copy(post,1,I-1)); solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i)); end;
第 29 页

NOIP 复习手册                                                         

崔晨

莒县一中

已知前序后序求中序的一种:

function ok(s1,s2:string):boolean; var i,l:integer; p:boolean; begin ok:=true; l:=length(s1); for i:=1 to l do begin p:=false; for j:=1 to l do if s1[i]=s2[j] then p:=true; if not p then exit(fasle); end; end; procedure solve(pre,post:string); var i:integer; begin if (pre='')or (post='') thenexit; i:=0; repeat inc(i); until ok(copy(pre,2,i),copy(post,1,i)); solve(copy(pre,2,i),copy(post,1,i)); midstr:=midstr+pre[1]; solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1)); end;
哈夫曼树:

const maxn=10000; max=2*maxn-1; type node=record data:int64; prt,lch,rch:0..max; end; treetype=array[1..max]of node; var tree:treetype;n,i:longint;s:int64; function min(h:integer):integer; var i,p:longint;m1:int64; begin m1:=maxlongint; for p:=1 to h do if (tree[p].prt=0)and(m1>tree[p].data) then begin i:=p;m1:=tree[p].data; end; min:=i; end;
第 30 页

NOIP 复习手册                                                         

崔晨

莒县一中

procedure hufm(var tree:treetype); var k,i,j:longint; begin fillchar(tree,sizeof(tree),0); for i:=1 to n do read(tree[i].data); for k:=n+1 to 2*n-1 do begin i:=min(k-1);tree[i].prt:=k;tree[k].lch:=i; j:=min(k-1);tree[j].prt:=k;tree[k].rch:=j; tree[k].data:=tree[i].data+tree[j].data; end; end;
二叉排序树:

type tree=^node; node=record data:Integer; lchild,rchild:tree; end; var bt:tree; n:Integer; procedure creat_order_tree(var btx:tree;nx:Integer); var p,s,f:tree; flag:Boolean; begin New(s); s^.data:=nx; s^.lchild:=nil; s^.rchild:=nil; flag:=True; p:=btx; while (p<>nil)and flag do begin f:=p; if s^.data=p^.data then flag:=False else if s^.data<p^.data then p:=p^.lchild else p:=p^.rchild; end; If flag then begin if btx=nil then btx:=s; if s^.data<f^.data then f^.lchild:=s; if s^.data>f^.data then f^.rchild:=s; end; end; procedure inorder_print(btx:tree); begin
第 31 页

NOIP 复习手册                                                         

崔晨

莒县一中

if btx<>nil then begin inorder_print(btx^.lchild); write(btx^.data,' '); inorder_print(btx^.rchild); end; end; begin bt:=nil; repeat read(n); If n>=0 Then creat_order_tree(bt,n); until n<0; inorder_print(bt); end.
并查集:

var n,m,p:longint; father,rank:array [1..50000] of longint; function find(x:longint):longint; begin if father[x]=0 then exit(x); if father[father[x]]=0 then exit(father[x]); find:=find(father[x]); father[x]:=find; end; procedure swap(var x,y:longint); begin x:=x xor y; y:=x xor y; x:=x xor y; end; procedure union(x,y:longint); var t:longint; begin x:=find(x); y:=find(y); if rank[x]>rank[y] then swap(x,y); if rank[x]=rank[y] then inc(rank[x]); father[x]:=y; end; procedure make(n:longint); var i:longint; begin for i:=1 to n do father[i]:=0; end;
第 32 页

NOIP 复习手册                                                         

崔晨

莒县一中

procedure handle; var i,x,y:longint; begin for i:=1 to m do begin read(x,y); if find(x)<>find(y) then union(x,y); end; end; procedure init; begin read(n,m,p); make(n); fillchar(rank,sizeof(rank),0); handle; end; procedure print(x,y:longint); begin if find(x)=find(y) then writeln('Yes') else writeln('No'); end; procedure ask(p:longint); var i,x,y:longint; begin for i:=1 to p do begin read(x,y); print(x,y); end; end; begin init; ask(p); end.
最近公共祖先 LCA(tarjan)

const v=50000; var fa,ans,d,o:Array[0..v]of longint; b:array[-v..v]of record y,t,nx:longint; end; x,y,t,i,m,ntotq:a; z:Array[0..v,0..1]of longint; function findfa(u:longint):longint; begin if fa[u]=u then exit(u);
第 33 页

NOIP 复习手册                                                         

崔晨

莒县一中

fa[u]:=findfa(fa[u]); exit(fa[u]); end; procedure insert(x,y,t,k:longint); begin inc(tot); b[tot].nx:=z[x,k];b[tot].y:=y; b[tot].t:=t;z[x,k]:=tot; b[-tot].nx:=z[y,k]; b[-tot].y:=x; b[-tot].t:=t;z[y,k]:=-tot; end; procedure dfs(u:longint); var c,y:a; begin fa[u]:=u;o[u]:=1;c:=z[u,1]; while c<>0 do begin y:=b[c].y; if o[y]=1 then begin t:=b[c].t; s[t]:=d[u]+d[y]-2*d[findfa(y)]; end; c:=b[c].nx; end; c:=z[u,0]; while c<>0 do begin y:=b[c].y; if o[y]=0 then begin d[y]:=b[c].t+d[u]; dfs(y); fa[y]:=u; end; c:=b[c].nx; end; end; begin readln(n,n); for i:=1 to n do begin readln(x,y,t); insert(x,y,t,0); end; readln(m);
第 34 页

NOIP 复习手册                                                         

崔晨

莒县一中

for i:=1 to m do begin readln(x,y); insert(x,y,i,1); end; dfs(1); for i:=1 to m do writeln(ans[i]); end.
树状数组:

计算2^k,k为i二进制形式下末尾0的个数 function lowbit(i:longint):longint; begin lowbit:=i and (i xor (i-1)); end; (1)构造C数组 for i:=1 to n do for j:=i-lowbit(i) to i do C[i]:=C[i]+a[j]; (2)动态更新C数组 procedure change(i,delta:longint); begin while i<n do begin C[i]:=C[i]+delta; i:=i+lowbit(i); end; end; 可以将构造C数组和更新合到一个过程中。 初始时,置C数组中每一个元素的值为0,每读一个a[i]的值,即时更新C数组中对应的元素值增加a[i], 操作如下: procedure init; begin for i:=1 to n do begin read(a[i]); change(i,a[i]); end; end; 时间复杂度为 O(nlogn)
第 35 页

NOIP 复习手册                                                         

崔晨

莒县一中

图?
深度优先搜索(dfs)

procedure dfs(i:integer); var j:integer; begin write(t[i]); visited[i]:=true; for j:=1 to n do if (a[i,j]=1) and not(visited[j]) then dfs(j); end;
广度优先搜索(bfs)

procedure bfs(i:integer); var j:integer; begin write(t[i]); visited[i]:=true; tail:=tail+1; queue[tail]:=i while head <=tail do begin for j:=1 to n do if (a[queue[head],j]=1) and not(visited[j]) then begin write(t[j]); visited[j]:=true; tail:=tail+1; queue[tail]:=j; end; head:=head+1; end; end;
计算图的传递闭包:

procedure longlink; var t:array[1..maxn,1..maxn] ofboolean; begin fillchar(t,sizeof(t),false); for k:=1to n do for i:=1 to n do for j:=1 to n do t[i,j]:=t[i,j]or(t[i,k] and t[k,j]); end;

第 36 页

NOIP 复习手册                                                         

崔晨

莒县一中

Prim 算法:

procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min,ans:integer; begin for i:=1 to n do begin lowcost[i]:=cost[v0,i]; closest[i]:=v0; end; for i:=1 to n-1 do {寻找离生成树最近的未加入顶点k} begin min:=maxint; for j:=1 to n do if (lowcost[closest[j]]=0)and(lowcost[j]<min)and(lowcost[j]<>0) then begin min:=lowcost[j]; k:=j; end; inc(ans, lowcost[k]); {把这条边加入生成树边集合T中} lowcost[k]:=0; {lowcost[k] = 0表示把顶点k加入集合U中} {修正各点的lowcost和closest值} for j:=1 to n do if cost[k,j]<lowcost[j] then begin lowcost[j]:=cost[k,j]; closest[j]:=k; end; end; writeln(ans); end;{prim}
时间复杂度为O(n^2),与边数无关,适合于稠密图。 prim 优化算法框架(利用堆),每次取最小值为 O(logm),总时间复杂度为 O(nlogm) 初始化,树仅含一个任意一点 v0 把 v0 的邻边插入堆 for i:=1 to n-1 do begin 从堆中取出最小值,设边为(u’,v’),v’为新点 (u’,v’)加入生成树中 v’和它所有不在树中的邻居组成的边插入堆 end;
第 37 页

NOIP 复习手册                                                         

崔晨

莒县一中

Kruskal 算法:

Program kruskal; const MXN=1000; type rqmap=record s,t,v:longint; end; var map:array[1..MXN*MXN] of rqmap; father:array[1..MXN] of longint; n,m,i,ingraph,ans:longint; procedure qsort(b,e:longint); var i,j,x:longint;t:rqmap; begin i:=b;j:=e;x:=map[(i+j)>>1].v; while (i<=j) do begin while (map[i].v<x) do inc(i); while (map[j].v>x) do dec(j); if (i<=j) then begin t:=map[i];map[i]:=map[j];map[j]:=t;inc(i);dec(j);end; end; if i<e then qsort(i,e);if j>b then qsort(b,j); end; function find(x:longint):longint; begin if (father[x]=x) then exit(x); father[x]:=find(father[x]); exit(father[x]); end; procedure union(a,b:longint); begin father[find(a)]:=find(father[b]); end; begin readln(n,m); for i:=1 to n do father[i]:=i; for i:=1 to m do readln(map[i].s,map[i].t,map[i].v); qsort(1,m);ans:=0;ingraph:=1;i:=0; while (ingraph<n) do begin inc(i); if find(map[i].s)<>find(map[i].t) then begin inc(ingraph);inc(ans,map[i].v);union(map[i].s,map[i].t); end; end; writeln(ans); end.
时间复杂度为O(ElogE),时间复杂度取决于边的数目,适合稀疏图。
第 38 页

NOIP 复习手册                                                         

崔晨

莒县一中

Dijkstra 算法:

const max=5; var cost:array[1..max,1..max] of longint; a:array[1..max]of integer; n,k,i,j:integer; mark:array[1..max] of boolean; procedure init; var i,j:integer; begin readln(n,k); for i:=1 to n do for j:=1 to n do read(cost[i,j]); end; procedure dijkstra; var i,j,min,minj,temp:integer; begin fillchar(mark,sizeof(mark),false); for i:=1 to n do a[i]:=maxint; a[k]:=0; for i:=1 to n-1 do begin min:=maxint; for j:=1 to n do if (not mark[j]) and (a[j]<min) then begin min:=a[j]; minj:=j; end; mark[minj]:=true; for j:=1 to n do if (not mark[j]) and (cost[minj,j]>0) then begin temp:=a[minj]+cost[minj,j]; if temp<a[j] then a[j]:=temp; end; end; end; begin init; dijkstra; for i:=1 to n-1 do write(a[i],' '); writeln(a[n]); end.
本质上是贪心算法,朴素实现时间复杂度为O(V^2+E),堆优化时间复杂度为O(VlogV+E)。
第 39 页

NOIP 复习手册                                                         

崔晨

莒县一中

Floyd 算法:

procedure floyd; var i,j,k:integer; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if a[i,k]+a[k,j]<a[i,j] then a[i,j]:=a[i,k]+a[k,j]; end;
本质是动态规划,时间复杂度为O(n^3),可以求得所有点对之间的最短路径,注意不要弄错了for循环的顺序。 Floyd算法可以被用来求最小环,后面就有一段代码。 Bellman-ford 算法:

var e:array[1..maxe]of record a,b,w:longint;end; { 距源点s距离 } dis:array[1..maxn]of longint;{ 前驱 } pre:array[1..maxn]of longint; m,n,s:longint; procedure relax(u,v,w:longint); begin if dis[u]+w<dis[v] then begin dis[v]:=dis[u]+w; pre[v]:=u; end; end; function bellman_ford:boolean; var i,j:longint; begin { 每条边松弛 } for i:=1 to n-1 do for j:=1 to m do with e[j] do relax(a,b,w); { 如果还能松弛 } for i:=1 to m do with e[i] do if dis[a]+w<dis[b] then exit(false); exit(true) end;
时间复杂度为O(VE),但进行松弛操作时存在冗余。
第 40 页

NOIP 复习手册                                                         

崔晨

莒县一中

SPFA 算法(Bellman-ford 算法队列优化):

const maxp=10000; var p,c,s,t:longint; {p,结点数;c,边数;s:起点;t:终点} a,b:array[1..maxp,0..maxp] of longint;{a[x,y]存x,y之间边的权;b[x,c]存与x相 连的第c个边的另一个结点y} d:array[1..maxp] of integer; {队列} v:array[1..maxp] of boolean; {是否入队的标记} dist:array[1..maxp] of longint; {到起点的最短路} head,tail:longint; {队首/队尾指针} procedure init; var i,x,y,z:longint; begin read(p,c); for i := 1 to c do begin readln(x,y,z);{x,y:一条边的两个结点;z:这条边的权值} inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z;{b[x,0]:以x为一个结点的边的条数} inc(b[y,0]);b[y,b[y,0]]:=x;a[y,x]:=z; end; readln(s,t); {读入起点与终点} end; procedure spfa(s:longint);{SPFA} var i,j,now,sum:longint; begin fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false); for j:=1 to p do dist[j]:=maxlongint; dist[s]:=0;v[s]:=true;d[1]:=s;{队列的初始状态,s为起点} head:=1;tail:=1; while head<=tail do {队列不空} begin
第 41 页

NOIP 复习手册                                                         

崔晨

莒县一中

now:=d[head]; {取队首元素} for i := 1 to b[now,0] do if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then begin dist[b[now,i]]:= dist[now]+a[now,b[now,i]]; {修改最短路} if not v[b[now,i]] then {扩展结点入队} {注意判断是否入队的条件是“是否修改了最短路”} begin inc(tail); d[tail]:=b[now,i]; v[b[now,i]]:=true; end; end; v[now]:=false;{释放结点} inc(head);{出队} end; end; procedure print; begin writeln(dist[t]); end; begin init; spfa(s); print; end.
SPFA算法的时间复杂度为O(ke),其中k是常数,通常在 2 左右。 拓扑排序:

while true do begin k:=0; for i:=n downto 1 do if f[i]=0 then k:=i; if k=0 then break; inc(m); q[m]:=k; f[k]:=-1; for i:=1 to d[k] do dec(f[a[k,i]]); end;
第 42 页

NOIP 复习手册                                                         

崔晨

莒县一中

最小环:

for k:=1 to n do begin for i:=1 to k-1 do for j:=i+1 to k-1 do ans:=min(ans,f[i,j]+a[i,k]+a[k,j]); for i:=1 to n do for j:=1 to n do f[i,j]:=min(f[i,j],f[i,k]+f[k,j]); end;
第 n 最短路径问题: 第二最短路径:每举最短路径上的每条边,每次删除一条,然后求新图的最短路径,取这些路径中最短的一条即 为第二最短路径。 同理,第 n 最短路径可在求解第 n-1 最短路径的基础上求解。 一笔画问题: 充要条件:图连通且奇点个数为 0 个或 2 个。 其他图论知识: 1.欧拉路:在无孤立结点的图 G 中,若存在一条路,经过图中每条边一次且仅一次,则称此路为欧拉路。 2.欧拉回路:若存在一条路,经过图中每条边一次且仅一次,且回到原来位置,则称此路为欧拉回路。 3.欧拉图:存在欧拉回路的图,称为欧拉图。 4.定理 1:存在欧拉路的条件:图是连通的,且存在 0 个或 2 个奇点。 5.定理 2:存在欧拉回路的条件:图是连通的,且存在 0 个奇点。 6.哈密尔顿图:无孤立结点的连通图,若存在一条路,经过图中每一个结点一次且仅一次,则称为哈密尔顿图。 7.哈密尔顿环:是一条沿着图的 n 边环行的路径,它访问每一个结点一次且仅一次,并且返回到它的开始位置。

第 43 页

NOIP 复习手册                                                         

崔晨

莒县一中

四、动态规划?
线性动态规划?
1.最长不下降子序列(LIS)(二分优化版本)(时间复杂度为 O(nlogn))

function dichotomy(l,r,aim:longint):longint; var mid:longint; begin{找出小于 aim 的最大编号} while (l+1<r) do begin mid:=(l+r) shr 1; if b[mid]<aim then l:=mid else r:=mid; end; if (b[r]<aim) then exit(r); exit(l); end; procedure lis; var i,t,ans,now:longint; begin fillchar(f,sizeof(f),0); fillchar(b,sizeof(b),10); now:=1; ans:=1; f[1]:=1; b[1]:=a[1]; for i:=2 to n do begin t:=dichotomy(0,now,a[i])+1; f[i]:=max(f[i],t); now:=max(now,t); ans:=max(ans,f[i]); if a[i]<b[f[i]] then b[f[i]]:=a[i]; end; writeln(ans); end;
2.最长公共子序列(LCS)

for i:=1 to n do for j:=1 to m do begin f[i,j]:=0; if x[i]=y[j] then f[i,j]:=f[i-1,j-1]+1 else f[i,j]:=max(f[i-1,j],f[i,j-1]); end;
第 44 页

NOIP 复习手册                                                         

崔晨

莒县一中

背包问题(强烈建议看《背包问题九讲》)?
注:本节完全从《NOIP2002 复习资料》中 copy 来的,向原作者致敬。 背包问题 *部分背包问题可有贪心法求解:计算 pi/wi 数据结构: w:第 i 个背包的重量; p:第 i 个背包的价值; 1.0-1 背包 每个背包只能使用一次或有限次(可转化为一次): 1)求最多可放入的重量。 noip2001 装箱问题 有一个箱子容量为 v(正整数,o≤v≤20000),同时有 n 个物品(o≤n≤30),每个物品有一个体积 (正整数)。要求从 n 个物品中,任取若千个装入箱内,使箱子的剩余空间为最小。 A)搜索方法

procedure search(k,v:integer); {搜索第k个物品,剩余空间为v} var i,j:integer; begin if v<best then best:=v; if v-(s[n]-s[k-1])>=best then exit; {s[n]为前n个物品的重量和} if k<=n then begin if v>w[k] then search(k+1,v-w[k]); search(k+1,v); end; end;
b)dp f[i,j]为前 i 个物品中选择若干个放入使其体积正好为 j 的标志,为布尔型。 实现:将最优化问题转化为判定性问题 f [i,j] = f [i-1,j-w] (w[i]<=j<=v)边界:f[0,0]:=true.

for i:=1 to n do for j:=w[i] to v do f[i,j]:=f[i-1,j-w[i]];
优化:当前状态只与前一阶段状态有关,可降至一维。

f[0]:=true; for i:=1 to n do begin f1:=f; for j:=w[i] to v do if f[j-w[i]] then f1[j]:=true; f:=f1; end;
第 45 页

NOIP 复习手册                                                         

崔晨

莒县一中

2)求可以放入的最大价值。 f[i,j] 为容量为 i 时取前 j 个背包所能获得的最大价值。 f [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] } C.求恰好装满的情况数。 dp:

procedure update; var j,k:integer; begin c:=a; for j:=0 to n do if a[j]>0 then if j+now<=n then inc(c[j+now],a[j]); a:=c; end;
2.可重复背包

1)求最多可放入的重量。

f[i,j]为前 i 个物品中选择若干个放入使其体积正好为 j 的标志,为布尔型。 状态转移方程为 f[i,j] = f [ i-1, j – w[i]*k ] (k=1.. j div w[i])

2)求可以放入的最大价值。

USACO 1.2 Score inflation 进行一次竞赛,总时间 t 固定,有若干种可选择的题目,每种题目可选入的数量不限,每种题目有一个 ti(解答此题 所需的时间)和一个 si(解答此题所得的分数) ,现要选择若干题目,使解这些题的总时间在 t 以内的前提下,所得的 总分最大,求最大的得分。 *易想到: f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j]) 其中 f[i,j]表示容量为 i 时取前 j 种背包所能达到的最大值。 *实现:

begin fillChar(f,SizeOf(f),0); for i:=1 to m do for j:=1 to n do if i-problem[j].time>=0 then begin t:=problem[j].point+f[i-problem[j].time]; if t>f then f:=t; End; writeln(f[m]); End.
第 46 页

NOIP 复习手册                                                         

崔晨

莒县一中

 3)求恰好装满的情况数。

Ahoi2001 problem2 求自然数n本质不同的质数和的表达式的数目。 思路一,生成每个质数的系数的排列,在一一测试,这是通法。

procedure try(dep:integer); var i,j:integer; begin cal; {此过程计算当前系数的计算结果,now为结果} if now>n then exit; {剪枝} if dep=l+1 then begin {生成所有系数} cal; if now=n then inc(tot); exit; end; for i:=0 to n div pr[dep] do begin xs[dep]:=i; try(dep+1); xs[dep]:=0; end; end;
思路二,递归搜索效率较高 

procedure try(dep,rest:integer); var i,j,x:integer; begin if (rest<=0) or (dep=l+1) then begin if rest=0 then inc(tot); exit; end; for i:=0 to rest div pr[dep] do try(dep+1,rest-pr[dep]*i); end; {main: try(1,n); }

第 47 页

NOIP 复习手册                                                         

崔晨

莒县一中

思路三:可使用动态规划求解 USACO1.2 money system V 个物品,背包容量为 n,求放法总数。 转移方程:

procedure update; var j,k:integer; begin c:=a; for j:=0 to n do if a[j]>0 then for k:=1 to n div now do if j+now*k<=n then inc(c[j+now*k],a[j]); a:=c; end; {main} begin read(now); {读入第一个物品的重量} i:=0; {a为背包容量为i时的放法总数}

while i<=n do begin a:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1,作为初值} for i:=2 to v do begin read(now); update; {动态更新} end; writeln(a[n])

? 坐标型动态规划?
经典例题:过河卒,数字三角形。 相信大家都做过,这里不再赘述。

区间型动态规划?
经典例题:石子合并,能量项链。 相信大家都做过,这里不再赘述。
第 48 页

NOIP 复习手册                                                         

崔晨

莒县一中

树型动态规划?
基本步骤(来自王建德课件): 步骤 1:如果问题是一棵隐性树(即不直接以树为背景) ,则需要将问题转化为一棵显性树,并存储各阶段的树状联系; 步骤 2:求解方式与线性 DP 的两个不同点 ①计算顺序不同。线性 DP 有二种方向:顺推与逆推;而树型 DP 亦有二个方向:由根至叶的先根遍历,但这种方向向 下的计算方式在实际的问题中很少运用。根据 DP 由枚举子问题决策状态值的特征,一般采用由叶至根的后根遍历,即 子节点将有用信息向上传递给父节点,逐层上推,最终由根得出最优解。 ②计算方式不同。线性 DP 采用的是传统的迭代形式,而树型 DP 是通过记忆化搜索实现的,因此采用的是递归方式。 经典例题: Binary Apple Tree(Ural 1018) Anniversary Party(POJ 2342)

状态压缩型动态规划?
主要应用了位运算的相关技巧,关于位运算的相关知识可以参考 Matrix67 的《位运算讲稿》 ,后面也会给出部分技巧。

第 49 页

NOIP 复习手册                                                         

崔晨

莒县一中

五、其他?
变量交换的异或写法:

procedure swap(var a,b:longint); begin a:=a xor b; b:=a xor b; a:=a xor b; end;
常见二进制位的变换操作(来自 Matrix67 的位运算讲稿):

常用 ASCII 码(FPC 的菜单中有 ASCII 码表) ord('0')=48;  ord(‘A’):=65;  ord('a')=97; 
第 50 页

NOIP 复习手册                                                         

崔晨

莒县一中

进制转换: 1)任意正整数进制间的互化 除 n(倒)取余 2)实数任意正整数进制间的互化 乘 n(正)取整 3)负数进制: (noip2001 进制转换) 设计一个程序, 读入一个十进制数的基数和一个负进制数的基数,并将此十进制数转换为此负进制下的数: -R ∈ {-2,-3,-4,....,-20} const d='123456789ABCDEFGHiJK'; var n,m,i:longint; procedure work(n,m:longint); var a,b,i:longint; str:ansistring; begin i:=1; a:=n; repeat b:=a mod m; a:=a div m; if b<0 then begin b:=b-m; inc(a); end; str:=d[b]+str; until a=0; writeln(n,'=',str,'(','base',m,')'); end;{end work} begin while not(eof) do begin readln(n,m); work(n,m); end; KMP 算法(了解): var i,j:longint; p:array[0..maxlongint]of longint; a,b:ansistring; begin readln(a); readln(b);
//--自匹配 预处理-j:=0; for i:=2 to length(b) do begin while(j>0)and(b[j+1]<>b[i])do j:=p[j]; if b[j+1]=b[i]then inc(j); p[i]:=j; end; //--匹配-j:=0;
第 51 页

NOIP 复习手册                                                         

崔晨

莒县一中

for i:=1 to length(a)do begin while(j>0)and(b[j+1]<>a[i])do j:=p[j]; if b[j+1]=a[i]then inc(j); if j=length(b)then begin write(j-length(b)+1,' '); j:=p[j]; end; end; end. 全排列与组合的生成

1)排列的生成:(1..n) procedure solve(dep:integer); var i:integer; begin if dep=n+1 then begin writeln(s);exit; end; for i:=1 to n do if not used then begin s:=s+chr(i+ord('0'));used:=true; solve(dep+1); s:=copy(s,1,length(s)-1); used:=false; end; end; 2)组合的生成(1..n中选取k个数的所有方案) procedure solve(dep,pre:integer); var i:integer; begin if dep=k+1 then begin writeln(s);exit;end; for i:=1 to n do if (not used) and (i>pre) then begin s:=s+chr(i+ord('0'));used:=true; solve(dep+1,i); s:=copy(s,1,length(s)-1); used:=false; end; end;

第 52 页

NOIP 复习手册                                                         

崔晨

莒县一中

六、后记?
由于假期时间仓促,而且本人能力有限,因此 DP 方面写的比较简略,这个手册难免有疏漏与不足之处。我将继续 完善这本手册,若各位大犇有什么建议,或者发现了什么错误,请尽快与我联系,联系方式将在下方给出。 因为我很弱,所以在整理这本手册时遇到了不少的麻烦,参考了一些很好的资料,下面给出。

参考资料(排名不分先后): 《NOIP 常用算法》 《全国青少年信息学竞赛培训教材 Pascal 语言程序设计》 《全国青少年信息学竞赛培训教材 复赛》 《信息学奥林匹克》 (山东省夏令营教材) 《实用算法分析与程序设计》 《全国信息学奥林匹克联赛 培训教程(二)》 《全国青少年奥林匹克联赛培训教材(中学高级本)》 《数据结构与程序实现》 《NOIP2002 复习资料》 《NOIP2012 最终征途》 《Matrix67 位运算讲稿》 山东省 2013NOIP 夏令营课件 山东省 2014NOIP 夏令营课件 王建德课件 百度百科 NOCOW

崔晨 2014 年 8 月 26 日 QQ:676219747 邮箱:onlycuichen@qq.com

第 53 页


相关文章:
NOIP复习手册.pdf
NOIP复习手册.pdf_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP复习手册.pdf_学科竞赛_高中教育_教育专区。NOIP 复习手册? ? ? ? ? ...
NOIP复习资料(C++版)
NOIP复习资料(C++版)_学科竞赛_高中教育_教育专区。noip 前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言...
noip初赛复习资料(全)
noip初赛复习资料(全)_学科竞赛_高中教育_教育专区。noip初赛复习资料(全) 分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中...
NOIP复习资料
int max,p; for (int i=1;i<=n;i++) { max=p=0; for (int j=1;j<=i;j++) { // p表示终点的位置 36 NOIP 复习资料(C++版) f[i][j] ...
NOIP复习
NOIP 复习排序问题 一:快速排序 program sort; var h,n:integer; a:array[1..100000] of Integer; procedure qsort(l,r: Integer); var i,j,mid,t: ...
noip复习资料
noip复习资料 隐藏>> 素数: function judge(p:longint):boolean; var i:longint; begin if i<2 then exit(false); if (i=2)or(i=3)then exit(true)...
NOIP复赛复习资料汇总
NOIP复赛复习资料汇总_IT认证_资格考试/认证_教育专区。noip复赛资料 NOIP 复赛知识总结 (一) Pascal 过程与函数调用 * abs(x):y 取 x 的绝对值,x 与 y ...
2016NOIP初赛复习资料
2016NOIP初赛复习资料_其它考试_资格考试/认证_教育专区。NOIP初赛复习资料 全国分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 ...
NOIP提高组复习资料(C++版)
前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言 有一天,我整理了 NOIP 的笔记,并收集了一些经典算法。...
NOIP复习资料
G.基数排序 思想:对每个元素按从低位到高位对每一位进行一 次排序 Noip 复习资料 五、高精度计算高精度数的定义: type hp=array[1..maxlen] of integer; 1...
更多相关标签: