NOIP复习资料终极版.doc

宜昌一中2009NOIP复习资料宜昌一中2009NOIP复习资料感谢唐弢（TT）、刘炟呈（CRL）、陈艺（衬衣）、猫（向缪丹妮）等众位大牛的倾力支持 特别感谢袁逸铭（yym）大牛的增添和指正预祝宜昌一中NOIP2009大捷！Quaty（高铭尉） 2009-11-19- 16 - 1、 高精度读入与输出用字符串读入数据，用数组存储数据。为了便于计算，可以用数组下标为0的元素记录该高精度数的长度。说明部分const maxn=250;type arr=array0.maxn of integer;var a,b:arr;读入部分procedure init(var a:arr);var str:string; i,j,l:integer;begin readln(str); fillchar(a,sizeof(a),0); a0:=length(str); for i:=1 to a0 doai:=ord(stra0-i+1)-ord(0);end;输出部分procedure print(a:arr);var i:integer;begin for i:=a0 downto 1 do write(ai); writeln;end;主程序部分begin init(a); init(b); print(a); print(b);end.高精度加法(1) Ai+Bi+进位得到和M；(2) M mod 10是结果的第i位数字；(3) M div 10 是该位向下一位的进位。procedure add(var a:arr;b:arr);var m,i,j:integer;begin if a00 then begin inc(a0); aa0:=m; end;end;高精度减法procedure minus(var a:arr;b:arr;var p:integer);a-bvar i,j,k,m:integer;temp:arr;begin if a0b0 then p:=1 else if a00) do dec(k); if akbk then p:=-1;end; if p0 thenbegin temp:=a; a:=b; b:=temp;end; for i:=1 to a0 dobegin ai:=ai-bi; if ai1) do dec(k); a0:=k;end;高精度减法（by yym大牛）if (length(n1)length(n2) or (length(n1)=length(n2) and (n1n2) then beginn:=n1;n1:=n2;n2:=n;write(-);end;lena:=length(n1);lenb:=length(n2); for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0); for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0); i:=1; while (i=lena) or(i1) do dec(lenc);高精度乘法（1） 高精度乘以单精度procedure multi1( var a:arr;x:integer);var i,m:integer;beginm:=0;for i:=1 to a0 do begininc(m,ai*x);ai:=m mod 10;m:=m div 10; end;while m0 do begin inc(a0); aa0:=m mod 10; m:=m div 10; end;end;（2）高精度乘以高精度procedure multi2(var a:arr;b:arr);var c:arr; i,j,k,l:integer;begin fillchar(c,sizeof(c),0); for i:=1 to a0 dofor j:=1 to b0 do inc(ci+j-1,ai*bj); for i:=1 to maxn-1 do begininc(ci+1,ci div 10);ci:=ci mod 10; end; k:=maxn; while (ck=0) and (k1) do dec(k); c0:=k; a:=c; end;2、 位运算运算符优先级Not1（高）*,/,div,mod,and,shl,shr2Xor,+,-,or3In,=,=,=,4（低）not 取反 not(1)=0; not(0)=1;and 同真则真 1 and 1=1; 0and 1=0; 0 and 0=0;or 有真则真 1 and 1=1; 0 and 1=1; 0 and 0=0;xor 异真同假 1 and 1=0; 0 and 1=1 0 and 0=0;shl a shl b就表示把a转为二进制后左移b位（在后面添b个0）。a shl b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。shr a shr b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。例如快排中mid选取可以定为 mid:=a(I+j)shr 1 以此替代 mid:=a(I+j)div 2常见应用：去掉x（的二进制的，下同）最后一位如：10011 1001x shr 1在x最后加一个0如：11101111010x shl 1在x最后加一个1如：1101101(x shl 1)+1把x最后一位变成1 如：11101111 ; 111111x or 1把最后一位变成0如：11111110 ; 100100 x or 1-1最后一位取反如：111110 ; 100101 x xor 1把右数第k位变成1如：10111111; 1111x or (1 shl (k-1)把右数第k位变成0如：11101100 ; 100100 x xor (1 shl (k-1)右数第k位取反如：111101;1100111101; x xor (1 shl (k-1)取x末k位如：11101101 (k=3)x and (1 shl k)-1)取右数第k位如：111011(k=3) x shr (k-1) and 1把末k位变成1如：110000 111111(k=4)x or (1 shl k)-1)末k位取反如：110111110000（k=3）x xor (1 shl k)-1)把右边连续的1变成0如：10101111010000x and (x+1)把右起第一个0变成1如：10101111011111 x or (x+1)把右边连续的0变成1如：10100001011111x or (x-1)取右边连续的1如：10111111 (x xor (x+1) shr 1去掉右起第一个1的左边如：11011 x and (x xor (x-1)3、 常见排序快速排序(从小到大，下同)procedure qsort(var data:arr;t,w:longint);var i,j,mid,a,b:longint;beginif w=t then exit;i:=t;j:=w;mid:=datarandom(w-t+1)+t;mid:=data(t+w) shr 1;repeat while dataimid do dec(j); if ij;if iw then qsort(data,i,w);if taj then begin a0:=aj; aj:=aj-1; aj-1:=a0; end;end;堆排序(by TT大牛)procedure swap(i,j:longint);/交换 var t:longint;begin t:=ai; ai:=aj; aj:=t;end;procedure heapdown(i:longint); var l,r:longint; m:longint;begin l:=i shl 1;l:=i*2;l是i的左儿子 r:=i shl 1+1;r:=(i*2)+1;r是i的右儿子 if (lai) then m:=l else m:=i; if (ram) then m:=r; if im then begin swap(i,m); heapdown(m); end;end;procedure heapup(i:longint); var f:longint;begin f:=i shr 1;f:=i div 2;f是i的父亲 if afai then begin swap(i,f); heapup(f); end;end;procedure buildheap;/建堆（大根堆） var i:longint;begin for i:=n shr 1 downto 1 do heapdown(i);end;堆排序(by yym大牛)procedure swap(i,j:longint);var t:longint;begint:=ai;ai:=aj;aj:=t;end;procedure build(i,m:longint); /建堆（小根堆）beginwhile i*2=m dobegin i:=i*2; if (iai) then inc(i); if (aiai div 2) then swap(i div 2,i) else break;end;end;procedure deal; /主程序beginfor i:=n div 2 downto 1 do build(i,n);for i:=n downto 2 do begin swap(1,i); build(1,i-1); end;end;4、 Pascal常见函数与过程函数copy(s,i,l)从字符串s中截取第I个字符开始后的长度为L的子串如：copy(abcdef,2,2)=bclength(s)求字符串s的长度如：length(edwsa)=5pos(s1,s2)如果s1是s2的子串 ，则返回s1的第一个字符在s2中的位置，若不是子串，则返回0如：pos(a,bcabca)=3upcase(ch)求字符ch的大写体如：upcase(a)=Ainc(i) 使i:=i+1;inc(i,b) 使i:=i+b;dec(i) 使i:=i-1; dec(i,b) 使i:=i-b; abs(x) 求x的绝对值chr(x) 求ACSII码x对应的字符ord(ch) 求字符ch对应的编号(注：ord(false)=0 ord(true)=1)sqr(x) 求x的平方sqrt(x) 求x的正根round(x) 求x的四舍五入trunc(x) 求x的整数部分 结果是integer型int(x) 求x的整数部分 结果是real型frac (x) 求x的小数部分 pred(x)求x的前导（pred(true)=false）succ(x) 求x的后继（succ(false)=true） odd(x) 判断x是否为奇数。如果是值为true，反之值为false. odd(2)=false odd(5)=trueeof布尔函数，用于判断文件结束否。eoln布尔函数，用于判断行结束否。过程detele(s,i,l)从字符串s中删除第I个字符开始后的长度为l的子串如：delete(abcdef,2,2)adefinsert(s1,s2,i)把s1插入到s2的第i个位置如：insert(12,abc,2)a12bcstr(x,s)把数值x化为数串s如：str(123,s) s=123val(s,x,i)把数串s转化为数值x,如果成功则i=0,不成功则i为无效字符的序数如：val(123,x,i) x=123 i=0fillchar(a,sizeof(a),x):x=00x=$7Fmaxlongintx=$F0-maxlongint5、 经典动规方程0/1背包一维动规版：for i:=1 to n do for j:=vmax downto vi dofj:=max(fj,fj-vi+wi);二维动规版：for i:=1 to n do for j:=0 to vmax dobegin fi,j:=fi-1,j; if j=vi then fi,j:=max(fi,j,fi-1,j-vi+wi);end;完全背包一维动规版：for i:=1 to n do for j:=0 to vmax do fj:=max(fj,fj-vi+wi);二维动规版：for i:=1 to n do for j:=0 to vmax dofi,j:=max(fi,j,fi-k,j-k*vi+k*wi);(0=k*vi1 bjbi)最长公共子序列以两个序列 X、Y 为例子：设有二维数组 fi,j 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：f11 = same(1,1);fi,j = maxfi-1j 1 + same(i,j),fi-1,j,fi,j1其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”，否则为“0”。6、 图论部分Prim（最小生成树 by CRL大牛）var cost:array1.100,1.100 of integer; mincost,closed:array1.100 of integer; min,k,i,j,n,tot:integer;begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(costi,j); if (ij) and (costi,j=0) then costi,j:=maxint; end; readln; end; for i:=1 to n do begin closedi:=1; mincosti:=cost1,i; end; for i:=2 to n do begin min:=maxint;k:=0; for j:=1 to n do if (mincostj0) and (mincostjcostk,j) and (mincostj0) then begin mincostj:=costk,j; closedj:=k; end; end; for i:=2 to n do begin inc(tot,costi,closedi); writeln(i,closedi); end; writeln(tot);end.Dijkstra（无负权边的单源最短路径 by CRL大牛） var s,e,n,i,j,min,mark:longint; source:array1.1000,1.1000 of integer; least,path:array1.1000 of longint; walked:array1.1000 of boolean; pa:array1.1000 of integer; k,go:integer;begin readln(n,s,e); fillchar(walked,sizeof(walked),false); for i:=1 to 1000 do leasti:=maxint; fillchar(path,sizeof(path),0); for i:=1 to n do begin for j:=1 to n do read(sourcei,j); if sourcei,j=0 then sourcei,j:=maxint; readln; end; for i:=1 to n do begin leasti:=sources,i; pathi:=s; end; walkeds:=true; for i:=1 to n-1 do begin min:=maxint; for j:=1 to n do if not(walkedj) and (leastjmin) then begin min:=leastj; mark:=j; end; walkedmark:=true; for j:=1 to n do if not(walkedj) and (sourcemark,j+leastmarkleastj) then begin leastj:=sourcemark,j+leastmark; pathj:=mark; end; end; if leaste=maxint then writeln(NO RESULT!) else writeln(leaste); if leastemaxint then begin fillchar(pa,sizeof(pa),0); k:=0; go:=pathe; while gos do begin inc(k); pak:=go; go:=pathgo; end; inc(k); pak:=s; for i:=k downto 1 do write(pai, ); write(e); end;end.SPFA（by CRL大牛，指针版）const maxmax=maxlongint div 2;type point=node; node=record next:point; data,n:longint; end;var i,j,n,s,t,x,y,c,head,now,tail,pi:longint; d:array1.10000 of longint; 队列 b:array1.1000 of point; 指针邻接表 dis:array1.1000 of longint; disi:i点到目标点的距离 v:array1.1000 of boolean; vi=true:i点当前正在队列里(注意不是i进过队,因为一个点有可能进几次队) path,pp:array1.1000 of longint; pathi=p:i的father是p; pp:倒过来的路径 p:point;begin assign(input,spfa.in); assign(output,spfa.out); reset(input); rewrite(output); readln(n,s,t); s:起始点; t:目标点 for i:=1 to n do bi:=nil; while not eof do begin readln(x,y,c); new(p); p.data:=c; p.n:=y; p.next:=bx; bx:=p; 上插入式吊桶法,避免循环去找队尾,或者再找个东西记对尾 new(p); p.data:=c; p.n:=x; p.next:=by; by:=p; 有向图不要上述部分,而且SPFA处理负权边的功能仅在有向图中能够体现出来 end; 初始化 head:=1; tail:=1; d1:=s; fillchar(v,sizeof(v),0); vs:=true; for i:=1 to n do disi:=maxmax; diss:=0; for i:=1 to n do pathi:=s; while head=tail do begin now:=dhead; 取队首点 p:=bnow; while pnil do begin if disp.ndisnow+p.data then begin 更新 disp.n:=disnow+p.data; pathp.n:=now; inc(tail); 加入队列 dtail:=p.n; vp.n:=true; 标记p.n已经在队里了 end; p:=p.next; end; inc(head); vnow:=false; 把队首元素踢出队列,这个初学者很容易忘! end; writeln(dist); pi:=0; i:=t; while is do 找路径(找出来是反的) begin inc(pi); pppi:=i; i:=pathi; end; inc(pi); pppi:=s; for i:=pi downto 再反回来 2 do write(ppi, ); writeln(pp1); 为避免评测机WS地把多余空格判错而必须采用的输出方法 close(input); close(output);end.SPFA（百度百科版）const maxp=100; 最大结点数var 变量定义p,c,s,t:longint; p,结点数;c,边数;s:起点;t:终点a,b:array1.maxp,0.maxp of longint; ax,y存x,y之间边的权;bx,c存与x相连的第c个边的另一个结点yd:array1.数组上界 of integer; 队列,保险情况下此处数组上界应至少为maxp的10倍v:array1.maxp of boolean; 是否入队的标记dist:array1.maxp of longint; 到起点的最短路head,tail:longint; 队首/队尾指针procedure init;vari,x,y,z:longint;beginread(p,c); for i := 1 to c dobeginreadln(x,y,z); x,y:一条边的两个结点;z:这条边的权值inc(bx,0); bx,bx,0 := y; ax,y := z; bx,0：以x为一个结点的边的条数inc(by,0); by,by,0 := x; ay,x := z;end;readln(s,t); 读入起点与终点end;procedure spfa(s:longint); SPFAvari,j,now,sum:longint;beginfillchar(d,sizeof(d),0);fillchar(v,sizeof(v),false);for j := 1 to p do dist j :=maxlongint;dists := 0; vs := true; d1 := s; 队列的初始状态,s为起点head := 1; tail := 1;while headdistnow+anow,bnow,i thenbegindistbnow,i:= distnow+anow,bnow,i; 修改最短路if not vbnow,i then 扩展结点入队begininc(tail);dtail := bnow,i;vbnow,i := true;end;end;vnow := false; 释放结点inc(head); 出队end;end;procedure print;beginwriteln(distt);end;begininit;spfa(s);print;end.7、 搜索部分1、广度优先搜索模版（by TT大牛，唐氏广搜08版）procedure BFS(k:longint);for j:=1 to n do 枚举每种变换情况变换所得状态为qif (j=1) and (i=0) then continue；if (not againq) and 满足条件then begin inc(team0); teamteam0:=q; stepteam0:=stepk+1; againq:=true; if q=aim then begin writeln(stepteam0); halt; end; end;main begin team0:=1; againteam1:=true; aim为目标状态 Team1初始状态 Team0做记录 k:=1; while k=team0 do begin BFS(k); inc(k); end;writeln(Impossible);end.8、 数论部分1求两数的最大公约数n （by 衬衣大牛）function gys(x,y:integer):integer; begin if y=0 then gys:=x else gys:=gys(y,x mod y); end; （方法2：扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和yfunction exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 thenbegin result:=a; x:=1; y:=0;endelsebeginresult:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end;end;（理论依据：gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1)）2求两数的最小公倍数n （by 衬衣大牛）Function gbs(a,b:integer):integer; begin If a0 do inc(gbs,a); End;（方法2：a*b div gcd(a,b);）3.判断一个数是否为质数,是质数则返回值1 否则为0： function prime (n: integer):boolean; var i: integer; begin for I:=2 to trunc(sqrt(n) do if n mod I=0 then begin prime:=false; exit; end; prime:=true; end;4.筛选法求素数readln(n);需要求2n之间所有的素数for j:=2 to n do aj:= true;全部清成真，表示目前是素数for j:=2 to n doif aj then当该数纪录是质数时开始筛选for i:=2 to n div j do aj*i := false;筛掉所有质数的倍数sum:=0;统计范围内有多少个质数for j:=2 to n doif aj then begin如果是质数就输出 write(j, ); Inc(sum); end;writeln(sum);输出总数5. 求前n个素数:program BasicMath_Prime;constmaxn=1000;varpnum,n:longint;p:array1.maxn of longint;function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum doif sqr(pi)=x then begin if x mod pi=0 then begin IsPrime:=false; exit; end;endelse begin IsPrime:=true; exit;end;IsPrime:=true;end;procedure main;var x:longint;beginpnum:=0;x:=1;while(pnumn) dobegininc(x);if IsPrime(x) then begin inc(pnum); ppnum:=x; end;end;end;procedure out;var i,t:integer;beginfor i:=1 to n dobeginwrite(pi:5);t:=t+1;if t mod 10=0 then writeln;end;end;beginreadln(n);main;out;end.6. 求不大于n的所有素数program sushu3;const maxn=10000;vari,k,n:integer;a:array1.maxn of integer;beginreadln(n);for i:=1 to n do ai:=i;a1:=0;i:=2;while in dobegink:=2*i;while k=n do begin ak:=0; k:=k+i; end;i:=i+1;while (ai=0) and (in) do i:=i+1;end;k:=0;for i:=1 to n doif ai0 then begin write(ai:5); k:=k+1; if k mod 10 =0 then writeln; endend.7. 将整数分解质因数的积program BasicMath_PolynomialFactors;constmaxp=1000;varpnum,n:longint;num,p:array1.maxp of longint;procedure main;var x:longint;beginfillchar(num,sizeof(num),0);fillchar(p,sizeof(p),0);pnum:=0;x:=1;while(n1) do begin inc(x); if n mod x=0 then begin inc(pnum); ppnum:=x; while(n mod x=0) do begin n:=n div x; inc(numpnum); end; end;end;end;procedure out;var j,i:integer;beginfor i:=1 to pnum dofor j:=1 to numi dowrite(pi:5);writeln;end;beginmain;out;end.8. 求方程ax+by=c的整数解 procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d0 thenbegin writeln(no answer); halt;end elsebegin x0:=x*(c div d); y0:=y*(c div d);end;end; 9. 方程ax+by=c整数解的应用 例1：有三个分别装有a升水、b升水和c升水的量筒(gcd(a，b)1，cba0),现c筒装满水，问能否在c筒个量出d升水(cd0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2不是一个筒被倒满就是另一个筒被倒光；3c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其 它限制。 程序如下: program mw;typenode=array0.1 of longint;vara,b,c:node; d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 then begin exgcd:=a;x:=1;y:=0; end else begin exgcd:=exgcd(b,a mod b,x,y); t:=x;x:=y;y:=t-(a div b)*y end;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d0 thenbegin wri