NOIP复习资料终极版.doc

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 do ai:=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 then begin temp:=a; a:=b; b:=temp; end; for i:=1 to a0 do begin ai:=ai-bi; if ai1) do dec(k); a0:=k;end;高精度乘法(1)高精度乘以单精度procedure multi1( var a:arr;x:integer);var i,m:integer;begin m:=0; for i:=1 to a0 do begin inc(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 do for j:=1 to b0 do inc(ci+j-1,ai*bj); for i:=1 to maxn-1 do begin inc(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.位运算not:取反 not(1)=0; not(0)=1;and:同真则真 1 and 1=1; 0 and 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(二进制)最后一位如:100111001x shr 1在x最后加一个0如:11101111010x shl 1在x最后加一个1如:1101101(x shl 1)+1把x最后一位变成1 如:11101111;111111x or 1把最后一位变成0如:11111110;100100x or 1-1最后一位取反如:111110;100101x xor 1把右数第k位变成1如:10111111;1111x or (1 shl (k-1)把右数第k位变成0如:11101100;100100x 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如:10101111011111x or (x+1)把右边连续的0变成1如:10100001011111x or (x-1)取右边连续的1如:10111111(x xor (x+1) shr 1 去掉右起第一个1的左边如:11011x and (x xor (x-1) 3.常见排序快速排序(从小到大,下同)procedure qsort(var data:arr;t,w:longint);var i,j,mid,a,b:longint;begin if w=t then exit; i:=t; j:=w; mid:=data(w+t) 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;堆排序1procedure swap(i,j:longint);/交换var t:longint;begin t:=ai; ai:=aj; aj:=t;end;procedure heapdown(i:longint);var l,r.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;堆排序2procedure swap(i,j:longint);var t:longint;begin t:=ai; ai:=aj; aj:=t;end;procedure build(i,m:longint);/建堆(小根堆)begin while i*2=m do begin i:=i*2; if (iai) then inc(i); if (aiai div 2) then swap(i div 2,i) else break; end;end;procedure deal;/主程序begin for 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 do fj:=max(fj,fj-vi+wi);二维动规版:for i:=1 to n do for j:=0 to vmax do begin 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 do fi,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,j-1其中,same(a,b)当X的第a位与Y的第b位完全相同时为1,否则为0.6.图论部分Prim(最小生成树)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(无负权边的单源最短路径)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(指针版)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 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);为避免评测机把多余空格判错而必须采用的输出方法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个边的另一个结点y d:array1.数组上界 of integer;队列,保险情况下此处数组上界应至少为maxp的10倍 v:array1.maxp of boolean;是否入队的标记dist:array1.maxp of longint;到起点的最短路 head,tail:longint;队首/队尾指针procedure init;var i,x,y,z:longint;begin read(p,c); for i := 1 to c dobegin readln(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);SPFAvar i,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 then begin distbnow,i:=distnow+anow,bnow,i;修改最短路 if not vbnow,i then begin扩展结点入队 inc(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.广度优先搜索模版procedure BFS(k:longint);begin for j:=1 to n do 枚举每种变换情况变换所得状态为q if (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;end; 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.求两数的最大公约数nfunction 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和y) function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;begin if b=0 thenbegin result:=a; x:=1; y:=0; end else begin result:=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.求两数的最小公倍数nFunction gbs(a,b:integer):integer; begin If a0 do inc(gbs,a); End;(方法2:a*b div gcd(a,b);)3.判断一个数是否为素数,是质数则返回值1否则为0: function ifprime (n:integer):boolean; var i:integer; begin for I:=2 to trunc(sqrt(n) do if n mod I=0 then begin ifprime:=false; exit; end; ifprime:=true; end;4.筛选法求素数procedure prime;begin 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);输出总数end; 5. 求前n个素数:const maxn=1000;var pnum,n:longint; p:array1.maxn of longint;function IsPrime(x:longint):boolean;var i:integer;begin for i:=1 to pnum doif sqr(pi)=x then begin if x mod pi=0 then begin IsPrime:=false; exit; end; end else begin IsPrime:=true; exit; end; IsPrime:=true;end;procedure main;var x:longint;begin pnum:=0; x:=1; while(pnumn) do begin inc(x); if IsPrime(x) then begin inc(pnum); ppnum:=x; end; end;end;procedure out;var i,t:integer;begin for i:=1 to n do begin write(pi:5);t:=t+1; if t mod 10=0 then writeln; end;end;begin readln(n); main; out;end.6.求不大于n的所有素数const maxn=10000;var i,k,n:integer; a:array1.maxn of integer;begin readln(n); for i:=1 to n do ai:=i; a1:=0; i:=2; while in do begin k:=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 thenwriteln; endend.7.将整数分解质因数的积const maxp=1000;var pnum,n:longint; num,p:array1.maxp of longint;procedure main;var x:longint;begin fillchar(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;begin for i:=1 to pnum do for j:=1 to numi do write(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;begin d:=exgcd(a,b,x,y); if c mod d0 then begin writeln(no answer); halt; end else begin 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.不是一个筒被倒满就是另一个筒被倒光；3.c筒仅起中转作用,而本身容积除了必须足够装下a简和b简的全部水外,别无其它限制. 程序如下: type node=array0.1 of longint;var a,b,c:node; d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:long