NOIP常用算法代码
NOIP常用算法代码
（Pascal）
1.数论算法
//1.1 最大公约数gcd function
gcd(a,b:longint):longint; begin
if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
//1.2 最小公倍数lcm function
lcm(a,b:longint):longint; begin
lcm:=a div gcd(a,b)*b; end;
//notice:要先除后乘，避免溢出//1.3.1 快速幂运算pow function
pow(x,n:longint):longint; 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;
//1.3.2 快速幂运算pow (mod P)
function
pow(x,n,P:longint):longint;ov erload;
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;
//1.3.3 快速幂非递归function
pow0(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; n:=n shr 1;
end;
exit(result);
end;
//1.4 朴素判断素数is_prime function
is_prime(x:longint):boolean; var i:longint;
begin
for i:=2 to round(sqrt(x)) do
if x mod i=0 then
exit(false);
if x<2 then exit(false) else exit(true);
end;
//1.5 素数的筛法procedure
get_prime(n:longint);//计算1-n之间的素数，存储在list数组中
var i,j:longint;
begin
for i:=2 to n do if not f[i] then
begin
inc(top);
list[top]:=i;
j:=i+i;
while j<=n do
begin
f[j]:=true;
inc(j,i);
end;
end;
end;
//1.5.2 素数的筛选加强版program prime2; const maxn=40000;
maxm=100001;
var l,r,i,j:longint;
f:array[0..maxn] of boolean;
q:array[0..maxm] of boolean;
begin
fillchar(f,sizeof(f),false); for i:=2 to
round(sqrt(maxn)) do if not f[i] then
begin j:=i+i;
while j<=maxn do begin
f[j]:=true;
inc(j,i);
end;
end;
readln(l,r);
for i:=2 to
round(sqrt(maxn)) do if not f[i] then
begin
j:=l-l mod i;
if j begin q[j-l]:=true; inc(j,i); end; end; if l=1 then q[0]:=true; for i:=l to r do if not q[i-l] then writeln(i); end. //1.6 模运算下的除法(mod P) // a/b mod P = a*b^(P-2) mod P function divide(a,b,P:longint):longint; begin divide:=a*pow(b,P-2,P) mod P; end; //1.7求组合数 program zuheshu; var n,m,i,j,k:longint; c:array[0..100,0..100] of longint; function c1(n,m:longint):int64; var i,j:longint; ans:int64; begin ans:=1; for i:=n-m+1 to n do begin j:=i; ans:=int64(ans)*j div (j-n+m); end; exit(ans); end; function gcd(a,b:longint):longint; begin if b=0 then exit(a) else exit(gcd(b,a mod b)); end; function c2(n,m:longint):longint; var i,j,s,t,ans,x:longint; a,b:array[1..100] of longint; begin s:=0; for i:=m+1 to n do begin inc(s); a[s]:=i; end; for i:=1 to n-m do b[i]:=i; for i:=1 to n-m do begin if a[i]=1 then continue; for j:=1 to n-m do begin if b[j]=1 then continue; t:=gcd(a[i],b[j]); a[i]:=a[i] div t; b[j]:=b[j] div t; end; end; ans:=1; for i:=1 to n-m do ans:=ans*a[i]; exit(ans); end; begin readln(n,m); c[0,0]:=1; for i:=0 to n do c[i,0]:=1; for i:=1 to n do for j:=1 to n do c[i,j]:=c[i-1,j]+c[i-1,j-1]; writeln(c[n,m]); writeln(c1(n,m)); writeln(c2(n,m)); end. 2.高精度运算 const NUMLEN = 100; //高精度数长度 DLEN = 4; //压位长度 MM = 10000; //压位进制// ps.若有乘法建议设置DLEN=3，MM=1000 type bignum = array[0..NUMLEN]of longint; var a,b,c:bignum; s:ansistring; procedure print(var a:bignum); var i:longint; begin write(a[a[0]]); for i:=a[0]-1 downto 1 do begin if a[i]<1000 then write(0); //若MM=1000，注释掉本行 if a[i]<100 then write(0); if a[i]<10 then write(0); write(a[i]); end; writeln; end; operator + (var a,b:bignum)c:bignum; var i:longint; begin fillchar(c,sizeof(c),0); if a[0]>b[0] then c[0]:=a[0] else c[0]:=b[0]; for i:=1 to c[0] do begin inc(c[i],a[i]+b[i]); if c[i]>=MM then begin dec(c[i],MM); inc(c[i+1]); end; end; if c[c[0]+1]<>0 then inc(c[0]); end; operator - (var a,b:bignum)c:bignum; var i:longint; begin fillchar(c,sizeof(c),0); c[0]:=a[0]; for i:=1 to c[0] do begin inc(c[i],a[i]-b[i]); if c[i]<0 then begin inc(c[i],MM); dec(c[i+1]); end; end; while (c[0]>1) and (c[c[0]]=0) do dec(c[0]); end; operator * (var a,b:bignum)c:bignum;var i,j:longint; begin fillchar(c,sizeof(c),0); c[0]:=a[0]+b[0]-1; for i:=1 to a[0] do for j:=1 to b[0] do inc(c[i+j- 1],a[i]*b[j]); for i:=1 to c[0] do begin inc(c[i+1],c[i] div MM); c[i]:=c[i] mod MM; end; if c[c[0]+1]<>0 then inc(c[0]); end; procedure convert(var a:bignum;b:longint);overload; begin fillchar(a,sizeof(a),0); repeat inc(a[0]); a[a[0]]:=b mod MM; b:=b div MM; until b=0; end; procedure convert(var a:bignum;s:ansistring);overlo ad; var i,t,n:longint; begin n:=length(s); a[0]:=(n-1)div DLEN+1; for i:=1 to n do begin t:=(n-i)div DLEN+1; a[t]:=a[t]*10+ord(s[i])-ord('0'); end; end; begin readln(s); convert(a,s); readln(s); convert(b,s); c:=a*b; print(c); end. 3.排序 //3.1 排序算法 quicksort procedure sort(l,r:longint); var i,j,tmp,mid:longint; begin i:=l; j:=r; mid:=a[(l+r+r)div 3]; while i<=j do begin while a[i] inc(i); while a[j]>mid do dec(j); if i<=j then begin tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp; inc(i); dec(j); end; end; if i if l end; //3.2 双关键字快排procedure multi_sort(l,r:longint); var i,j,tmp,mid0,mid1:longint; begin i:=l; j:=r; mid0:=a[(l+r+r)div 3]; mid1:=b[(l+r+r)div 3]; while i<=j do begin while (a[i] while (a[j]>mid0) or ((a[j]=mid0)and(a[j]>mid1)) do dec(j); if i<=j then begin tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp; tmp:=b[i]; b[i]:=b[j]; b[j]:=tmp; inc(i); dec(j); end; end; if i if l //3.3插入排序 procedure insert_sort; var i,j:longint; begin for i:=2 to n do begin a[0]:=a[i]; j:=i-1; while a[0] begin a[j+1]:=a[j]; dec(j); end; a[j+1]:=a[0]; end; end; //3.4堆排 procedure heap_sort; procedure sift(i,m:longint); var k:integer; begin a[0]:=a[i]; k:=2*i; while k<=m do begin if (k if a[0] begin a[i]:=a[k]; i:=k; k:=i+i; end else break; end; a[i]:=a[0]; end; var i,j:longint; begin for i:=n div 2 downto 1 do sift(i,n); for i:=n downto 2 do begin a[0]:=a[i]; a[i]:=a[1]; a[1]:=a[0]; sift(1,i-1); end; end; //3.5归并排序 procedure merge_sort(var r,r1:arr; s,t:longint); procedure merge(r:arr; l,m,n:longint; var r2:arr); var i,j,k,p:longint; begin i:=l; j:=m+1; k:=l-1; while (i<=m)and(j<=n) do begin inc(k); if r[i]<=r[j] then begin r2[k]:=r[i]; inc(i); end else begin r2[k]:=r[j]; inc(j); end end; if i<=m then begin for p:=i to m do begin inc(k); r2[k]:=r[p]; end; end; if j<=n then begin for p:=j to n do begin inc(k); r2[k]:=r[p]; end; end; end; var k:longint; c:arr; begin if s=t then r1[s]:=r[s] else begin k:=(s+t) shr 1; merge_sort(r,c,s,k) ; merge_sort(r,c,k+ 1,t); merge(c,s,k,t,r1); end; end; 4.树状数组 //4.1.基本操作 function sum(i:longint):longint; var result:longint; begin result:=0; while i>0 do begin inc(result,a[i]); dec(i,i and -i); end; exit(result); end； procedure add(i,d:longint); begin while i<=MAXM do begin inc(a[i],d); inc(i,i and -i); end; end; //4.2应用举例 A．求逆序对 const MAXN=200000; var a,d,p,h:array[0..MAXN]of longint; n,t,i,j:longint; ans:int64; procedure sort(const l,r:longint); var i,j,tmp,mid:longint; begin i:=l; j:=r; mid:=d[(l+r+r)div 3]; repeat while d[i]>mid do inc(i); while d[j] if i<=j then begin tmp:=d[i]; d[i]:=d[j]; d[j]:=tmp; tmp:=p[i]; p[i]:=p[j]; p[j]:=tmp; inc(i); dec(j); end; until i>j; if i if l end; function sum(i:longint):longint; begin sum:=0; while i<>0 do begin inc(sum,a[i]); dec(i,i and -i); end; end; procedure add(i,d:longint); begin while i<=n do begin inc(a[i],d); inc(i,i and -i); end; end; begin assign(input,'B.in'); reset(input); assign(output,'B.out'); rewrite(output); readln(n); for i:=1 to n do begin readln(d[i]); p[i]:=i; end; sort(1,n); t:=1; h[p[1]]:=t; for i:=2 to n do begin if d[i]<>d[i-1] then inc(t); h[p[i]]:=t; end; ans:=0; for i:=1 to n do begin t:=sum(h[i]-1); ans:=ans+t; add(h[i],1); end; writeln(ans); close(input); close(output); end. B．求最长上升子序列 var data,a,f:array[1..MAXN]of longint; function getmax(i:longint):longint; begin getmax:=0; while i<>0 do begin if a[i]>getmax then getmax:=a[i]; dec(i,i and -i); end; end; procedure change(i,d:longint); begin while i<=n do begin if d>a[i] then a[i]:=d; inc(i,i and -i); end; end; begin for i:=1 to n do begin f[i]:=getmax(data[i]) +1; change(data[i],f[i]); end; end. 5.搜索 //5.1深搜（N皇后的对称优化及位运算） program Nhuanghou（对称优化）; const maxn=100; var n,n1,n2:integer; x:array[1..maxn] of integer; a:array[1..maxn] of boolean; b:array[2..maxn*2] of boolean; c:array[1-maxn..maxn-1] of boolean; s,t1,t2:boolean; procedure out(var s:boolean); var j:integer; begin if odd(n) then begin if not t1 then if x[1]>n div 2 then begin n1:=count; t1:=true; end; if t1 and not t2 then if x[1]>(n+1) div 2 then begin n2:=conut; t2:=true; end; if t1 and t2 then begin count:=n1+n2; s:=true; exit; end; end else begin if x[1]>n div 2 then begin count:=count*2; s:=true; exit; end; end; inc(count); for j:=1 to n do write(x[j],' '); end; procedure place(j:integer); var i:integer; begin for i:=1 to n do if not (a[i] or b[i+j] or c[i-j]) then begin x[j]:=i; a[i]:=true; b[i+j]:=true; c[i-j]:=true; if j out(s); if s then begin writeln (count); halt; end; end; a[i]:=false; b[i+j]:=false; c[i-j]:=false; end; end; begin readln(n); place(1); end. program checker;（位运算）var limite,n,t:longint; r:array[1..13]of integer; procedure print; var i:integer; begin for i:=1 to n-1 do write(r[i],' '); writeln(r[n]); end; procedure try(row,ld,rd,lv:longint); var p,pos:longint; begin if row while pos<>0 do begin p:=pos and -pos; pos:=pos-p; if t<=3 then r[lv]:=round(ln(p)/ln(2))+1; try(row or p,(ld+p)shl 1,(rd+p) shr 1,lv+1); end end else begin inc(t); if t<=3 then print; end; end; begin readln(n); limite:=(1 shl n)-1; try(0,0,0,1); writeln(t); end. //5.2双向广搜（字符串的变换） const maxn=100; type node=record s:string; depth:integer; //father:integer; end; var q:array[0..1,1..maxn]of node; head,tail:array[0..1]of integer; s1,s2:string; i,n:integer; procedure init; begin assign(input,'a1.in'); reset(input); readln(s1); readln(s2); n:=length(s1); close(input); end; procedure print(m:integer); begin if m=-1 then writeln('No answer') else writeln(m); halt; end; function find(t:integer; ss:string):boolean; var i:integer; begin for i:=1 to tail[t] do if ss=q[t,i].s then exit(true); exit(false); end; procedure checkmeet(t:integer); var i:integer; begin for i:=1 to tail[1-t] do if q[t,tail[t]].s=q[1-t,i].s then print(q[t,tail[t]].depth+ q[1-t,i].depth); end; procedure expand(t:integer); var i:integer; s,ss:string; step:integer; begin inc(head[t]); s:=q[t,head[t]].s; step:=q[t,head[t]].depth+1; for i:=1 to n-1 do if s[i]<>s[i+1] then begin ss:=s; ss[i]:=s[i+1]; ss[i+1]:=s[i]; if not find(t,ss) then begin inc(tail[t]); q[t,tail[t]].s:=ss; q[t,tail[t]].depth:=st ep; checkmeet(t); end; end; end; procedure doubfs; begin head[0]:=0; tail[0]:=1; q[0,1].s:=s1; head[1]:=0; tail[1]:=1; q[1,1].s:=s2; while (head[0] if tail[0] then expand(0) else expand(1); end; print(-1); end; Begin init; doubfs; End. 6.图论 //6.1SSSP（单源最短路径） 6.1.1Dijkstra（输出路径） Const maxn=100; var a:array[1..maxn,1..maxn] of integer; d:array[1..maxn] of integer; path:array[1..maxn] of integer; f:array[1..maxn] of boolean; n,ks,mb:integer; procedure init; var i,j,k:integer; begin assign(input,fin); reset(input); readln(n); for i:=1 to n do for j:=1 to n do a[i,j]:=maxint; for i:=1 to n do a[i,i]:=0; readln(ks,mb); while not seekeof do begin readln(i,j,k); a[i,j]:=k; a[j,i]:=k; end; close(input); end; procedure dijkstra; var i,j,k,min:integer; begin for i:=1 to n do begin d[i]:=a[ks,i]; f[i]:=false; path[i]:=ks; end; f[ks]:=true; for i:=2 to n do begin min:=maxint; for j:=1 to n do if (not f[j]) and (d[j] begin min:=d[j]; k:=j; end; f[k]:=true; for j:=1 to n do if (not f[j]) and (d[k]