tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

冲刺NOIP必掌握


冲刺 NOIP2014 必掌握资料
NOIP 2014,我一定能成功! 注: ‘*’表示重要程度。

一、基本函数
⑴ ⑵ ⑶ ⑷ ⑸ ⑹ 绝对值函数 abs(x) abs(-2.3); { 2.3 } 取整函数 int(x) int(123.567); { 123.0 } 截尾函数 trunc(x) trunc(1.4) {1} 四舍五入

函数 round(x) round(9.456) { 9 } 取小数函数 frac(x) frac(-123.456) { -0.456 } 求平方根函数 sqrt(x)和平方函数 sqr(x) sqrt(64) {8} sqr(8) {64} ⑺ 随机函数 random:随机产生一个 0~1(不含 1)之间的小数。 ⑻ 求字符串长度函数 length length(‘asdf’) { 4 } ⑼ 复制子串或求子串的函数 copy copy(‘window’,4,3) { dow } ⑽ 插入子串或插入字符串 insert 例如:若 st2:=‘wins’;执行 insert(‘dow’,st2,4)后 st2 的值是‘windows’ ⑾ 删除子串 delete 例如:若 st=‘excel’;执行 delete(st,4,2)后 st 的值是‘exc’ ⑿ 字符串转为数值 val val(‘359’,a,c1)执行后将使变量 a 得到数值 359(可参加四则运算) val(‘124.32’,b,c2)执行后将使变量 b 得到数值 124.32(可参加四则运算) val(‘adb’,c,c3)执行后,c3 将会出现错误值。 ⒀ 数值转为字符串 str str(128,s1)执行后字符串变量 s1 得到‘128’ ⒁ 查找子串起始位置 pos pos(‘in’,‘windows’)的值是 2,pos(‘+’,‘13+418=’) 的值是 3 ⒂ 字符完全串连+ ‘Bei’+‘jing’+‘2008’的值是 Beijing2008 ⒃ 求字符的 ASCII 码的函数。也称序数函数。 ord(‘A’)的值是 65 ord(‘Z’)的值是 90 ⒄ 求 ASCII 码对应的字符的函数。也称字符函数 chr(78)的值是 N, chr(57)的值是 9 ⒅ 求前趋 pred 的函数 pred(‘D’)的值是 C pred(‘65’)的值是 64 ⒆ 后继 succ 的函数 succ(‘D’)的值是 E ,succ(‘65’)的值是 66

二、数学算法
1.欧几里得(最大公约数)

**

function gcd(a,b:longint):longint; begin if b=0 then exit(a) else gcd:=gcd(b,a mod b);

充满无不能的精神

坚定必成功的信念!

1

end; 2.最小公倍数

**

function lcm(a,b:longint):longint; begin lcm:=a*b div gcd(a,b); end; 3.同余方程 //同余 即: a mod b=n mod b,也可表达为 a≡n(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:longint; 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 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

充满无不能的精神

坚定必成功的信念!

2

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); 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); end. 4.快速幂//求解 ans=a^b 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.筛选法求素数

**
充满无不能的精神 坚定必成功的信念!
3

Procedure get_prime(n:longint); 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; 6.分解质因数//x=(p1^i1)*(p2^i2)*(pl^i3)....

**

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); end; writeln(p,' ',i); end; inc(p); end; if x<>1 then writeln(x,' ',1); end. 7.中国剩余定理 {中国剩余余定理: 应用条件: 被除数互素 余数已知 如: 孙子算经中的一个问题 今有物不知几何,三三数至于二;五五数之余三;七七数之余二。问物几何? 答曰:二十三。 标准程序如下:} var n,m,i,j,k,l,x,z,y:longint; a,b,c:array[1..10]of longint; function gcd(x,y:longint):longint;

充满无不能的精神

坚定必成功的信念!

4

