《上海交通大学ACM算法模板gai(共89页)》由会员分享，可在线阅读，更多相关《上海交通大学ACM算法模板gai(共89页)（90页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上ACM 算法模板集Contents一. 常用函数与STL二. 重要公式与定理1.Fibonacci Number2.Lucas Number3.Catalan Number4.Stirling Number(Second Kind)5.Bell Number6.Stirlings Approximation7.Sum of Reciprocal Approximation8.Young Tableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三. 大数模板，字符读入四. 数论算法1.Gre
2、atest Common Divisor最大公约数2.Prime素数判断3.Sieve Prime素数筛法4.Module Inverse模逆元 5.Extended Euclid扩展欧几里德算法6.Modular Linear Equation模线性方程(同余方程)7.Chinese Remainder Theorem中国余数定理(互素于非互素)8.Euler Function欧拉函数9.Farey总数9.Farey序列构造10. Miller_Rabbin素数测试，Pollard_rho因式分解五. 图论算法1.最小生成树(Kruscal算法)2.最小生成树(Prim算法)3.单源最短路径
3、(Bellman-ford算法)4.单源最短路径(Dijkstra算法)5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10. 最大团11. 二分图最大匹配(匈牙利算法)12. 带权二分图最优匹配(KM算法)13. 强连通分量(Kosaraju算法)14. 强连通分量(Gabow算法)15. 无向图割边割点和双连通分量16. 最小树形图O(N3)17. 最小树形图O(VE)六. 几何算法1.几何模板2.球面上两点最短距离3.三点求圆心坐标4. 三角形几个重要的点七. 专题讨论1.树状数组2.字典树3.后缀树4.线段树5.
4、并查集6.二叉堆7.逆序数(归并排序)8.树状DP9.欧拉路10. 八数码11. 高斯消元法12. 字符串匹配(KMP算法)13. 全排列,全组合14. 二维线段树15. 稳定婚姻匹配16. 后缀数组17. 左偏树18. 标准RMQ-ST19. 度限制最小生成树20. 最优比率生成树(0/1分数规划)21. 最小花费置换22. 区间K大数23. LCA - RMQ-ST24. LCA Tarjan25. 指数型母函数26. 指数型母函数（大数据）27. 单词前缀树（字典树+KMP）28. FFT（大数乘法）29. 二分图网络最大流最小割30. 混合图欧拉回路31. 无源汇上下界网络流32. 二
5、分图最小点权覆盖33. 带约束的轨道计数(Burnside引理)34. 三分法求函数波峰35. 单词计数，矩阵乘法36. 字符串和数值hash37. 滚动队列，前向星表示法38. 最小点基，最小权点基第一章 常用函数和STL一. 常用函数#includeintgetchar(void);/读取一个字符,一般用来去掉无用字符char*gets(char*str);/读取一行字符串#includevoid*malloc(size_tsize);/动态内存分配,开辟大小为size的空间voidqsort(void*buf,size_tnum,size_tsize,int(*compare)(cons
6、tvoid*,constvoid*);/快速排序Sample:intcompare_ints(constvoid*a,constvoid*b)int*arg1=(int*)a;int*arg2=(int*)b;if(*arg1*arg2)return-1;elseif(*arg1=*arg2)return0;elsereturn1;intarray=-2,99,0,-743,2,3,4;intarray_size=7;qsort(array,array_size,sizeof(int),compare_ints);#include/求反正弦,arg-1,1,返回值-pi/2,+pi/2doub
7、leasin(doublearg);/求正弦,arg为弧度,弧度=角度*Pi/180.0,返回值-1,1doublesin(doublearg);/求e的arg次方doubleexp(doublearg);/求num的对数,基数为edoublelog(doublenum);/求num的根doublesqrt(doublenum);/求base的exp次方doublepow(doublebase,doubleexp);#include/初始化内存,常用来初始化数组void*memset(void*buffer,intch,size_tcount);memset(the_array,0,sizeo
8、f(the_array);/printf是它的变形,常用来将数据格式化为字符串intsprintf(char*buffer,constchar*format,.);sprintf(s,%d%d,123,4567);/s=/scanf是它的变形,常用来从字符串中提取数据intsscanf(constchar*buffer,constchar*format,.);Sample:charresult100=24hello,str100;intnum;sprintf(result,%d%s,num,str);/num=24;str=hello;/字符串比较,返回值0代表str10代表str1str2i
9、ntstrcmp(constchar*str1,constchar*str2);二. 常用STL标准container概要vector大小可变的向量, 类似数组的用法, 容易实现删除list双向链表queue队列, empty(), front(), pop(), push()stack栈, empty(), top(), pop(), push()priority_queue 优先队列, empty(), top(), pop(), push()set集合map关联数组, 常用来作hash映射标准algorithm摘录for_each()对每一个元素都唤起（调用）一个函数find() 查找第
10、一个能与引数匹配的元素replace() 用新的值替换元素, O(N)copy() 复制（拷贝）元素, O(N)remove()移除元素reverse()倒置元素sort() 排序, O(N log(N)partial_sort() 部分排序binary_search()二分查找merge() 合并有序的序列, O(N)C+ String摘录copy() 从别的字符串拷贝empty() 判断字符串是否为空erase() 从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr() 取子字符串swap()交换字符串第二章 重要公
11、式与定理1. Fibonacci Number0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 Formula:2. Lucas Number1, 3, 4, 7, 11, 18, 29, 47, 76, 123.Formula:3. Catalan Number1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, Formula:Application:1) 将 n + 2 边形沿弦切割成 n个三角形的不同切割数Sample:n = 2;n = 3;2) n + 1个数相
12、乘, 给每两个元素加上括号的不同方法数Sample:n = 2; (1 (2 3),(1 2) 3)n = 3; (1 (2 (3 4), (1 (2 3) 4) , (1 2) (3 4), (1 (2 3) 4), (1 2) 3) 4)3) n 个节点的不同形状的二叉树数(严数据结构P.155)4) 从n * n 方格的左上角移动到右下角不升路径数Sample:n = 2;n = 3;4. Stirling Number(Second Kind)S(n, m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m 个无标号的盒子中, 要求无一为空, 其不同的方案数Formu
13、la:Special Cases:5. Bell Numbern 个元素集合所有的划分数Formula:6. Stirlings Approximation7. Sum of Reciprocal ApproximationEulerGamma = 0.1209;8. Young TableauYoung Tableau(杨式图表)是一个矩阵, 它满足条件:如果格子i, j没有元素, 则i+1, j也一定没有元素如果格子i, j有元素ai, j,则i+1, j要么没有元素, 要么ai+1, j ai, jYn代表n个数所组成的杨式图表的个数Formula:Sample:n = 3;9. 整数划分将整数n分成k份, 且每份不能为空, 任
