OI基本算法总结.doc

学习文档 仅供参考
语言部分
一、常用函数与过程：
* abs(x):y
取x的绝对值，x与y可为整型或实型。
* frac(x):y
取x的小数部分，x与y均为实型。
* int(x):y
取x的整数部分，x与-1]);
writeln(d[n,k]);
*变形1：考虑顺序
d[ i, j] : = d [ i-k, j-1] (k=1..i)
*变形2：假设分解出来的每个数均有一个上限m
d[ i, j] : = d [ i-k, j-1] (k=1..m)
5．错位排列
d[1] = 0; d[2] = 1;
d[n] = (n-1) * (d[n-1] + d[n-2])
二、图论与计算几何
1．度边定理： sigema di = 2*E
2．.三角形面积
|x1 y1 1|
s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3
|x3 y3 1|
*海伦公式： 令p=(a+b+c)/2, 则S=sqrt(p*(p-a)*(p-b)*(p-c));
学习文档 仅供参考
三、组合公式
1．长度为n的0-1串中最多含k个1的
例 长度为N (N<=31)的01串中1的个数小于等于L的串组成的集合中找出按大小排序后的第I个01串。
2给定序列入栈出栈后可形成的情况总数为C(n,2n) – C(n-1,2n)+1.
例 fjoi2000
在一个列车调度站中，2条轨道连接到2条侧轨处，形成2个铁路转轨站，如下列图所示。其中左边轨道为车皮入口，右边轨道为出口。编号为1，2，……，n的N个车皮从入口依次进入转轨站，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序a1,a2,……,an。
给定正整数N〔1<=n<=300〕，编程计算右边轨道最多可以得到多少个不同的车皮编序方案。
例如当n=3时，最多得到6组不同的编序方案。
四、数论公式
1．模取幂a^b mod n= (..(a mod b)*a) mod b)*a..) mod b;
2．n的约数的个数
假设n满足n=a1^n1 * a2^n2 * a3^n3 * ... * am^nm,则n约数的个数为
(n1+1)(n2+1)(n3+1)...(nm+1)
3．费马小定理
假设n为质数 p^n = p (mod n)
算法部分
一、数论算法
1．求两数的最大公约数
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
2．求两数的最小公倍数
function lcm(a,b:integer):integer;
begin
if a<b then swap(a,b);
lcm:=a;
while lcm mod b>0 do inc(lcm,a);
end;
3．素数的求法
：
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;
〔包含求50000以内的素数表〕：
学习文档 仅供参考
procedure getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i<50000 do begin
if p[i] then begin
j:=i*2;
while j<50000 do begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p[i] then begin
inc(l);pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begi