NOIP算法总结byNap.doc

NOIP算法总结
BY.W.X
吃了、还得睡
（一）数论
1.最大公约数，最小公倍数
2.筛法求素数
3. mod规律公式
4.排列组合数，错排
5.Catalan数
6.康拓展开
7负进制
8.中位数的应用
9.位运算
（二）高精度算法
1. 朴素加法减法
2. 亿进制加法减法

3. 乘法
4. 除法
5. 亿进制读入处理
6. 综合应用
(三)排序算法
1. 冒泡
2快排
3堆排
4归并
（四）DP
1. 概念
2. 解题步骤
3. 背包类DP
4. 线性DP
5. .区间动态规划
6. 坐标型动态规划（规则类DP）
7. 资源分配型动态规划
8. 树型动态规划
9. 状态压缩的动态规划
10. 动态规划的一般优化方法
（五）图论
1. Floyd-Warshall
2. Bellman-ford
3. SPFA
4. dijkstra
5. prim
6. kruskal
7. 欧拉回路
8. 哈密顿环
9. flood fill（求图的强连通分量）
10. 最小环问题（基于floyd）
11. Topological sort
12. 次短路
13. 次小生成树
（六）树
1.堆
2. 二叉排序树
3. 最优二叉树（哈夫曼树）
4.求树的后序遍历
5.并查集及应用
（七）分治
1.二分查找
2.二分逼近（注意精度问题）
3．二分答案
4．快排（见排序算法）
5.归并排序（见排序算法）
6.快速幂
（八）贪心
（九）搜索
（十）其它
1. 离散化
2. KMP
3. 字符串哈希
4. 常用字符串函数过程