begin if y=0 then exit(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(a[i],b[i]); if n=1 then begin writeln(a[1]+b[1]);halt;end; x:=a[1]; for i:=2 to n do begin z:=gcd(x,a[i]); x:=x*a[i] div z; end; for i:=1 to n do begin c[i]:=1; for j:=1 to n do begin if j=i then continue; if j<>i then begin z:=gcd(c[i],a[j]); c[i]:=c[i]*a[j] div z; end; end; for z:= 1 to 100 do if ((z*c[i]) mod a[i]=1) then begin c[i]:=z*c[i]; break; end; end; for i :=1 to n do begin

充满无不能的精神

坚定必成功的信念!

5

writeln('c[',i,']',':=',c[i]); y:=c[i]*b[i]+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:array[0..maxn]of double; a:array[0..maxn,0..maxn+1]of double; procedure xiao; 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(a[j,i])-abs(a[k,i])>zero then k:=j; if abs(a[k,i])<=zero then continue; if k<>l then for j:=i to n+1 do swap(a[l,j],a[k,j]); for j:=l+1 to n do begin t:=-a[j,i]/a[l,i]; for k:=i to n+1 do a[j,k]:=t*a[l,k]+a[j,k]; end; inc(l); end; end; procedure dai; var i,j,k:longint; begin k:=n; while (abs(a[k,n])<=zero)and(k>0) do begin if abs(a[k,n+1])>zero then begin writeln('no solution'); exit; end; dec(k); end; if k<n then begin writeln('untold solution');

充满无不能的精神

坚定必成功的信念!

6

for i:=n downto 1 do begin x[i]:=a[i,n+1]/a[i,i]; if abs(x[i])<=zero then x[i]:=0; for j:=1 to i-1 do a[j,n+1]:=a[j,n+1]-x[i]*a[j,i]; end; for i:=1 to n do if abs(x[i])<=zero then write(0,' ') else write(x[i]:0:2,' '); writeln; end; begin readln(n); for i:=1 to n do for j:=1 to n+1 do read(a[i,j]); xiao; back; end; 9.矩阵乘法 设 A 是 n 行 r 列的矩阵,B 是 r 行 m 列的矩阵,则矩阵 A,B 可相乘 矩阵 A,B 相乘后得到 n 行 m 列的 S 矩阵 且满足 S[i,j]=Σ (A[i,k]*B[k,j]),其中 1<=k<=r (应用) 若 A= { Fn-1 Fn-2 } B= 1 1 1 0 A*B={f[n],f[n-1]} 用此法可以计算较大项斐波那契数列取模后的值。

三、高精度运算
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; end;
7

充满无不能的精神

坚定必成功的信念!

2.高精度减法

*

procedure substract(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]<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; end; 3.高精度乘以低精度

**

procedure multiply(a:hp;b:longint;var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a[0]; for i:=1 to len do begin inc(c[i],a[i]*b); inc(c[i+1],(a[i]*b) div 10); c[i]:=c[i] mod 10; end; inc(len); while (c[len]>=10) do begin c[len+1]:=c[len] div 10; c[len]:=c[len] mod 10; inc(len); end; while (len>1) and (c[len]=0) do dec(len); c[0]:=len; end; 4.高精度乘以高精度

*

procedure high_multiply(a,b:hp; var c:hp} var i,j,len:integer; begin fillchar(c,sizeof(c),0); for i:=1 to a[0] do

充满无不能的精神

坚定必成功的信念!

8

for j:=1 to b[0] do begin inc(c[i+j-1],a[i]*b[j]); inc(c[i+j],c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10; end; len:=a[0]+b[0]+1; while (len>1) and (c[len]=0) do dec(len); c[0]:=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:=a[0]; d:=0; for i:=len downto 1 do begin d:=d*10+a[i]; c[i]:=d div b; d:=d mod b; end; while (len>1) and (c[len]=0) then dec(len); c[0]:=len; exit(c); end;

四、图论
1.spfa

**

var a,b,e:array[1..1000] of longint; vis:array[1..2000] of boolean; q,d,f:array[1..2001] of longint; n,m,i,s,t:longint; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(l+r) shr 1]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y;

充满无不能的精神

坚定必成功的信念!

9

y:=b[i]; b[i]:=b[j]; b[j]:=y; y:=e[i]; e[i]:=e[j]; e[j]:=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,l,t:longint; begin fill