logo资料库

ACM_算法模板集史上最完整收藏版223页全免费版.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.90M 资料格式：pdf 举报 版权申诉
第1页 / 共223页
第2页 / 共223页
第3页 / 共223页
第4页 / 共223页
第5页 / 共223页
第6页 / 共223页
第7页 / 共223页
第8页 / 共223页
资料共223页，剩余部分请下载后查看
    ACM 算法模板集 免费模板~~~~~~~~~~~~ WisKey Standard CodeCodeCodeCode Library Standard ACMACMACMACM Standard Library Standard Library Library Huang Wei Software Engineering Computer and Software College Hangzhou Dianzi University October, 2008 - 1 -
    ACM 算法模板集 WisKey ACMACMACMACM 算法模板集 算法模板集 算法模板集 算法模板集 Contents Contents Contents Contents 一.... 常用函数与 STLSTLSTLSTL 二.... 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of Reciprocal Approximation 8. Young Tableau 9. 整数划分 10. 错排公式 11. 三角形内切圆半径公式 12. 三角形外接圆半径公式 13. 圆內接四边形面积公式 14. 基础数论公式 三.... 大数模板，字符读入 四.... 数论算法 1. Greatest 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. 单源最短路径(Bellman-ford 算法) - 2 -
    ACM 算法模板集 WisKey 4. 单源最短路径(Dijkstra 算法) 5. 全源最短路径(Folyd 算法) 6. 拓扑排序 7. 网络预流和最大流 8. 网络最小费用最大流 9. 网络最大流(高度标号预流推进) 10. 最大团 11. 最大匹配(Hungary，HopcroftKarp 算法) 12. 带权二分图最优匹配(KM 算法) 13. 强连通分量(Kosaraju 算法) 14. 强连通分量(Gabow 算法) 15. 无向图割边割点和双连通分量 16. 最小树形图 O(N^3) 17. 最小树形图 O(VE) 六.... 几何算法 1. 几何模板 2. 球面上两点最短距离 3. 三点求圆心坐标 4. 三角形几个重要的点 七.... 专题讨论 1. 树状数组 2. 字典树 3. 后缀树 4. 线段树 5. 并查集 6. 二叉堆 7. 逆序数(归并排序) 8. 树状 DP 9. 欧拉路 10. 八数码 11. 高斯消元法 12. 字符串匹配(KMP 算法) 13. 全排列,全组合 14. 二维线段树 15. 稳定婚姻匹配 16. 后缀数组 17. 左偏树 18. 标准 RMQ-ST 19. 度限制最小生成树 20. 最优比率生成树(0/1 分数规划) 21. 最小花费置换 22. 区间 K 大数 - 3 -
    ACM 算法模板集 WisKey 23. LCA - RMQ-ST 24. LCA – Tarjan 25. 指数型母函数 26. 指数型母函数(大数据) 27. AC 自动机(字典树+KMP) 28. FFT(大数乘法) 29. 二分图网络最大流最小割 30. 混合图欧拉回路 31. 无源汇上下界网络流 32. 二分图最小点权覆盖 33. 带约束的轨道计数(Burnside 引理) 34. 三分法求函数波峰 35. 单词计数，DFA 自动机，Trie 图(完全 AC 自动机) 36. 字符串和数值 hash 37. 滚动队列，前向星表示法 38. 最小点基，最小权点基 39. LCSubsequence O(N^2/logN) 40. 伸展树 41. Treap 42. 0/1 分数规划 K 约束 43. 表达式求值 44. 乘除法博弈,Wythoff 博弈 45. 状态压缩的积木型 DP 46. 解一般线性方程组(消元法) 47. 块状链表 48. Factor Oracle - 4 -
    ACM 算法模板集 WisKey 常用函数和 STLSTLSTLSTL 常用函数和 第一章第一章第一章第一章 常用函数和 常用函数和 一一一一.... 常用函数 常用函数 常用函数 常用函数 #include int getchar( void ); char *gets( char *str ); //读取一个字符, 一般用来去掉无用字符 //读取一行字符串 //快速排序 int* arg2 = (int*) b; //动态内存分配, 开辟大小为 size 的空间 #include void * malloc( size_t size ); void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); Sample: int compare_ints( const void* a, const void* b ) { int* arg1 = (int*) a; if( *arg1 < *arg2 ) return -1; else if( *arg1 == *arg2 ) return 0; else return 1; } int array[] = { -2, 99, 0, -743, 2, 3, 4 }; qsort( array, array_size, sizeof(int), compare_ints ); int array_size = 7; #include //求反正弦, arg∈[-1, 1], 返回值∈[-pi/2, +pi/2] double asin( double arg ); //求正弦, arg 为弧度, 弧度=角度*Pi/180.0, 返回值∈[-1, 1] double sin( double arg ); //求 e 的 arg 次方 double exp( double arg ); //求 num 的对数, 基数为 e double log( double num ); //求 num 的根 double sqrt( double num ); //求 base 的 exp 次方 double pow( double base, double exp ); #include //初始化内存, 常用来初始化数组 void* memset( void* buffer, int ch, size_t count ); memset( the_array, 0, sizeof(the_array) ); //printf 是它的变形, 常用来将数据格式化为字符串 int sprintf( char *buffer, const char *format, ... ); sprintf(s, "%d%d", 123, 4567); //s="1234567" - 5 -
    ACM 算法模板集 WisKey //scanf 是它的变形, 常用来从字符串中提取数据 int sscanf( const char *buffer, const char *format, ... ); Sample: char result[100]="24 hello", str[100]; sprintf( result, "%d %s", num,str );//num=24;str="hello" ; //字符串比较, 返回值<0 代表 str10 代表 str1>str2 int strcmp( const char *str1, const char *str2 ); int num; 二二二二.... 常用常用常用常用 STLSTLSTLSTL container [[[[标准 container container 概要]]]] container vector list queue stack priority_queue set map 大小可变的向量, 类似数组的用法, 容易实现删除 双向链表 队列, empty(), front(), pop(), push() 栈, empty(), top(), pop(), push() 优先队列, empty(), top(), pop(), push() 集合 关联数组, 常用来作 hash 映射 对每一个元素都唤起（调用）一个函数 查找第一个能与引数匹配的元素 用新的值替换元素, O(N) 复制（拷贝）元素, O(N) 移除元素 algorithm [[[[标准 algorithm algorithm 摘录]]]] algorithm for_each() find() replace() copy() remove() reverse() sort() partial_sort() binary_search() merge() 倒置元素 排序, O(N log(N)) 部分排序 二分查找 合并有序的序列, O(N) 从别的字符串拷贝 判断字符串是否为空 从字符串移除元素 String [C++[C++[C++[C++ String String 摘录]]]] String copy() empty() erase() find() insert() length() replace() substr() swap() 查找元素 插入元素 字符串长度 替换元素 取子字符串 交换字符串 - 6 -
    ACM 算法模板集 WisKey 第二章第二章第二章第二章 重要公式与定理 重要公式与定理 重要公式与定理 重要公式与定理 Fibonacci Number Fibonacci Number Fibonacci Number 1. Fibonacci Number 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 … Formula: Formula: Formula: Formula: F 0 F 1 F F F i i − 5) (1 − − 2 5 n i 1 − (1 = = = 1 1 5) + = 5 n 2 n 1 = + ⎛ ⎜ ⎜ ⎝ ⎤ ⎥ ⎥ ⎦ F n n ⎞ ⎟ ⎟ ⎠ 1 5 + 2 ⎡ ⎢ ⎢ ⎣ 2.2.2.2. Lucas Lucas Number Lucas Number Lucas Number Number 1, 3, 4, 7, 11, 18, 29, 47, 76, 123... Formula: Formula: Formula: Formula: 5 1 n n ⎞ ⎟ ⎟ ⎠ 5 1 + = ⎞ ⎟ ⎟ ⎠ nL − 2 + 2 ⎛ ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ⎝ 3.3.3.3. Catalan Catalan Number Catalan Number Catalan Number Number 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012… Formula: Formula: Formula: Formula: Cat n Cat n = C nn (2 , ) n 1 + n 1 − = ∑ Cat Cat * i i = 0 n i 1 − − Application: Application: Application: Application: 1) 将 n + 2 边形沿弦切割成 n 个三角形的不同切割数 Sample: n = 2; n = 3; 2) n + 1 个数相乘, 给每两个元素加上括号的不同方法数 Sample: - 7 -
    ACM 算法模板集 (1 ((2 3) 4)) , (1 (2 3)), ((1 2) 3) (1 (2 (3 4))), n = 2; n = 3; (((1 2) 3) 4) 3) n 个节点的不同形状的二叉树数(严《数据结构》P.155) 4) 从 n * n 方格的左上角移动到右下角不升路径数 Sample: ((1 2) (3 4)), WisKey ((1 (2 3)) 4), n = 2; n = 3; 4.4.4.4. Stirling Number(Second Stirling Kind) Stirling Number(Second Kind) Number(Second Kind) Stirling Number(Second Kind) S(n, m)表示含 n 个元素的集合划分为 m 个集合的情况数 或者是 n 个有标号的球放到 m 个无标号的盒子中, 要求无一为空, 其不同 的方案数 Formula: Formula: Formula: Formula: m = S nm , 0 ( S n m 1 1, − − ⎧ ⎨ ⎩ 0 || < m S + × n m ) ( n m 1, − n m ≥ > 1) C mi m i ) n − , ) × ( ( × = S nm , ( 1) i − 1 m ∑ m = ! i 0 Special Cases: Special Cases: Special Special Cases: Cases: S n ,0 S n ,1 S n ,2 = = = 1 − 0 1 2 n 1 − 1 (3 6 C n = 1 n ( ,2) 3 2 n − × + 3) = S n ,3 S nn 1 , − S = nn , 5.5.5.5. BellBellBellBell Number Number Number Number n 个元素集合所有的划分数 Formula: Formula: Formula: Formula: B n n = ∑ i = 0 S ni , - 8 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料