NOIP算法总结 by Nap

《NOIP算法总结 by Nap》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、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归并（四）DP1.概念2.解题步骤3.背包类DP4.线性DP5..区间动态规划6.坐标型动态规划（规则类DP）7.资源分配型动态规划8.树型动态规划9.状态压缩的动态规划10

2、.动态规划的一般优化方法（五）图论1.Floyd-Warshall2.Bellman-ford3.SPFA4.dijkstra６９1.prim2.kruskal3.欧拉回路4.哈密顿环5.floodfill（求图的强连通分量）6.最小环问题（基于floyd）7.Topologicalsort8.次短路9.次小生成树（六）树1.堆2.二叉排序树3.最优二叉树（哈夫曼树）4.求树的后序遍历5.并查集及应用（七）分治1.二分查找2.二分逼近（注意精度问题）3．二分答案4．快排（见排序算法）5.归并排序

3、（见排序算法）6.快速幂（八）贪心（九）搜索（十）其它1.离散化2.KMP3.字符串哈希4.常用字符串函数过程６９(一)数论1.最大公约数，最小公倍数functiongcd(a,b:longint):longint;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;functionjslcm(a,b:longint):longint;beginjslcm:=adivgcd(a,b)*b;(先div防215)end;2.筛法求素数varf:array[1.

4、.10000000]ofboolean;su:array[1..100000]oflongint;sj,n,i,j:longint;beginreadln(sj);fillchar(f,sizeof(f),true);f[2]:=true;fori:=2tosjdoiff[i]thenbeginj:=i+i;whilej

5、3.mod规律公式结合律((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)modp4.排列组合数，错排A(n,m)=n!/(n-m)! C(n,m):=n!/m!(n-m)!错排通项f[n]:=n递推式f[n]:=(n-1)*(f[n-

6、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）=c（2n，n）/（n+1）；为什么呢？

7、在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.康拓展开functionktzk(s:string):longint;constjc:array[1..8]oflo

8、ngint=(1,2,6,24,120,720,5040,40320);vari,j,num,tem,l:longint;begin６９l:=length(s);num:=0;fori:=1tol-1dobegintem:=0;forj:=i+1toldoifs[i]>s[j]theninc(tem);num:=num+tem*jc[8-i];end;ktzk:=num;end;7.负进制constch:array[0..19]ofchar=('0','1','2','3','4','5','6