(一)数论
1. 最大公约数，最小公倍数
function gcd(a,b:longint):longint;
begin
if b=0 then gcd:=a
else gcd:=gcd(b,a mod b);
end;
function jslcm(a,b:longint):longint;
begin
jslcm:=a div gcd(a,b)*b;(先div防215)
end;
2.筛法求素数
var
f:array[1..10000000] of boolean;
su:array[1..100000] of longint;
sj,n,i,j:longint;
begin
readln(sj);
fillchar(f,sizeof(f),true);
f[2]:=true;
for i:=2 to sj do
if f[i] then
begin
j:=i+i;
while jd.
3. mod规律公式
结合律 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p
((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p
分配律 ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p
4.排列组合数，错排
A(n,m)=n!/(n-m)!
  C(n,m):=n!/m!(n-m)!
错排 通项 f[n]:=n![1-1/1!+1/2!-1/3!……+(-1)^n*1/n!]
(利用容斥原理证明)
递推式 f[n]:=(n-1)*(f[n-1]+f[n-2]) (加法原理)
5.Catalan数
（1）公式
　　  h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
【计算过程中可用质因子表优化】
（2）应用 01串，出栈序列
　　   对于一个二进制的01串，共n+m位，满足n个1，m个0，且0<=n-m<=1，该串还满足从左向右1的个数永远大于0的个数。问：共有多少种排列方式？
此题可理解为进出栈问题，n个元素组成的队列，共有多少种进出栈的方式？
答案是满足卡特兰数的，即n个元素的进出站顺序为h（n）=c2n，n）/（n+1）；
为什么呢？
在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。
h（n）=c（2n，n）-c（2n，n-1）=c（2n，n）/（n+1）；
推广：当n<>m时，即1的个数为n，0的个数为m
排列方式的总数为：c（n+m,m）-c(n+m,m-1) =c(n+m,n-1)*(n-m+1)/m;
6.康拓展开
function ktzk(s:string):longint;
const
jc:array[1..8] of longint=(1,2,6,24,120,720,5040,40320);
var
i,j,num,tem,l:longint;
begin
l:=length(s);
num:=0;
for i:=1 to l-1 do
begin
tem:=0;
for j:=i+1 to l do
if s[i]>s[j] then inc(tem);
num:=num+tem*jc[8-i];
end;
ktzk:=num;
end;
7.负进制
const
ch:array[0..19]ofchar=('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J');
var n,r,x,y,z,nn,i:longint;
ans:array[1..2000]of longint;
begin
readln(n,r);
x:=0;
nn:=n;
repeat;
inc(x);
ans[x]:=n mod r;
n:=n div r;
if ans[x]<0 then
begin;
ans[x]:=ans[x]-r;
n:=n+1;
end;
until n=0;
write(nn,'=');
for i:=x downto 1 do write(ch[ans[i]]);
writeln('(base',r,')');
end.
8.中位数的应用(应用：士兵站队)
var
min,i,j,n,h,mid:longint;
x,y:array[1..10000] of longint;
procedure qs1(s,t:longint);
procedure qs2(s,t:longint);
begin
readln(n);
for i:=1 to n do
read(x[i],y[i]);
qs1(1,n);（对y排序）
min:=0;
mid:=y[n div 2+1];
for i:=1 to n do
min:=min+abs(y[i]-mid);
qs2(1,n); （对x排序）
for i:=1 to n do
x[i]:=x[i]-i+1;
qs2(1,n); （对x排序）
mid:=x[n div 2+1];
for i:=1 to n do
min:=min+abs(x[i]-mid);
writeln(min);
end.
9.位运算
（1） 基本操作
and
or 运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。
xor 0和1异或0都不变，异或1则取反。
例：对01串 0101010之类，改变某一位上的值，只需xor 某一位，如：对有数第三位取反，只需xor 4；
　　　　  对有数第三位和第二位同时取反，只需xor 6；
not；not运算的定义是把内存中的0和1全部取反。
.Shl  通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
shr;    我们也经常用shr 1来代替div 2
（2） 应用
计算二进制中的1的个数
    同样假设x是一个32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520那么最后x就变成了9，它表示1314520的二进制中有9个1。
x := (x and $55555555) + ((x shr 1) and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
    为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进行处理的。我们拿数字211来开刀。211的二进制为11010011。

+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |   <---原数
+---+---+---+---+---+---+
|  1 0  |  0 1  |  0 0  |  1 0  |   <---第一次运算后
+-------+-------+-------+-------+
|    0 0 1 1    |    0 0 1 0    |   <---第二次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |   <---第三次运算后，得数为5
+-------------------------------+

    整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100....，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。
例题：玩欺诈的小杉
描述 Description
是这样的，在小杉的面前有一个N行M列的棋盘，棋盘上有N*M个有黑白棋的棋子（一面为黑，一面为白），一开始都是白面朝上。
小杉可以对任意一个格子进行至多一次的操作（最多进行N*M个操作），该操作使得与该格同列的上下各2个格子以及与该格同列的左右各1个格子以及该格子本身翻面。
例如，对于一个5*5的棋盘，仅对第三行第三列的格子进行该操作，得到如下棋盘（0表示白面向上，1表示黑面向上）。

00100
00100
01110
00100
00100
对一个棋盘进行适当的操作，使得初始棋盘（都是白面朝上）变成已给出的目标棋盘的操作集合称作一个解法。
小杉的任务是对给出的目标棋盘求出所有解法的总数。
输入格式 Input Format
每组测试数据的
第一行有3个正整数，分别是N和M和T(1<=N,M<=20,1<=T<=5)
接下来T个目标棋盘，每个目标棋盘N行，每行M个整数之前没有空格且非0即1，表示目标棋盘（0表示白面朝上，1表示黑面朝上）
两个目标棋盘之间有一个空行。
特别地，对于30%的数据，有1<=N,M<=15
输出格式 Output Format
对每组数据输出T行，每行一个整数，表示能使初始棋盘达到目标棋盘的解法总数
var
z,m,n,t,ans,i,j,l,k:longint;
en:array[1..21] of longint;
s:string;
procedure find(x:longint);
var las,mak,i,ls:longint;
begin
las:=0; mak:=x;
for i:=1 to m do
begin
ls:=mak;
mak:=(mak xor en[i] xor (mak shl 1)xor(mak shl 2) xor(mak shr 1)xor(mak shr 2) xor las)and k;
las:=ls;
end;
if mak=0 then inc(ans);
end;
begin
readln(n,m,t);
for z:=1 to t do
begin
fillchar(en,sizeof(en),0);
for i:=1 to n do
begin
readln(s);
for j:=1 to m do
en[j]:=en[j]*2+ord(s[j])-48;
end;
ans:=0;
k:=1 shl n -1;
for i:=1 to k do find(i);
writeln(ans);
readln;
end;

end.
（二）高精度算法
1.朴素加法减法
var
a,b,c:array[1..10000] of longint;
jin,x,la,lb,lc,i:longint;
s1,s2:string;
procedure jiafa;
begin
if la>lb then lc:=la else lc:=lb;
jin:=0;
for i:=1 to lc do
begin
x:=a[i]+b[i]+jin;
c[i]:=x mod 10;
jin:=x div 10;
end;
if jin<>0 then begin inc(lc);c[lc]:=jin;end;
for i:=lc downto 1 do
write(c[i]);
writeln;
end;
procedure jianfa;
begin
fillchar(c,sizeof(c),0);
if la>lb then lc:=la else lc:=lb;
for i:=1 to lc do
begin
c[i]:=c[i]+a[i]-b[i];
if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end;
end;
while (c[lc]=0)and(lc>0) do dec(lc);
for i:=lc downto 1 do
write(c[i]);
writeln;
end;
begin
readln(s1);
readln(s2);
la:=length(s1);
lb:=length(s2);
for i:=1 to la do
a[i]:=ord(s1[la-i+1])-48;
for i:=1 to lb do
b[i]:=ord(s2[lb-i+1])-48;
jiafa;
if (lb>la)or((la=lb)and(s1有一个正整数，即要排列的骨牌个数。
【输出格式】
　　一个数，即不美观的排列个数。
【样例输入】
　　4
【样例输出】
　　6
【样例解释】
　　有四种不美观的排列。
　　黑黑黑黑，白白白白，黑黑黑白，白白白黑，黑白白白，白黑黑黑
【数据范围】
　　20％的数据，n≤60；
　　50％的数据，n≤600；
　　100％的数据，n≤10000
type
arr=array[1..1000] of longint;
var
lf,lg:array[0..10000] of longint;
f,g:array[0..10000] of arr;
er:arr;
i,j,m,n,ler:longint;
function gj1(a,b:arr;la,lb:longint;var lc:longint):arr;
var
c:arr;i,j,jin,x:longint;
begin
jin:=0;
fillchar(c,sizeof(c),0);
if la>lb then lc:=la else lc:=lb;
for i:=1 to lc do
begin
x:=a[i]+b[i]+jin;
c[i]:=x mod 100000000;
jin:=x div 100000000;
end;
if jin<>0 then begin inc(lc);c[lc]:=jin; end;
gj1:=c;
end;
function gj2(a,b:arr;la:longint;var lc:longint):arr;
var
i,j,x:longint;
begin
for i:=1 to la do
begin
x:=a[i]-b[i];
if x<0 then begin x:=x+100000000;dec(a[i+1]); end;
a[i]:=x;
end;
while (a[la]=0)and(la>0) do dec(la);
lc:=la;
gj2:=a;
end;
begin
readln(n);
f[0][1]:=0;g[0][1]:=2;
f[1][1]:=0;g[1][1]:=2;
f[2][1]:=0;g[2][1]:=4;
er[1]:=4; ler:=1;
for i:=0 to 2 do begin lf[i]:=1;lg[i]:=1;end;
for i:=3 to n do
begin
er:=gj1(er,er,ler,ler,ler);
f[i]:=gj1(f[i-1],f[i-1],lf[i-1],lf[i-1],lf[i]);
f[i]:=gj1(f[i],g[i-3],lf[i],lg[i-3],lf[i]);
g[i]:=gj2(er,f[i],ler,lg[i]);
end;
write(f[n][lf[n]]);
for i:=lf[n]-1 downto 1 do
if f[n][i]>=10000000 then write(f[n][i])
else if f[n][i]>=1000000 then write('0',f[n][i])
else if f[n][i]>=100000 then write('00',f[n][i])
else if f[n][i]>=10000 then write('000',f[n][i])
else if f[n][i]>=1000 then write('0000',f[n][i])
else if f[n][i]>=100 then write('00000',f[n][i])
else if f[n][i]>=10 then write('000000',f[n][i])
else write('0000000',f[n][i]);
writeln;
end.

3.乘法
procedure chengfa;
var c:array[1..200] of integer;
i,j,lc,x:integer;
cod:char;
begin
fillchar(c,sizeof(c),0);
cod:='+';
if ca<>cb then cod:='-';
for i:=1 to la do
for j:=1 to lb do
begin
c[i+j-1]:=c[i+j-1]+a[i]*b[j];
c[i+j]:=c[ij]+c[i+j-1] div 10;
c[i+j-1]:=c[i+j-1] mod 10;
end;
lc:=la+lb;
while (lc>1)and(c[lc]=0) do dec(lc);
if cod='-' then write(cod);
for i:=lc downto 1 do write(c[i]);
end;
4.除法
（1）
计算A/B的精确值，设A，B是一般整数，计算机可接受的数，精确小数后20位。不考虑四舍五入。
输入：两个数，n m
输出：n/m的结果。
Sample Input
3 2
Sample Output
3/2=1.50000000000000000000
var
a,b,i,j,l:integer;
c:array[0..21] of integer;
procedure prepare;
begin
l:=0;
c[0]:=a div b;
end;
procedure gchu;
begin
while l<20 do
begin
a:=(a-c[l]*b)*10;
c[l+1]:=a div b;
inc(l);
end;
end;
begin
readln(a,b);
write(a,'/',b,'=');
prepare;
gchu;
write(c[0],'.');
for i:=1 to 20 do
write(c[i]);
end.
（2）计算A/B的精确值，设A是高精度数（不超过100位），B是一般整数，计算机可接受的数，精确小数后100位。不考虑四舍五入。
输入：第一行被除数n,第二行除数m
输出：n/m的结果。
Sample Input
3
2
Sample Output
1.5
var
c:array[1..1000] of longint;
aa:string;
a:array[1..100] of longint;
b,i,j,la,l,beg,en:longint;
cho:boolean;
begin
cho:=false;
readln(aa);
readln(b);
la:=length(aa);
for i:=1 to la do
a[i]:=ord(aa[i])-48;
i:=1;
while i<=la do
begin
c[i]:=a[i] div b;
a[i+1]:=a[i+1]+(a[i]-c[i]*b)*10;
inc(i);
end;
dec(i);
if a[i+1]=0 then cho:=true;
l:=i+1;
while (l-i<=100) do
begin
c[l]:=a[i+1] div b;
a[i+1]:=(a[i+1]-c[l]*b)*10;
inc(l)
end;
beg:=1;
while c[beg]=0 do inc(beg);
en:=l-1;
while (c[en]=0)and(a[i+1]=0) do dec(en);
for j:=beg to i do
write(c[j]);
if cho then exit;
write('.');
for j:=i+1 to en do
write(c[j]);
end.
7. 亿进制读入
readln(s);
la:=length(s);
p:=0;
while la>0 do
begin
inc(p);
ls:=copy(s,la-7,8);
s:=copy(s,1,la-8);
la:=length(s);
val(ls,a[p]);
end;
6.应用
红豆玲珑骰（mark.pas/c/cpp）
【题目描述】
红豆玲珑骰一共六面，每一面上有+、-、*其中之一的符号。每当骰子落下后，hh4742的两条卷轴就会自动打开，上面分别显示有一个整数。
你所要做的工作，就是将这两个整数用骰子朝上的一面上显示的符号运算得出结果。
【输入格式】
第一行，骰子上显示的符号。
第二行，一个整数a。
第三行，一个整数b。
（-10^69<=a,b<=10^69）
【输出格式】
输出文件共一行，即计算得来的结果。
【输入样例】
*
-50
6
【输出样例】
-300
var
a,b,h:array[1..71] of integer;
ch,fu,sign:char;
ca,cb:boolean;
i,jm,n,la,lb,lh:longint;
s1,s2,hs:string;
procedure int;
begin
readln(fu);
readln(s1);
la:=length(s1);
ca:=true;
if s1[1]='-' then begin ca:=false; dec(la);delete(s1,1,1);end;
while (s1[1]='0')and(la>1) do
begin
dec(la);
delete(s1,1,1);
end;
for i:=la downto 1 do
a[la-i+1]:=ord(s1[i])-48;
readln(s2);
lb:=length(s2); cb:=true;
if s2[1]='-' then begin cb:=false; dec(lb);delete(s2,1,1);end;
while (s2[1]='0')and(lb>1) do
begin
dec(lb);
delete(s2,1,1);
end;
for i:=lb downto 1 do
b[lb-i+1]:=ord(s2[i])-48;
end;
procedure jiafa;
var x,w,jin,i:integer;
begin
if la>lb then w:=la else w:=lb;
jin:=0;
for i:=1 to w do
begin
x:=a[i]+b[i]+jin;
a[i]:=x mod 10;
jin:=x div 10;
end;
if jin<>0 then begin inc(w);a[w]:=jin; end;
la:=w;
if sign='-' then write(sign);
for i:=la downto 1 do write(a[i]);
writeln;
end;
procedure jianfa;
var jie,i,x,w:integer;
cod:char;
begin
cod:='+';
if (la0 then begin jie:=-1;x:=x+10;end;
a[i]:=x mod 10;
end;
if (la<>1)and(a[la]=0) then dec(la);
if cod='-' then write(cod);
for i:=la downto 1 do write(a[i]);
end;
procedure chengfa;
var c:array[1..142] of integer;
i,j,lc,x:integer;
cod:char;
begin
fillchar(c,sizeofc),0);
cod:='+';
if ca<>cb then cod:='-';
for i:=1 to la do
for j:=1 to lb do
begin
c[i+j-1]:=c[i+j-1]+a[i]*b[j];
c[i+j]:=c[i+j]+c[i+j-1] div 10;
c[i+j-1]:=c[i+j-1] mod 10;
end;
lc:=la+lb;
while (lc>1)and(c[lc]=0) do dec(lc);
if cod='-' then write(cod);
for i:=lc downto 1 do write(c[i]);
end;
begin
int;
sign:='+';
if (fu='+')and(ca)and(cb) then jiafa;
if (fu='+')and(not ca)and(not cb) then begin sign:='-';jiafa;end;
if (fu='+')and(ca)and(not cb) then jianfa;
if (fu='+')and(not ca)and(cb) then
begin h:=a;a:=b;b:=h;lh:la;la:=lb;lb:=lh;hs:=s1;s1:=s2;s2:=hs;jianfa; end;
if (fu='-')and(ca)and(cb) then jianfa;
if (fu='-')and(ca)and(not cb) then jiafa;
if (fu='-')and(not ca)and(not cb) then
begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;jianfa;end;
if (fu='-')and(not ca)and(cb) then begin sign:='-';jiafa;end;
if fu='*' then chengfa;
end.
（三）排序算法
1. 冒泡
var
temp,i,j,k,n:integer;
a:array[1..1000]of longint;
begin ;
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=1 to n-i do
if a[j]i:=1 to n do write(a[i],' ');
writeln;
end.
2. 快排
（1） 不稳定
procedure qs(s,t:longint);
var x,i,j,h:longint;
begin
i:=s;j:=t;
x:=a[(i+j)div 2];
repeat
while a[i]x do dec(j);
if i<=j then begin h:=a[i];a[i]:=a[j];a[j]:=h;
h:=b[i];b[i]:b[j];b[j]:=h;inc(i);dec(j);end;
until i>j;
if i