沖刺N(yùn)OIP必掌握

1、沖刺N(yùn)OIP2014必掌握資料NOIP 2014，我一定能成功！注：*表示重要程度。 一、基本函數(shù) 絕對值函數(shù)abs(x) abs(-2.3); 2.3 取整函數(shù) int(x) int(123.567); 123.0 截尾函數(shù) trunc(x) trunc(1.4) 1 四舍五入函數(shù)round(x) round(9.456) 9 取小數(shù)函數(shù)frac(x)frac(-123.456) -0.456 求平方根函數(shù)sqrt(x)和平方函數(shù)sqr(x) sqrt(64)8 sqr(8) 64 隨機(jī)函數(shù)random：隨機(jī)產(chǎn)生一個01（不含1）之間的小數(shù)。 求字符串長度函數(shù)length length(as

2、df) 4 復(fù)制子串或求子串的函數(shù)copy copy(window,4,3) dow 插入子串或插入字符串insert 例如：若st2:=wins;執(zhí)行insert(dow,st2,4)后st2的值是windows 刪除子串delete 例如：若st=excel;執(zhí)行delete(st,4,2)后st的值是exc 字符串轉(zhuǎn)為數(shù)值val val(359,a,c1)執(zhí)行后將使變量a得到數(shù)值359（可參加四則運(yùn)算） val(124.32,b,c2)執(zhí)行后將使變量b得到數(shù)值124.32（可參加四則運(yùn)算） val(adb,c,c3)執(zhí)行后，c3將會出現(xiàn)錯誤值。 數(shù)值轉(zhuǎn)為字符串str str(128,s1

3、)執(zhí)行后字符串變量s1得到128 查找子串起始位置pos pos(in,windows)的值是2，pos(+,13+418=) 的值是3 字符完全串連+ Bei+jing+2008的值是Beijing2008 求字符的ASCII碼的函數(shù)。也稱序數(shù)函數(shù)。 ord(A)的值是65ord(Z)的值是90 求ASCII碼對應(yīng)的字符的函數(shù)。也稱字符函數(shù)chr(78)的值是N, chr(57)的值是9 求前趨pred的函數(shù) pred(D)的值是Cpred(65)的值是64 后繼succ的函數(shù) succ(D)的值是E ，succ(65)的值是66二、數(shù)學(xué)算法1.歐幾里得(最大公約數(shù))*function gc

4、d(a,b:longint):longint;begin if b=0 then exit(a) else gcd:=gcd(b,a mod b);end;2.最小公倍數(shù)*function lcm(a,b:longint):longint;begin lcm:=a*b div gcd(a,b);end;3.同余方程/同余 即： a mod b=n mod b,也可表達(dá)為 an(mod b);var a,b,n,i,j,k,d,e:longint; x,y:longint;function gcd(a,b:longint; var x,y:longint):longint; var t:long

