NOIP算法整理Word文件下载.doc
《NOIP算法整理Word文件下载.doc》由会员分享，可在线阅读，更多相关《NOIP算法整理Word文件下载.doc（65页珍藏版）》请在冰点文库上搜索。
回路问题 22
Euler回路 22
Hamilton回路 22
一笔画问题 22
图的遍历 25
DFS 25
BFS 25
最短路径 27
dijkstra算法 27
floyd算法 28
spfa算法 29
最小生成树 32
prim算法 32
Kruskal算法 33
topology排序 35
关键路径 36
利用拓扑排序 36
按照概念 37
次短路 39
次小生成树 39
匈牙利算法 39
博弈 40
取对称状态 40
取NIM值 41
分治 42
回溯 43
N皇后 43
HanoiTower 44
高精度计算 44
高精度加法 44
高精度减法 45
高精度乘法 47
高精度除法 48
高精度阶乘 50
高级数据结构 51
二叉树 51
并查集 53
树状数组 54
线段树 55
二叉搜索树 57
进制转换 61
1.将m进制数n转化成一个十进制数 61
2.将十进制数n转换成m进制数 62
后记 63
搜索
DFS
框架
proceduredfs（x）;
var
begin
if达到目标状态then输出结果并退出过程;
if满足剪枝条件thenexit;
fori:
=1to搜索宽度do
begin
备份现场；
（注意如果现场使用了全局变量，则需要使用局部变量备份）
dfs（参数+增量）；
恢复现场；
end;
优化
（1）最优化剪枝：
求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝
（2）可行性剪枝：
提前判断该状态是否能得到可行解，如不能则退出
（3）记忆化搜索：
对于已经搜索过的状态直接退出
（4）改变搜索顺序：
对于看起来希望更大的决策先进行搜索
（5）优化搜索策略
（6）预处理找到大体搜索翻译
（7）改写成IDA*算法
（8）卡时（注意现在联赛中禁止使用meml掐时）
BFS
初始化；
把初始布局存入
设首指针head=0；
尾指针tail:
=1；
repeat
inc（head），取出队列首记录为当前被扩展结点；
fori：
=1to规则数do{r是规则编号}
begin
if新空格位置合法then
begin
if新布局与队列中原有记录不重复
tail增1，并把新布局存入队尾；
if达到目标then输出并退出；
end；
end；
untilhead>
=tail；
{队列空}
判重的优化：
hash，二叉排序树
双向广搜或启发式搜索
改写成A*算法
二分优化
排序
冒泡排序
vara:
array[1..100]oflongint;
t,n,i,j:
longint;
proceduresort;
begin
fori:
=1ton-1do{与每个数都进行比较}
forj:
=1ton-ido
ifa[j]>
a[j+1]then
begin
t:
=a[j];
a[j]:
=a[j+1];
a[j+1]:
=t;
end;
选择排序
=1ton-1do
=1+itondo{大数沉小数浮}
a[i]then
=a[i];
a[i]:
插入排序
array[0..100]oflongint;
n,i,j,t:
fori:
=2tondo
forj:
=1to（i-1）do
begin
if（a[i]<
a[j]）then
t:
a[j]:
a[i]:
end;
end;
桶排序
vara,b:
r,i,j,t,k,n:
=0to100dob[i]:
=0;
{为B数组清零，小桶内容清零}
=1tondob[a[i]]:
=b[a[i]]+1;
{桶的序号就是那个要排序的东西；
出现一次，桶里得旗数加一}
=0to100do{扫描所有的桶}
ifb[i]<
>
0then{桶里有旗}
forj:
=1tob[i]dowrite（i,'
'
）;
{桶的序号就是那个数}
快速排序
n,i,h,g:
procedurekp（l,r:
longint）;
{变量不能与全局变量相同，否则会被抹去}
varb,m,i,j,t:
i:
=l;
j:
=r;
m:
=a[（l+r）div2];
{基准数最好从中间取}
repeat
whilea[j]>
mdodec（j）;
whilea[i]<
mdoinc（i）;
{两侧的哨兵移动}
ifi<
=jthen
{哨兵未碰面}{“=”利用repeat循环的性质，使repeat循环得以结束}
begin
t:
a[j]:
=a[i
a[i]:
{交换两个哨兵的值}
inc（j）;
dec（j）;
{哨兵继续运动}
end;
untili>
j;
ifj>
lthenkp（l,j）;
ifi<
rthenkp（i,r）;
{都是循环不结束后进行的动作}
read（n）;
=1tondoread（a[i]）;
kp（1,n）;
{“一”位置与“N”位置}
=1ton-1dowrite（a[i],'
write（a[n]）;
{防止多输出空格使程序结果出错}
end.
堆排序
n,i,b:
procedurejianshu（i:
while（（a[i]>
a[i*2]）or（a[i]>
a[i*2+1]））and（i<
=ndiv2）do
{当父亲数大于子女数时并且他有孩子时进行}
ifa[i*2]<
=a[i*2+1]{左儿子小于右儿子}
then
begin
b:
=a[i*2];
a[i*2]:
a[i]:
=b;
{左右儿子的值互换}
jianshu（i*2）;
{继续为左儿子建树}
end
else
=a[i*2+1];
a[i*2+1]:
jianshu（i*2+1）;
{上同，不过是为右儿子建树}
end;
end;
proceduretiao;
whilen<
0do
write（a[1]）;
a[1]:
=a[n];
n:
=n-1;
fori:
=（ndiv2）downto1do
jianshu（i）;
=1tondo
read（a[i]）;
jianshu（i）;
tiao;
数学定理
中国剩余定理
若有一些两两互质的整数m1,m2,…mn，则对任意的整数：
a1,a2,...an，以下联立同余方程组对模数m1,m2,…mn有公解：
康托展开
a[i]为当前未出现的元素中是排在第几个（从0开始）
把一个整数X展开成如下形式：
X=a[n]*（n-1）!
+a[n-1]*（n-2）!
+...+a[i]*（i-1）!
+...+a[2]*1!
+a[1]*0!
其中a[i]为当前未出现的元素中是排在第几个（从0开始），并且0<
=a[i]<
i（1<
=i<
=n）
错排通项
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。
f[1]=0;
f[2]=1;
f[n]=（n-1）（f[n-2）+f[n-1]）
f[n]:
=n!
[1-1/1!
+1/2!
-1/3!
……+（-1）^n*1/n!
]
f[n]=（n!
/e+0.5），其中e是自然对数的底，[x]为x的整数部分。
费马大定理
•费马大定理，又被称为“费马最后的定理”，由法国数学家费马提出。
它断言当整数n>
2时，关于x,y,z的方程xn+yn=zn没有正整数解。
•被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·
怀尔斯证明。
费马小定理
假如a是一个整数，p是一个素数，那么ap≡a（modp）。
如果a不是p的倍数，这个定理也可以写成ap-1≡1（modp）。
----这个更加常用
逆元
由费马小定理：
假如p是质数，且gcd（a,p）=1，那么ap-1≡1（modp）
逆元：
如果ab≡1（modp），那么在模p意义下，a、b互为逆元。
所以，假如p是质数，且gcd（a,p）=1，那么a的逆元是ap-2
逆元的作用：
在模意义下进行除法。
乘a的逆元等同于除以a。
欧拉函数
在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。
此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。
若m,a为正整数，且m,a互素，（gcd（a,m）=1），则aφ（m）≡1，其中为φ（m）欧拉函数，modm为同余关系。
欧拉定理实际上是费马小定理的推广。
Stirling数
第一类s（p,k）的一个的组合学解释是：
将p个物体排成k个非空循环排列的方法数。
s（p,k）的递推公式：
s（p,k）=（p-1）*s（p-1,k）+s（p-1,k-1）
1<
=k<
=p-1
边界条件：
s（p,0）=0,p>
=1
s（p,p）=1
p>
=0
递推关系的说明：
考虑第p个物品，p可以单独构成一个非空循环排列，这样前p-1种物品构成k-1个非空循环排列，方法数为s（p-1,k-1）；
也可以前p-1种物品构成k个非空循环排列，而第p个物品插入第i个物品的左边，这有（p-1）*s（p-1,k）种方法。
第二类S（p,k）的一个组合学解释是：
将p个物体划分成k个非空的不可辨别的（可以理解为盒子没有编号）集合的方法数。
k!
S（p,k）是把p个人分进k间有差别（如：
被标有房号）的房间（无空房）的方法数。
S（p,k）的递推公式是：
S（p,k）=k*S（p-1,k）+S（p-1,k-1）
=
k<
S（p,p）=1
=0
S（p,0）=0,p>
=1
考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的不可辨别的集合，方法数为S（p-1,k-1）；
也可以前p-1种物品构成k个非空的不可辨别的集合，第p个物品放入任意一个中，这样有k*S（p-1,k）种方法。
PS：
第一类斯特林数和第二类斯特林数有相同的初始条件，但递推关系不同。
sapproximation
快速求阶乘，不推荐用于竞赛。
更加精确的近似公式为：
其中：
·
.
数论
LCM
//GCD
functiongcd（a,b:
longint）:
ifb=0thengcd:
=a
elsegcd:
=gcd（b,amodb）;
end;
//LCM
functionlcm（a,b:
ifa<
bthenswap（a,b）;
lcm:
=a;
whilelcmmodb>
0doinc（lcm,a）;
素数
//单个判断
functionprime（n:
longint）:
boolean;
varilongint;
fori:
=2totrunc（sqrt（n））do
ifnmodi=0thenexit（false）
exit（true）;
//筛法打表
proceduremain;
vari,j:
fillchar（f,sizeof（f）,true）;
f[0]:
=false;
f[1]:
fori:
=2totrunc（sqrt（maxn））do
iff[i]then
begin
j:
=2*i;
whilej<
=maxndo
f[j]:
inc（j,i）;
end;
end;
快速幂
{a^bmodn}
functionf（a,b,n:
int64）:
int64;
vart,y:
=1;
y:
whileb<
if（band1）=1thent:
=t*ymodn;
y:
=y*ymodn;
{这里用了一个很强大的技巧,y*y即求出了a^（2^（i-1））不知道这是什么的看原理}
=bshr1;
{去掉已经处理过的一位}
exit（t）;
模运算法则
（A+B）modC=（AmodC+BmodC）modC
（A-B）modC=（AmodC-BmodC）modC
（A*B）modC=（AmodC）*（BmodC）modC
（A/B）modC=?
?
结合律
（（a+b）modp+c）modp=（a+（b+c）modp）modp
（（a*b）modp*c）modp=（a*（b*c）modp）modp
分配律
（（a+b）modp×
c）modp=（（a×
c）modp+（b×
c）modp）modp
组合和全排列
排列A（n,m）（m是上标）=n!
/（n-m）!
=nx（n-1）x...xm
组合C（n,m）=n!
/m!
（n-m）!
=[nx（n-1）x...xm]/m!
阶乘
functionfac（n1:
varj,k:
k:
forj:
=1tondok:
=k*j;
fac:
=k;
约瑟夫环问题
递推公式，设有n个人（0,...,n-1），数m，则第i轮出局的人为f（i）=（f（i-1）+m-1）%（n-i+1）,f（0）=0;
例：
有M个猴子围成一圈，每个有一个编号，编号从1到M。
打算从中选出一个大王。
经过协商，决定选大王的规则如下：
从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。
要求：
从键盘输入M，N，编程计算哪一个编号的猴子成为大王。
array[1..1000]oflongint;
m,n,i,j,sum:
weizhi:
longint=0;
readln（m,n）;
=1tomdoa[i]:
=i;
sum:
=m;
repeat
weizhi:
=weizhi+1;
ifweizhi>
mthenweizhi:
=weizhi-m;
ifa[weizhi]<
0then
j:
=j+1;
ifj=nthen
a[weizhi]:
j:
sum:
=sum-1;
untilsum=1;
=1tomdoifa[i]<
0thenwrite（a[i]）;
Catalan数
h（n）=h（0）*h（n-1）+h
（1）*h（n-2）+...+h（n-1）h（0）（n>
=2）
h[0]:
h[1]:
=i-1;
k:
whilek<
ido
begin
h[i]:
=h[i]+h[k]*h[j];
dec（j）;
inc（k）;
end;
1.矩阵连乘：
P=a1×
a2×
a3×
……×
an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
（h（n-1）种）
2.一个栈（无穷大）的进栈序列为1，2，3，…，n，有多少个不同的出栈序列。
3.对于一个二进制的01串，共n+m位，满足n个1，m个0，且0<
=n-m<
=1，该串还满足从左向右1的个数永远大于0的个数。
问共有多少种排列方式。
4.在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。
求不同划分的方案数。
5.给定N个节点，能构成多少种不同的二叉树？
扩展欧几里德算法
若存在一组解x0,y0，满足b*x0+（amodb）*y0=d则取x=y0，y=x0-（adivb）*y0，有
ax+by=d这样,我们可以用类似辗转相除的迭代法求解。
functionextended-gcd（a,b:
varx,y:
integer）;
varx1,y1:
integer;
ifb=0thenbegin
extended-gcd:
x:
y:
endelsebegin
=extended-gcd（b,amodb,x1,y1）;
=y1;
y:
=x1-（adivb）*y1;
对自然数因子的计算
怎样求一个数有多少个因数？
对于一个已知的自然数，要求出它有多少个因数，可用下列方法：
首先将这个已知数分解质因数，将此数化成几个质数幂的连乘形式，然后把这些质数的指数分别加一，再相乘，求出
升级会员 