5、int; begin if b=0 then begin x:=1;y:=0; exit(a); end; gcd:=gcd(b, a mod b,x,y); t:=x; x:=y; y:=t-(a div b)*x; end;procedure noans; begin writeln('按題目要求'); end;begin readln(a,b,n); d:=gcd(a,n,x,y); if n mod d<>0 then noans; e:=x*(b div d) mod n; while e<0 do begin e:=(e+(n div d) mod

6、 n; end; writeln(e);end./解同余方程組var a,b,x,y,k,n,m2,m1,a2,a1,g,t,c:longint; flag:boolean;function extended_gcd(a,b:longint;var x,y:longint):longint;var t:longint;begin if b=0 then begin x:=1; y:=0; exit(a); end; extended_gcd:=extended_gcd(b,a mod b,x,y); t:=x; x:=y; y:=t - (a div b)*y;end;begin read(n

7、); read(m1,a1); while n>1 do begin dec(n); read(m2,a2); g:=extended_gcd(m1,m2,x,y); c:=a2-a1; if c mod g<>0 then begin flag:=true;break;end; k:=m2 div g; t:=(c div g *x mod k+k) mod k; a1:=a1+t*m1; m1:=m1 div g *m2; end; if flag=false then write(a1) else write(-1);close(input);close(output)

8、;end.4.快速冪/求解ans=ab mod c;*function soso(a,b:longint):longint;var total:longint;begin total:=1; while b>0 do begin if odd(b) then total:=(total*a) mod c; b:=b shr 1; a:=(a*a) mod c; end; exit(total);end;5.篩選法求素數(shù)*Procedure get_prime(n:longint);var i,j:longint; begin for i:=2 to n do if not fi then

9、 begin inc(top); listtop:=i; J:=i+i; while j<=n do begin fj:=true; inc(j,i); end; end;end;6.分解質(zhì)因數(shù)/x=(p1i1)*(p2i2)*(pli3).*var x,p,i,t:longint;begin readln(x); p:=2;t:=trunc(sqrt(x); while (x<>1)and(p<=t)do begin if x mod p=0 then begin i:=0; while x mod p=0 do begin x:=x div p;inc(i); en

10、d; writeln(p,' ',i); end; inc(p);end; if x<>1 then writeln(x,' ',1);end.7.中國剩余定理中國剩余余定理： 應(yīng)用條件： 被除數(shù)互素 余數(shù)已知如：孫子算經(jīng)中的一個問題 今有物不知幾何，三三數(shù)至于二；五五數(shù)之余三；七七數(shù)之余二。問物幾何？ 答曰：二十三。標(biāo)準(zhǔn)程序如下：var n,m,i,j,k,l,x,z,y:longint; a,b,c:array1.10of longint;function gcd(x,y:longint):longint;begin if y=0 then ex

11、it(x) else gcd:=gcd(y,x mod y);end;procedure init;begin assign(input,'number.in');reset(input); assign(output,'number.out');rewrite(output);end;procedure guan;begin close(input); close(output);end;begin /init; readln(n); fillchar(c,sizeof(c),0); for i:=1 to n do readln(ai,bi); if n=1

12、 then begin writeln(a1+b1);halt;end; x:=a1; for i:=2 to n do begin z:=gcd(x,ai); x:=x*ai div z; end; for i:=1 to n do begin ci:=1; for j:=1 to n do begin if j=i then continue; if j<>i then begin z:=gcd(ci,aj); ci:=ci*aj div z; end; end; for z:= 1 to 100 do if (z*ci) mod ai=1) then begin ci:=z*

13、ci; break; end; end; for i :=1 to n do begin writeln('c',i,'',':=',ci); y:=ci*bi+y; end; writeln(x); y:=y mod x; writeln(y);end.8.高斯消元*procedure gao si xiao yuan;const zero=0.0000001; var i,j,n:longint; x:array0.maxnof double; a:array0.maxn,0.maxn+1of double; procedure xiao;

14、var i,j,k,l:longint; t:double; begin l:=1; for i:=1 to n do begin k:=l; for j:=l+1 to n do if abs(aj,i)-abs(ak,i)>zero then k:=j; if abs(ak,i)<=zero then continue; if k<>l then for j:=i to n+1 do swap(al,j,ak,j); for j:=l+1 to n do begin t:=-aj,i/al,i; for k:=i to n+1 do aj,k:=t*al,k+aj,

15、k; end; inc(l); end; end; procedure dai; var i,j,k:longint; begin k:=n; while (abs(ak,n)<=zero)and(k>0) do begin if abs(ak,n+1)>zero then begin writeln('no solution'); exit; end; dec(k); end; if k<n then begin writeln('untold solution'); for i:=n downto 1 do begin xi:=ai,

16、n+1/ai,i; if abs(xi)<=zero then xi:=0; for j:=1 to i-1 do aj,n+1:=aj,n+1-xi*aj,i; end; for i:=1 to n do if abs(xi)<=zero then write(0,' ') else write(xi:0:2,' '); writeln; end; begin readln(n); for i:=1 to n do for j:=1 to n+1 do read(ai,j); xiao; back; end;9.矩陣乘法設(shè)A是n行r列的矩陣,B是r

17、行m列的矩陣，則矩陣A，B可相乘矩陣A,B相乘后得到n行m列的S矩陣且滿足Si,j=(Ai,k*Bk,j),其中 1<=k<=r（應(yīng)用）若A= Fn-1 Fn-2 B=1 1 1 0 A*B=fn,fn-1用此法可以計算較大項(xiàng)斐波那契數(shù)列取模后的值。三、高精度運(yùn)算1.高精度加法*procedure plus (a,b:hp;var c:hp); var i,len:integer;begin fillchar(c,sizeof(c),0); if a0>b0 then len:=a0 else len:=b0; for i:=1 to len do begin inc(ci,

18、ai+bi); if ci>10 then begin dec(ci,10); inc(ci+1); end; end; if clen+1>0 then inc(len); c0:=len; end;2.高精度減法*procedure substract(a,b:hp;var c:hp); var i,len:integer;begin fillchar(c,sizeof(c),0); if a0>b0 then len:=a0 else len:=b0; for i:=1 to len do begin inc(ci,ai-bi); if ci<0 then beg

19、in inc(ci,10);dec(ci+1); end; end; while (len>1) and (clen=0) do dec(len); c0:=len; end; 3.高精度乘以低精度*procedure multiply(a:hp;b:longint;var c:hp);var i,len:integer;begin fillchar(c,sizeof(c),0); len:=a0; for i:=1 to len do begin inc(ci,ai*b); inc(ci+1,(ai*b) div 10); ci:=ci mod 10; end; inc(len); w

20、hile (clen>=10) do begin clen+1:=clen div 10; clen:=clen mod 10; inc(len); end; while (len>1) and (clen=0) do dec(len); c0:=len; end;4.高精度乘以高精度*procedure high_multiply(a,b:hp; var c:hpvar i,j,len:integer;begin fillchar(c,sizeof(c),0); for i:=1 to a0 do for j:=1 to b0 do begin inc(ci+j-1,ai*bj)

21、; inc(ci+j,ci+j-1 div 10); ci+j-1:=ci+j-1 mod 10; end; len:=a0+b0+1; while (len>1) and (clen=0) do dec(len); c0:=len; end; 5.高精度除以低精度function devide(a:hp;b:longint; var c:hp; var d:longint):hp;c:=a div b; d:= a mod b var i,len:integer;begin fillchar(c,sizeof(c),0); len:=a0; d:=0; for i:=len downt

22、o 1 do begin d:=d*10+ai; ci:=d div b; d:=d mod b; end; while (len>1) and (clen=0) then dec(len); c0:=len; exit(c);end;四、圖論1.spfa*var a,b,e:array1.1000 of longint; vis:array1.2000 of boolean; q,d,f:array1.2001 of longint;n,m,i,s,t:longint;procedure qsort(l,r:longint);var i,j,x,y:longint;begin i:=l

23、; j:=r; x:=a(l+r) shr 1; repeat while ai<x do inc(i); while aj>x do dec(j); if not(i>j) then begin y:=ai; ai:=aj; aj:=y; y:=bi; bi:=bj; bj:=y; y:=ei; ei:=ej; ej:=y; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j);end;procedure spfa(s:longint);var i,k,

24、l,t:longint;begin fillchar(vis,sizeof(vis),0); for i:=1 to n do di:=maxlongint; ds:=0; l:=0; t:=1; q1:=s; viss:=true; repeat l:=l mod 10000 +1; k:=ql; for i:=fk to fk+1-1 do if dk+ei<dbi then begin dbi:=dk+ei; if not visbi then begin t:=t mod 10000 +1; qt:=bi; visbi:=true; end; end; visk:=false;

25、until l=t;end;begin readln(n,m); for i:=1 to m do readln(ai,bi,ei); qsort(1,m); for i:=1 to m do if fai=0 then fai:=i; fn+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; readln(s,t); spfa(s); writeln(dt);gram spfa;By Zine.Chant type link=node; node=record x,y:longint;x是指向的節(jié)點(diǎn)，y是邊權(quán) next:lin

26、k; end; var i,n,m,x,y,z,start,head,tail:longint; f:array1.10000 of longint;當(dāng)前最優(yōu)值 a:array1.10000 of link; 每個點(diǎn)連出的邊的鏈表的頭 d:array1.1000000 of longint; 隊列 o:array1.10000 of boolean;檢驗(yàn)元素是否在未被處理的隊列中 r:link; procedure setup; begin assign(input,'spfa.in'); reset(input); assign(output,'spfa.out

27、9;); rewrite(output);end; procedure endit; begin close(input); close(output); end; begin setup; readln(n,m);點(diǎn)和邊的個數(shù) readln(start);起點(diǎn) for i:=1 to n do begin new(ai); fillchar(ai,sizeof(ai),0);要有初始化的好習(xí)慣 end; for i:=1 to m do begin readln(x,y,z); new(r); r.x:=y; r.y:=z; r.next:=ax.next; ax.next:=r; new(

28、r); r.x:=x; r.y:=z; r.next:=ay.next; ay.next:=r; end; 讀入邊 head:=0; tail:=1; d1:=start; for i:=1 to n do fi:=maxlongint; fstart:=0; fillchar(o,sizeof(o),false); while head<tail do begin inc(head); odhead:=false; 這三處是spfa的核心優(yōu)化 r:=adhead; while r.next<>nil do begin r:=r.next; if fdhead+r.y<

29、fr.x then begin fr.x:=fdhead+r.y; if or.x then continue; 這三處是spfa的核心優(yōu)化 inc(tail); dtail:=r.x; odtail:=true; 這三處是spfa的核心優(yōu)化 end; end; end; for i:=1 to n do writeln(i:5,':',fi:8); 輸出起點(diǎn)到每一個點(diǎn)的最短路徑 endit; end.2.dijkstra*var dist:Array1.1001,1.1001 of longint; n,m,i,j:longint; aa,bb,zz:longint; v:a

30、rray1.1001 of boolean;procedure dijkstra(s:longint);var i,j,min,k:longint;begin vs:=true;dists,s:=0; for i:=1 to n-1 do begin min:=10000000; for j:=1 to n do if (dists,j<min)and(not vj) then begin k:=j; min:=dists,j; end; vk:=true; for j:=1 to n do if distk,j>0 then if (dists,k+distk,j<dist

31、s,j)or(dists,j=0) then dists,j:=dists,k+distk,j; end;end;begin fillchar(dist,szieof(dist),127); readln(n,m); for i:=1 to m do begin readln(aa,bb,zz); distaa,bb:=zz; end; dijkstra(1); for i:=2 to n do writeln(dist1,i);end.3. kruskal *function find(v:longint):longint;begin if fv=v then exit(v) else be

32、gin fv:=find(fv);find:=fv;end;end;beginkuaipai(1,k);/把邊排序for i:=1 to n do fi:=i;total:=0;for i:=1 to k dobeginx:=find(ai); y:=find(bi); if x<>y then begin inc(total,wi); fx:=y; end; end; writeln(total);end.kruskal（MST）constmaxn=10000;maxm=100000;varu,v,w:array1. maxmof longint;fa:array1. maxno

33、f longint;n,m,x,y,i,left:longint;function getfa(i:longint):longint;beginif fai=0 then exit(i);fai:=getfa(fai);exit(fai);end;beginreadln(n,m);for i:=1 to m do readln(ui,vi,wi);sort(1,m);left:=n-1;for i:=1 to m dobeginx:=getfa(ui);y:=getfa(vi);if x=y then continue;fax:=y;writeln(ui,' ',vi,'

34、; ',wi);dec(left);if left=0 then break;end;end.最小樹形圖（有向圖的最小生成樹）var n,m,i,ans:longint; q:array0.102of longint; a:array0.102,0.102of longint; f:array0.102of boolean; vis:array0.102of boolean; procedure init; var i,j,k,l:longint; begin readln(n,m); for i:=1 to n do for j:=1 to n do ai,j:=maxlongint

35、; for i:=1 to m do begin readln(j,k,l); if l<aj,k then aj,k:=l; end; end; procedure dfs(x:longint); var j:longint; begin visx:=true; for j:=1 to n do if ax,j<maxlongint then if not(visj) then dfs(j); end; function min(a,b:longint):longint; begin if a<b then exit(a); exit(b); end; procedure

36、zhuliu; var i,j,k:longint; begin fillchar(f,sizeof(f),true); while true do begin for i:=2 to n do if fi then begin ai,i:=maxlongint; qi:=i; for j:=1 to n do if fj then if aj,i<aqi,i then qi:=j; end; i:=2; while i<=n do begin if not(fi) then begin inc(i); continue; end; j:=i; fillchar(vis,sizeo

37、f(vis),false); while (not(visj)and(j<>1) do begin visj:=true; j:=qj; end; if j=1 then begin inc(i); continue; end; i:=j; inc(ans,aqi,i); j:=qi; while j<>i do begin inc(ans,aqj,j); fj:=false; j:=qj; end; for j:=1 to n do if fj then if aj,i<maxlongint then dec(aj,i,aqi,i); j:=qi; while

38、j<>i do begin for k:=1 to n do if fk then begin if aj,k<maxlongint then ai,k:=min(ai,k,aj,k); if ak,j<maxlongint then ak,i:=min(ak,i,ak,j-aqj,j); end; j:=qj; end; break; end; if i>n then begin for j:=2 to n do if fj then inc(ans,aqj,j); break; end; end; end;begin assign(input,'rac

39、eline.in'); reset(input); assign(output,'raceline.out'); rewrite(output); fillchar(q,sizeof(q),0); fillchar(vis,sizeof(vis),false); init; dfs(1); for i:=1 to n do if not(visi) then begin writeln('impossible'); close(input); close(output); halt; end; ans:=0; zhuliu; writeln(ans);

40、close(input); close(output);end. 4.匈牙利算法function find(v:longint):boolean; /從v出發(fā)找匹配var i:longint;begin for i:=1 to m do /枚舉與v相連的點(diǎn)i if gv,i and (not yi) then /如果i與v相連且還未被訪問過 begin yi:=true; /標(biāo)記i已被訪問過 if (linki=0)or find(linki) then /如果i無匹配或原來的匹配點(diǎn)linki可以另找一個匹配 begin linki:=v; /讓v-i與i匹配 find:=true; /匹配成

41、功并返回 exit; end; end; find:=false; /匹配不成功end;5. Floyd*最短路：for k:=1 to n do for i:=1 to n dofor j:=1 to n do if di,j>di,k+dk,j then di,j:=di,k+dk,j;最小環(huán)：fillchar(f,sizeof(f),$3f div 2); fillchar(a,sizeof(a),$3f div 2); ans:=10000000; 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,fi,j+ai,k+ak,j); for i:=1 to n do for j:=1 to n do fi,j:=min(fi,j,fi,k+fk,j);end;無向帶權(quán)圖最小環(huán)program zuixiaohuan;var d,g:array0.100,0.100 of longint; n,m,x,y,w,i,j,k,ans:longint;function min(x,y:int64):int64; begin if x>y then exit(y) else exit(x); end;begin readln(n,m); f