ACM最常用算法,算法讲解,ACM大赛无压力

A C M程序设计常用算法与数据结构参考ACM程序设计常用算法与数据结构参考Tomsdinary目录前言 (7)排序算法 (8)插入排序 (8)选择排序 (10)冒泡排序 (11)希尔排序 (12)随机化快速排序 (14)归并排序 (18)堆排序 (19)大整数处理 (22)包含头文件 (22)定义 (22)实现 (24)流输出 (24)流输入 (24)赋值 (25)转换函数 (26)规范化符号化 (26)带符号乘法 (27)无符号取模 (27)整数乘法 (28)整数加法 (30)带符号加法 (32)浮点乘法 (33)浮点加法 (35)带符号减法 (36)整数减法 (37)浮点减法 (40)带符号比较 (41)无符号比较 (42)无符号乘方 (43)带符号乘方 (43)使用方法 (44)高级数据结构 (44)普通二叉搜素树 (44)包含头文件 (44)定义 (44)实现 (47)删树 (50)插入元素到树 (50)复制树 (53)求树的高度 (56)删除元素 (57)使用方法 (59)基本线段树模式 (60)基本并查集模式 (62)散列实现的一种方式参考 (63)定义与实现 (63)使用方法 (72)堆 (72)包含头文件 (72)定义与实现 (73)使用方法 (75)图相关算法 (76)图的深度优先和广度优先算法举例 (76)无向图最小生成树的Kruskal算法举例 (78)无向图最小生成树的Prim算法举例 (80)有向图的单源最短路径Dijkstra算法举例 (82)有向图的多源最短路径Floyd算法举例 (84)拓扑排序举例 (85)AOE网的算法举例 (88)求图的一个中心算法举例 (92)求图的P个中心算法举例 (95)SPFA算法举例 (99)割顶和块的算法举例 (102)计算几何算法 (105)向量模 (105)向量点积 (105)向量叉积 (105)左右判断 (106)相交判断 (106)正规相交交点 (106)判断多边形凸 (107)任意多变形面积 (107)凸包问题的快包实现举例 (108)STL算法参考 (113)accumulate() (113)adjacent_difference() (113)adjacent_find() (114)binary_search() (114)copy() (115)copy_backward() (115)count() (116)count_if() (116)equal() (116)fill() (118)fill_n() (118)find() (118)find_if() (118)find_end() (119)find_first_of() (119)for_each() (120)generate() (120)generate_n() (120)includes() (121)inner_product() (121)inplace_merge() (122)iter_swap() (122)lexicographical_compare() (123)lower_bound() (124)max() (124)max_element() (125)min() (125)min_element() (125)merge() (126)mismatch() (126)next_permutation() (127)nnth_element() (127)partial_sort() (128)partial_sort_copy() (129)partial_sum() (129)prev_permutation() (130)random_shuffle() (130)remove() (131)remove_copy() (132)remove_if() (132)remove_copy_if() (132)replace() (133)replace_copy() (133)replace_if() (133)replace_copy_if() (133)reverse() (134)reverse_copy() (134)rotate() (134)rotate_copy() (135)search() (135)search_n() (135)set_difference() (136)set_symmetric_difference() (137)set_union() (138)sort() (138)stable_partition() (139)stable_sort() (139)swap() (140)swap_range() (140)transform() (140)unique() (141)unique_copy() (142)upper_bound() (142)make_heap() (143)pop_heap() (143)push_heap() (144)sort_heap() (144)字符串处理 (145)KMP算法举例 (145)C++语言可用头文件 (147)<algorithm> (147)<bitset> (147)<complex> (147)<deque> (147)<exception> (147)<fstream> (147)<functional> (147)<iomanip> (148)<ios> (148)<iosfwd> (148)<iostream> (148)<iso646.h> (148)<istream> (148)<iterator> (148)<limits> (149)<list> (149)<locale> (149)<map> (149)<memory> (149)<new> (149)<numeric> (149)<ostream> (150)<queue> (150)<set> (150)<sstream> (150)<stdexcept> (150)<streambuf> (150)<string> (151)<strstream> (151)<utility> (151)<valarray> (151)<vector> (151)<cassert> (151)<cctype> (151)<cerrno> (151)<cfloat> (152)<ciso646> (152)<climits> (152)<clocale> (152)<cmath> (152)<csetjmp> (152)<csignal> (152)<cstdarg> (152)<cstddef> (152)<cstdio> (153)<cstdlib> (153)<cstring> (153)<ctime> (153)<cwchar> (153)<cwctype> (153)前言如今的程序设计已不再是个人英雄时代了，程序的设计和开发实施需要靠团队成员的积极配合和合作。

16个ACM经典算法介绍1.深度优先(DFS)DFS是一种递归的算法，用于遍历或图、树或状态空间。

它从起始节点开始遍历，然后沿着一条路径一直遍历到最深处，然后回溯到上一个节点，继续遍历其他路径。

2.广度优先(BFS)BFS也是一种遍历算法，但与DFS不同的是，它先遍历当前节点的所有相邻节点，然后再遍历相邻节点的相邻节点，以此类推。

BFS通常使用队列数据结构，先进先出。

3. 迪杰斯特拉算法 (Dijkstra's Algorithm)迪杰斯特拉算法用于求解带权图中的最短路径问题。

它采用贪心策略，每次选择当前节点到其他节点的最短路径，从起始节点开始逐步扩展，直到到达目标节点。

4. 弗洛伊德算法 (Floyd's Algorithm)弗洛伊德算法用于求解图中所有节点之间的最短路径。

它采用动态规划的思想，通过不断更新节点之间的最短路径，最终求得所有节点之间的最短路径。

5. 快速排序 (Quick Sort)快速排序是一种高效的排序算法，它通过选择一个基准元素，将待排序列表划分为左右两部分，左边部分都小于基准元素，右边部分都大于基准元素，然后对左右两部分分别递归地进行排序。

6. 归并排序 (Merge Sort)归并排序是一种稳定的排序算法，它将待排序列表分成长度相等的两部分，然后分别对这两部分进行排序，最后将排序好的两部分再合并成一个有序列表。

7. 堆排序 (Heap Sort)堆排序利用二叉堆数据结构实现，它将待排序列表看作是一颗完全二叉树，利用堆的性质对其进行排序。

8. Prim算法 (Prim's Algorithm)Prim算法用于求解最小生成树问题，它从一个节点开始，然后逐步扩展，每次选择当前节点到其他节点的最小权值边，直到生成一棵包含所有节点的树。

9. Kruskal算法 (Kruskal's Algorithm)Kruskal算法也用于求解最小生成树问题，它通过对所有边按权重从小到大进行排序，然后逐步加入图中，直到生成一棵包含所有节点的树。

ACM必须的算法1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。

：1. 二分图匹配（匈牙利），最小路径覆盖2. 网络流，最小费用流。

3. 线段树.4. 并查集。

5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp6.博弈类算法。

博弈树，二进制法等。

7.最大团，最大独立集。

8.判断点在多边形内。

9. 差分约束系统. 10. 双向广度搜索、A*算法，最小耗散优先.相关的知识图论：路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径Bellman-Ford Bellman-Ford的Yen-氏优化差分约束系统 Floyd 广义路径问题传递闭包极小极大距离 / 极大极小距离 EulerPath / Tour 圈套圈算法混合图的 Euler Path / TourHamilton Path / Tour 特殊图的Hamilton Path / Tour 构造生成树问题最小生成树第k小生成树最优比率生成树 0/1分数规划度限制生成树连通性问题强大的DFS算法无向图连通性割点割边二连通分支有向图连通性强连通分支 2-SAT最小点基有向无环图拓扑排序有向无环图与动态规划的关系二分图匹配问题一般图问题与二分图问题的转换思路最大匹配有向图的最小路径覆盖0 / 1矩阵的最小覆盖完备匹配最优匹配稳定婚姻网络流问题网络流模型的简单特征和与线性规划的关系最大流最小割定理最大流问题有上下界的最大流问题循环流最小费用最大流 / 最大费用最大流弦图的性质和判定组合数学解决组合数学问题时常用的思想逼近递推 / 动态规划概率问题Polya定理计算几何 / 解析几何计算几何的核心：叉积 / 面积解析几何的主力：复数基本形点直线，线段多边形凸多边形 / 凸包凸包算法的引进，卷包裹法Graham扫描法水平序的引进，共线凸包的补丁完美凸包算法相关判定两直线相交两线段相交点在任意多边形内的判定点在凸多边形内的判定经典问题最小外接圆近似O(n)的最小外接圆算法点集直径旋转卡壳，对踵点多边形的三角剖分数学 / 数论最大公约数Euclid算法扩展的Euclid算法同余方程 / 二元一次不定方程同余方程组线性方程组高斯消元法解mod 2域上的线性方程组整系数方程组的精确解法矩阵行列式的计算利用矩阵乘法快速计算递推关系分数分数树连分数逼近数论计算求N的约数个数求phi(N)求约数和快速数论变换……素数问题概率判素算法概率因子分解数据结构组织结构二叉堆左偏树二项树胜者树跳跃表样式图标斜堆reap统计结构树状数组虚二叉树线段树矩形面积并圆形面积并关系结构Hash表并查集路径压缩思想的应用 STL中的数据结构vectordequeset / map动态规划 / 记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列问题最长不下降子序列最长公共子序列最长公共不下降子序列一类NP问题的动态规划解法树型动态规划背包问题动态规划的优化四边形不等式函数的凸凹性状态设计规划方向线性规划常用思想二分最小表示法串KMPTrie结构后缀树/后缀数组 LCA/RMQ有限状态自动机理论排序选择/冒泡快速排序堆排序归并排序基数排序拓扑排序排序网络中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487,poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,po j2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj333 6,poj3315,poj2148,poj1263)初期:一.基本算法:(1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法. (4)递推.(5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,po j2240)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排)(poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,po j2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D+w(i,j)}(poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1 ]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)。

ACM竞赛中的数学方法初步(二)1. 引言ACM竞赛中的数学方法是竞赛中必不可少的一部分。

在竞赛中，数学方法可以帮助选手快速解决问题，提高竞赛成绩。

本文将介绍一些ACM竞赛中常用的数学方法。

2. 组合数学组合数学是ACM竞赛中最常用的数学方法之一。

组合数学包括排列组合、二项式定理、卡特兰数等。

在竞赛中，选手可以通过组合数学来求解排列组合问题，计算概率等。

例如，求解一个n个元素的集合中，取出m个元素的所有组合数，可以使用组合数公式C(n,m)=n!/m!(n-m)!来计算。

3. 数论数论是ACM竞赛中另一个重要的数学方法。

数论包括质数、最大公约数、最小公倍数、欧拉函数等。

在竞赛中，选手可以使用数论来解决一些特殊的问题，例如求解最大公约数、最小公倍数等。

例如，求解两个数a和b的最大公约数，可以使用辗转相除法来计算。

4. 矩阵矩阵是ACM竞赛中常用的数学工具。

在竞赛中，选手可以使用矩阵来解决一些复杂的问题，例如线性方程组、矩阵乘法等。

例如，求解一个n阶线性方程组Ax=b，可以使用矩阵的逆来计算。

5. 微积分微积分是ACM竞赛中较为高级的数学方法。

在竞赛中，选手可以使用微积分来解决一些复杂的问题，例如极值、最优化等。

例如，求解一个函数的最大值或最小值，可以使用微积分的极值定理来计算。

6. 几何几何是ACM竞赛中常用的数学方法之一。

在竞赛中，选手可以使用几何来解决一些几何问题，例如计算面积、周长等。

例如，求解一个三角形的面积，可以使用海伦公式来计算。

7. 结论ACM竞赛中的数学方法是竞赛中必不可少的一部分。

在竞赛中，选手可以使用组合数学、数论、矩阵、微积分、几何等数学方法来解决问题。

选手需要熟练掌握这些数学方法，才能在竞赛中取得好成绩。

做acm 需要学的算法转一个搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红, 发挥自己的长处,这才是重要的.1 训练阶段1.1 第一阶段：练经典常用算法。

下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来.1. 最短路(Floyd、Dijstra,BellmanFord)2. 最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换1.1 第二阶段：练习复杂一点，但也较常用的算法。

1. 二分图匹配（匈牙利），最小路径覆盖2. 网络流，最小费用流。

3. 线段树.4. 并查集。

5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp6.博弈类算法。

博弈树，二进制法等。

7.最大团，最大独立集。

8.判断点在多边形内。

9. 差分约束系统.10. 双向广度搜索、A*算法，最小耗散优先.2 相关的知识2.1 图论路径问题0/1边权最短路径BFS非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径Bellman-FordBellman-Ford的Yen-氏优化差分约束系统Floyd广义路径问题传递闭包极小极大距离/ 极大极小距离Euler Path / Tour圈套圈算法混合图的Euler Path / TourHamilton Path / Tour特殊图的Hamilton Path / Tour 构造生成树问题最小生成树第k小生成树最优比率生成树0/1分数规划度限制生成树连通性问题强大的DFS算法无向图连通性割点割边二连通分支有向图连通性强连通分支2-SAT最小点基有向无环图拓扑排序有向无环图与动态规划的关系二分图匹配问题一般图问题与二分图问题的转换思路最大匹配有向图的最小路径覆盖0 / 1矩阵的最小覆盖完备匹配最优匹配稳定婚姻网络流问题网络流模型的简单特征和与线性规划的关系最大流最小割定理最大流问题有上下界的最大流问题循环流最小费用最大流/ 最大费用最大流弦图的性质和判定2.2 组合数学解决组合数学问题时常用的思想逼近递推/ 动态规划概率问题Polya定理2.3 计算几何 / 解析几何计算几何的核心：叉积/ 面积解析几何的主力：复数基本形点直线，线段多边形凸多边形/ 凸包凸包算法的引进，卷包裹法Graham扫描法水平序的引进，共线凸包的补丁完美凸包算法相关判定两直线相交两线段相交点在任意多边形内的判定点在凸多边形内的判定经典问题最小外接圆近似O(n)的最小外接圆算法点集直径旋转卡壳，对踵点多边形的三角剖分2.4 数学 / 数论最大公约数Euclid算法扩展的Euclid算法同余方程/ 二元一次不定方程同余方程组线性方程组高斯消元法解mod 2域上的线性方程组整系数方程组的精确解法矩阵行列式的计算利用矩阵乘法快速计算递推关系分数分数树连分数逼近数论计算求N的约数个数求phi(N)求约数和快速数论变换……素数问题概率判素算法概率因子分解2.5 数据结构组织结构二叉堆左偏树二项树胜者树跳跃表样式图标斜堆reap统计结构树状数组虚二叉树线段树矩形面积并圆形面积并关系结构Hash表并查集路径压缩思想的应用STL中的数据结构vectordequeset / map2.6 动态规划 / 记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列问题最长不下降子序列最长公共子序列最长公共不下降子序列一类NP问题的动态规划解法树型动态规划背包问题动态规划的优化四边形不等式函数的凸凹性状态设计规划方向2.7 线性规划3 常用思想二分最小表示法串KMP Trie结构后缀树/后缀数组LCA/RMQ有限状态自动机理论排序选择/冒泡快速排序堆排序归并排序基数排序拓扑排序排序网络4 Poj（就是传说中的很好很有层次感）4.1 初级:一.基本算法:(1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法. (4)递推.(5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)拓扑排序(poj1094)(5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串(poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584)(4)凸包. (poj2187,poj1113)4.2 中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化(poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)4.3 高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.(poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,p oj1263)。

ACM竞赛知识点简介ACM竞赛是指由国际大学生程序设计竞赛（ACM-ICPC）组织的一系列编程比赛。

ACM竞赛旨在培养学生的计算机科学和编程能力，提高解决实际问题的能力和团队合作精神。

本文将介绍ACM竞赛的基本知识点和技巧，帮助读者更好地了解和参与这一竞赛。

知识点1. 数据结构在ACM竞赛中，数据结构是解决问题的关键。

以下是一些常用的数据结构：•数组：用于存储一组相同类型的数据。

•链表：用于存储和操作具有相同数据类型的元素。

•栈：一种后进先出（LIFO）的数据结构。

•队列：一种先进先出（FIFO）的数据结构。

•树：一种非线性的数据结构，由节点和边组成。

•图：一种由节点和边组成的数据结构，用于表示各种关系。

2. 算法ACM竞赛中常用的算法包括：•排序算法：如快速排序、归并排序、堆排序等，用于将数据按照一定的规则进行排序。

•查找算法：如二分查找、哈希表等，用于在数据中查找指定的元素。

•图算法：如深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法等，用于解决图相关的问题。

•动态规划：一种将复杂问题分解为简单子问题的方法，用于解决多阶段决策问题。

•贪心算法：一种每一步都选择当前最优解的方法，用于解决优化问题。

3. 数学数学在ACM竞赛中扮演着重要的角色。

以下是一些常用的数学知识点：•组合数学：包括排列组合、二项式定理、卡特兰数等，用于计算对象的排列和组合方式。

•数论：包括素数、最大公约数、最小公倍数等，用于解决与整数相关的问题。

•概率与统计：包括概率分布、统计推断等，用于分析和预测事件发生的概率。

•矩阵与线性代数：用于解决与矩阵和线性方程组相关的问题。

4. 字符串处理在ACM竞赛中，字符串处理是常见的问题之一。

以下是一些常用的字符串处理技巧：•字符串匹配：如KMP算法、Boyer-Moore算法等，用于在一个字符串中查找另一个字符串。

•字符串排序：如字典序排序、后缀数组等，用于对字符串进行排序。

ACM常用算法ACM常考算法ACM小组内部预定函数Ver 2.0 by IcyFenix数学问题：1.精度计算――大数2.精度计算――乘法（大数3.精度计算――乘法（大阶乘5.精度计算――减法9.快速傅立叶变换（FFT）字符串处理：1.字符串替换计算几何：1.叉乘法求任意多边形面积5.射向法判断点是否在多边形内部9.点到线段最短距离数论：1.x的二进制长度5.求解模线性方程组(中国余数定理) 图论：1.Prim算法求最小生成树排序/查找：1.快速排序数据结构：1.顺序队列乘小数）6.任意进制转换10.Ronberg算法计算积分2.字符串查找2.求三角形面积6.判断点是否在线段上10.求两直线的交点2.返回x的二进制表示中从低到高的第i位6.筛法素数产生器2.Dijkstra算法求单源最短路径2.希尔排序2.顺序栈数乘大数）4.精度计算――加法7.最大公约数、最小公倍数8.组合序列11.行列式计算12.求排列组合数3.字符串截取3.两矢量间角度4.两点距离（2D、3D）7.判断两线段是否相交8.判断线段与直线是否相交11.判断一个封闭图形是12.Graham扫描法寻凹集还是凸集找凸包3.模取幂运算4.求解模线性方程7.判断一个数是否素数3.Bellman-ford算法求4.Floyd算法求每对单源最短路径节点间最短路径3.选择法排序4.二分查找3.链表4.链栈ACM常考算法5.二叉树一、数学问题1.精度计算――大数阶乘语法：int result=factorial(int n); 参数：n：n 的阶乘返回阶乘结果的位数值：注意：源程序：本程序直接输出n!的结果，需要返回结果请保留long a[] 需要math.hint factorial(int n){long a[__];int i,j,l,c,m=0,w; a=1;for(i=1;ii++) { c=0;for(j=0;jj++) {a[j]=a[j]*i+c; c=a[j]/__; a[j]=a[j]%__; }if(c0) {m++;a[m]=c;} }w=m*4+log10(a[m])+1;printf(“\n%ld",a[m]);for(i=m-1;ii--) printf("%4.4ld",a[i]);return w; }2.精度计算――乘法（大数乘小数）语法：mult(char c[],char t[],int m); 参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10以内返回null 值：注意：需要string.hACM常考算法源程序：void mult(char c[],char t[],int m) {int i,l,k,flag,add=0; char s; l=strlen(c);for (i=0;ii++)s[l-i-1]=c[i]-'0';for (i=0;ii++) {k=s[i]*m+add;if (k=10) {s[i]=k%10;add=k/10;flag=1;}else {s[i]=k;flag=0;add=0;} }if (flag) {l=i+1;s[i]=add;}else l=i; for (i=0;ii++)t[l-1-i]=s[i]+'0'; t[l]='\0'; }3.精度计算――乘法（大数乘大数）语法：mult(char a[],char b[],char s[]); 参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回null 值：注意：源程序：空间复杂度为o(n^2) 需要string.hvoid mult(char a[],char b[],char s[]) {int i,j,k=0,alen,blen,sum=0,res={0},flag=0; char result;alen=strlen(a);blen=strlen(b);for (i=0;ialen;i++)for (j=0;jblen;j++) res[i][j]=(a[i]-'0')*(b[j]-'0'); for (i=alen-1;ii--) {for (j=blen-1;jj--) sum=sum+res[i+blen-j-1][j]; result[k]=sum%10; k=k+1;ACM常考算法sum=sum/10; }for (i=blen-2;ii--) {for (j=0;jj++) sum=sum+res[i-j][j]; result[k]=sum%10; k=k+1;sum=sum/10; }if (sum!=0) {result[k]=sum;k=k+1;} for (i=0;ii++) result[i]+='0';for (i=k-1;ii--) s[i]=result[k-1-i]; s[k]='\0';while(1) {if (strlen(s)!=strlen(a)s=='0') strcpy(s,s+1); elsebreak; } }4.精度计算――加法语法：add(char a[],char b[],char s[]); 参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回null 值：注意：源程序：空间复杂度为o(n^2) 需要string.hvoid add(char a[],char b[],char back[]) {int i,j,k,up,x,y,z,l; char *c; if (strlen(a)strlen(b)) l=strlen(a)+2;elsel=strlen(b)+2; c=(char *) malloc(l*sizeof(char)); i=strlen(a)-1; j=strlen(b)-1; k=0;up=0;while(i=0||j=0) {if(i0) x='0'; else x=a[i];ACM常考算法if(j0) y='0'; else y=b[j]; z=x-'0'+y-'0'; if(up) z+=1;if(z9) {up=1;z%=10;} else up=0; c[k++]=z+'0'; i--;j--; }if(up) c[k++]='1'; i=0;c[k]='\0';for(k-=1;kk--) back[i++]=c[k]; back[i]='\0'; }5.精度计算――减法语法：sub(char s1[],char s2[],char t[]); 参数：s1[]：被减数，用字符串表示，位数不限s2[]：减数，用字符串表示，位数不限t[]：结果，用字符串表示返回null 值：注意：源程序：默认s1=s2，程序未处理负数情况需要string.hvoid sub(char s1[],char s2[],char t[]) {int i,l2,l1,k;l2=strlen(s2);l1=strlen(s1); t[l1]='\0';l1--;for (i=l2-1;ii--,l1--) {if (s1[l1]-s2[i]=0)t[l1]=s1[l1]-s2[i]+'0'; else {t[l1]=10+s1[l1]-s2[i]+'0'; s1[l1-1]=s1[l1-1]-1; } } k=l1;while(s1[k]0) {s1[k]+=10;s1[k-1]-=1;k--;} while(l1=0) {t[l1]=s1[l1];l1--;} loop:if (t=='0') {ACM常考算法l1=strlen(s1);for (i=0;il1-1;i++) t[i]=t[i+1]; t[l1-1]='\0'; goto loop; }if (strlen(t)==0) {t='0';t='\0';} }6.任意进制转换语法：conversion(char s1[],char s2[],long d1,long d2); 参数：s[]：原进制数字，用字符串表示s2[]：转换结果，用字符串表示d1：原进制数d2：需要转换到的进制数返回null 值：注意：源程序：高于9的位数用大写'A'～'Z'表示，2～16位进制通过验证void conversion(char s[],char s2[],long d1,long d2) {long i,j,t,num; char c; num=0;for (i=0;s[i]!='\0';i++) {if (s[i]='9's[i]='0') t=s[i]-'0';else t=s[i]-'A'+10;num=num*d1+t; } i=0; while(1) {t=num%d2;if (t=9) s2[i]=t+'0';else s2[i]=t+'A'-10; num/=d2;if (num==0)break; i++; }for (j=0;jj++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;} s2[i+1]='\0'; }7.最大公约数、最小公倍数ACM常考算法语法：resulet=hcf(int a,int b)、result=lcd(int a,int b) 参数：a：int a，求最大公约数或最小公倍数b：int b，求最大公约数或最小公倍数返回返回最大公约数（hcf）或最小公倍数（lcd）值：注意：源程序：lcd 需要连同hcf 使用int hcf(int a,int b) {int r=0; while(b!=0) {r=a%b; a=b; b=r; }return(a); }lcd(int u,int v,int h) {return(u*v/h); }8.组合序列语法：m_of_n(int m,int n1,int m1,int* a,int head) 参数：m：组合数C的上参数n1：组合数C的下参数m1：组合数C的上参数，递归之用*a：1～n的整数序列数组head：头指针返回null 值：注意：源程序：*a需要自行产生初始调用时，m=m1、head=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);ACM常考算法void m_of_n(int m,int n1,int m1,int* a,int head) {int i,t;if(m10 || m1n1)return; if(m1==n1) {for(i=0;ii++) couta[i]' '; // 输出序列cout'\n'; return; }m_of_n(m,n1-1,m1,a,head); // 递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t; m_of_n(m,n1-1,m1-1,a,head+1); // 再次递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t; }9.快速傅立叶变换（FFT）语法：kkfft(double pr[],double pi[],int n,int k,double fr[],double fi[],int l,int il); 参数：pr[n]：输入的实部pi[n]：数入的虚部n，k：满足n=2^k fr[n]：输出的实部fi[n]：输出的虚部l：逻辑开关，0 FFT，1 ifFTil：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回null 值：注意：源程序：需要math.hvoid kkfft(pr,pi,n,k,fr,fi,l,il)int n,k,l,il;double pr[],pi[],fr[],fi[]; {int it,m,is,i,j,nv,l0;double p,q,s,vr,vi,poddr,poddi; for (it=0; it=n-1; it++) {m=it; is=0;for (i=0; i=k-1; i++){j=m/2; is=2*is+(m-2*j); m=j;} fr[it]=pr[is]; fi[it]=pi[is]; }pr=1.0; pi=0.0; p=6.__-__6/(1.0*n);pr=cos(p); pi=-sin(p);ACM常考算法if (l!=0) pi=-pi; for (i=2; i=n-1; i++) {p=pr[i-1]*pr; q=pi[i-1]*pi;s=(pr[i-1]+pi[i-1])*(pr+pi); pr[i]=p-q; pi[i]=s-p-q; }for (it=0; it=n-2; it=it+2) {vr=fr[it]; vi=fi[it];fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1]; }m=n/2; nv=2;for (l0=k-2; l0 l0--) {m=m/2; nv=2*nv;for (it=0; it=(m-1)*nv; it=it+nv) for (j=0; j=(nv/2)-1; j++) {p=pr[m*j]*fr[it+j+nv/2]; q=pi[m*j]*fi[it+j+nv/2]; s=pr[m*j]+pi[m*j];s=s*(fr[it+j+nv/2]+fi[it+j+nv/2]); poddr=p-q; poddi=s-p-q;fr[it+j+nv/2]=fr[it+j]-poddr; fi[it+j+nv/2]=fi[it+j]-poddi;fr[it+j]=fr[it+j]+poddr; fi[it+j]=fi[it+j]+poddi; } }if (l!=0)for (i=0; i=n-1; i++) {fr[i]=fr[i]/(1.0*n); fi[i]=fi[i]/(1.0*n); } if (il!=0)for (i=0; i=n-1; i++) {pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]); if (fabs(fr[i])0.000001*fabs(fi[i])) {if ((fi[i]*fr[i])0) pi[i]=90.0; else pi[i]=-90.0; } elsepi[i]=atan(fi[i]/fr[i])*360.0/6.__-__6; } return; }10.Ronberg算法计算积分语法：result=integral(double a,double b);ACM常考算法参数：a：积分上限b：积分下限function积分函数f：返回值：f在（a,b）之间的积分值注意：源程序：function f(x)需要自行修改，程序中用的是sina(x)/x 需要math.h 默认精度要求是1e-5double f(double x) {return sin(x)/x; //在这里插入被积函数}double integral(double a,double b) {double h=b-a;double t1=(1+f(b))*h/2.0; int k=1;double r1,r2,s1,s2,c1,c2,t2; loop:double s=0.0;double x=a+h/2.0; while(xb) {s+=f(x); x+=h; }t2=(t1+h*s)/2.0; s2=t2+(t2-t1)/3.0; if(k==1) {k++;h/=2.0;t1=t2;s1=s2; goto loop; }c2=s2+(s2-s1)/15.0; if(k==2){c1=c2;k++;h/=2.0; t1=t2;s1=s2; goto loop; }r2=c2+(c2-c1)/63.0; if(k==3){r1=r2; c1=c2;k++; h/=2.0;t1=t2;s1=s2; goto loop; }while(fabs(1-r1/r2)1e-5){ r1=r2;c1=c2;k++; h/=2.0;ACM常考算法t1=t2;s1=s2; goto loop; }return r2; }11.行列式计算语法：result=js(int s[][],int n) 参数：s[][]：行列式存储数组n：行列式维数，递归用返回行列式值值：注意：源程序：函数中常数N为行列式维度，需自行定义int js(s,n)int s[][N],n; {int z,j,k,r,total=0; int b[N][N];/*b[N][N]用于存放，在矩阵s[N][N]中元素s的余子式*/if(n2) {for(z=0;zz++) {for(j=0;jj++)for(k=0;kk++)if(k=z) b[j][k]=s[j+1][k+1]; else b[j][k]=s[j+1][k];if(z%2==0) r=s[z]*js(b,n-1); /*递归调用*/ else r=(-1)*s[z]*js(b,n-1); total=total+r; } }else if(n==2)total=s*s-s*s; return total; }12.求排列组合数语法：result=P(long n,long m); / result=long C(long n,long m); 参数：m：排列组合的上系数n：排列组合的下系数返回排列组合数ACM常考算法值：注意：源程序：符合数学规则：m＝nlong P(long n,long m) {long p=1; while(m!=0){p*=n;n--;m--;} return p; }long C(long n,long m) {long i,c=1; i=m;while(i!=0){c*=n;n--;i--;} while(m!=0) {c/=m;m--;} return c; }二、字符串处理1.字符串替换语法：replace(char str[],char key[],char swap[]); 参数：str[]：在此源字符串进行替换操作key[]：被替换的字符串，不能为空串swap[]替换的字符串，可以为空串，为空串表示在源字符中删除key[] ：返回null 值：注意：源程序：默认str[]长度小于1000，如否，重新设定设定tmp大小需要string.hvoid replace(char str[],char key[],char swap[]) {int l1,l2,l3,i,j,flag; char tmp; l1=strlen(str); l2=strlen(key);l3=strlen(swap);for (i=0;i=l1-l2;i++)ACM常考算法{flag=1;for (j=0;jj++)if (str[i+j]!=key[j]) {flag=0;break;} if (flag) {strcpy(tmp,str);strcpy(tmp[i],swap);strcpy(tmp[i+l3],str[i+l2]); strcpy(str,tmp); i+=l3-1;l1=strlen(str); } } }2.字符串查找语法：result=strfind(char str[],char key[]); 参数：str[]：在此源字符串进行查找操作key[]：被查找的字符串，不能为空串返回如果查找成功，返回key在str中第一次出现的位置，否则返回-1 值：注意：源程序：需要string.hint strfind(char str[],char key[]) {int l1,l2,i,j,flag; l1=strlen(str); l2=strlen(key);for (i=0;i=l1-l2;i++) {flag=1;for (j=0;jj++)if (str[i+j]!=key[j]) {flag=0;break;} if (flag)return i; }return -1; }3.字符串截取语法：mid(char str[],int start,int len,char strback[]) 参数：str[]：操作的目标字符串start：从第start个字符串开始，截取长度为len的字符ACM常考算法len：从第start个字符串开始，截取长度为len的字符strback[ 截取的到的字符]：返回值：0：超出字符串长度，截取失败；1：截取成功注意：需要string.h源程序：int mid(char str[],int start,int len,char strback[]) {int l,i,k=0; l=strlen(str);if (start+lenl)return 0; for (i=start;istart+len;i++) strback[k++]=str[i]; strback[k]='\0'; return 1; }三、计算几何1.叉乘法求任意多边形面积语法：result=polygonarea(Point *polygon,int N); 参数：*polyg多变形顶点数组on：N：多边形顶点数目返回多边形面积值：注意：源程序：支持任意多边形，凹、凸皆可多边形顶点输入时按顺时针顺序排列typedef struct { double x,y; } Point;double polygonarea(Point *polygon,int N) {int i,j;double area = 0;for (i=0;ii++) { j = (i + 1) % N;area += polygon[i].x * polygon[j].y; area -= polygon[i].y *polygon[j].x; }ACM常考算法area /= 2;return(area 0 ? -area : area); }2.求三角形面积语法：result=area3(float x1,float y1,float x2,float y2,float x3,float y3); 参数：x1～3：三角形3个顶点x坐标y1～3：三角形3个顶点y坐标返回三角形面积值：注意：源程序：需要math.hfloat area3(float x1,float y1,float x2,float y2,float x3,float y3) {float a,b,c,p,s;a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)); c=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c)); return s; }3.两矢量间角度语法：result=angle(double x1,double y1,double x2,double y2); 参数：x/y1～两矢量的坐标2：返回两的角度矢量值：注意：源程序：返回角度为弧度制，并且以逆时针方向为正方向需要math.h#define PI 3.__-__double angle(double x1,double y1,double x2,double y2) {ACM常考算法double dtheta,theta1,theta2; theta1 = atan2(y1,x1); theta2 =atan2(y2,x2); dtheta = theta2 - theta1; while (dtheta PI) dtheta -= PI*2; while (dtheta -PI) dtheta += PI*2; return(dtheta); }4.两点距离（2D、3D）语法：result=distance_2d(float x1,float x2,float y1,float y2); 参数：x/y/z1各点的x、y、z坐标～2：返回两点之间的距离值：注意：源程序：需要math.hfloat distance_2d(float x1,float x2,float y1,float y2) {return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); }float distance_3d(float x1,float x2,float y1,float y2,float z1,float z2) { return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))); }5.射向法判断点是否在多边形内部语法：result=insidepolygon(Point *polygon,int N,Point p); 参数：*polyg多边形顶点数组on：N：多边形顶点个数p：被判断点返回0：点在多边形内部；1：点在多边形外部值：注意：若p点在多边形顶点或者边上，返回值不确定，需另行判断ACM常考算法源程序：需要math.h#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct { double x,y; } Point;int insidepolygon(Point *polygon,int N,Point p) {int counter = 0; int i;double xinters; Point p1,p2;p1 = polygon;for (i=1;ii++) { p2 = polygon[i % N];if (p.y MIN(p1.y,p2.y)) {if (p.y = MAX(p1.y,p2.y)) {if (p.x = MAX(p1.x,p2.x)) { if (p1.y != p2.y) { xinters =(p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;if (p1.x == p2.x || p.x = xinters) counter++; } } } }p1 = p2; }if (counter % 2 == 0) return(__); elsereturn(INSIDE); }6.判断点是否在线段上语法：result=Pointonline(Point p1,Point p2,Point p); 参数：p1、p2：线段的两个端点p：被判断点返回0：点在不在线段上；1：点在线段上值：注意：源程若p线段端点上返回1 需要math.hACM常考算法序：#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct {double x,y; } Point;int FC(double x1,double x2) {if (x1-x20.000002x1-x2-0.000002)return 1;else return 0; }int Pointonline(Point p1,Point p2,Point p) {double x1,y1,x2,y2; x1=p.x-p1.x; x2=p2.x-p1.x; y1=p.y-p1.y; y2=p2.y-p1.y;if (FC(x1*y2-x2*y1,0)==0)return 0;if ((MIN(p1.x,p2.x)=p.xp.x=MAX(p1.x,p2.x))(MIN(p1.y,p2.y)=p.yp.y=MAX(p1.y,p2.y))) return 1;else return 0; }7.判断两线段是否相交语法：result=sectintersect(Point p1,Point p2,Point p3,Point p4); 参数：p1～两条线段的四个端点4：返回0：两线段不相交；1：两线段相交；2两线段首尾相接值：注意：源程序：p1!=p2;p3!=p4;#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct { double x,y; } Point;int lineintersect(Point p1,Point p2,Point p3,Point p4) {Point tp1,tp2,tp3; if((p1.x==p3.xp1.y==p3.y)||(p1.x==p4.xp1.y==p4.y)||(p2.x==p3.xp2.y==p3.y )||(p2.x==p4.xp2.y==p4.y)) return 2; //快速排斥试验if((MIN(p1.x,p2.x)p3.xp3.xMAX(p1.x,p2.x)MIN(p1.y,p2.y)p3.yMAX(p1.y,p2.y))|| ACM常考算法(MIN(p1.x,p2.x)p4.xp3.xMAX(p1.x,p2.x)MIN(p1.y,p2.y)p3.yMAX(p1.y,p2.y))) ; else return 0;//跨立试验tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y;if ((tp1.__tp2.y-tp1.y*tp2.x)*(tp2.__tp3.y-tp2.y*tp3.x)=0)return 1;else return 0; }8.判断线段与直线是否相交语法：result=lineintersect(Point p1,Point p2,Point p3,Point p4); 参数：p1、p2：线段的两个端点p3、p4：直线上的两个点返回0：线段直线不相交；1：线段和直线相交值：注意：源程序：如线段在直线上，返回1typedef struct { double x,y; } Point;int lineintersect(Point p1,Point p2,Point p3,Point p4) {Point tp1,tp2,tp3; tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y;if ((tp1.__tp2.y-tp1.y*tp2.x)*(tp2.__tp3.y-tp2.y*tp3.x)=0)return 1;else return 0; }9.点到线段最短距离语法：result=mindistance(Point p1,Point p2,Point q); 参数：p1、线段的两个端点p2：ACM常考算法q：判断点返回点q到线段p1p2的距离值：注意：源程序：需要math.h#define MIN(x,y) (x y ? x : y)#define MAX(x,y) (x y ? x : y) typedef struct { double x,y; } Point;double mindistance(Point p1,Point p2,Point q) {int flag=1; double k; Point s;if (p1.x==p2.x) {s.x=p1.x;s.y=q.y;flag=0;} if (p1.y==p2.y){s.x=q.x;s.y=p1.y;flag=0;} if (flag) {k=(p2.y-p1.y)/(p2.x-p1.x);s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1); s.y=k*(s.x-p1.x)+p1.y; }if (MIN(p1.x,p2.x)=s.xs.x=MAX(p1.x,p2.x))return sqrt((q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y)); elsereturnMIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y))); }10.求两直线的交点语法：result=mindistance(Point p1,Point p2,Point q); 参数：p1～直线上不相同的两点p4：*p：通过指针返回结果返回1：两直线相交；2：两直线平行值：注意：源程序：如需要判断两线段交点，检验k和对应k1（注释中）的值是否在0～1之间，用在0～1之间的那个求交点ACM常考算法typedef struct { double x,y; } Point;int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p) {double k; //同一直线if ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0) return 2; //平行，不同一直线if ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0) return 0;k=((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)); (*p).x=p1.x+k*(p2.x-p1.x);(*p).y=p1.y+k*(p2.y-p1.y); return 1;//有交点}11.判断一个封闭图形是凹集还是凸集语法：result=convex(Point *p,int n); 参数：*p：封闭曲线顶点数组n：封闭曲线顶点个数返回1：凸集；-1：凹集；0：曲线不符合要求无法计算值：注意：源程序：默认曲线为简单曲线：无交叉、无圈typedef struct { double x,y; } Point;。

ACM基础算法入门教程ACM（ACM International Collegiate Programming Contest）是国际大学生程序设计竞赛的缩写，被认为是计算机领域最有权威和最具挑战性的竞赛之一、ACM竞赛要求参赛者在规定的时间内，根据给出的问题，编写出能在规定时间内运行并给出正确答案的程序。

参加ACM竞赛不仅可以锻炼算法思维，提高编程实力，还可以拓宽知识领域和增加竞争力。

在这个ACM基础算法入门教程中，我们将介绍一些常用的基础算法和数据结构，帮助初学者更好地理解和掌握ACM竞赛所需的算法知识。

一、排序算法排序算法是ACM竞赛中最常用的算法之一，能够帮助我们按照一定的规则将数据进行排序，从而解决一些需要有序数据的问题。

1.冒泡排序：通过多次比较和交换来实现，每次迭代将最大的值沉到最底部。

2.快速排序：选择一个基准元素将数组分为两部分，一部分都小于基准元素，一部分都大于基准元素，递归排序子数组。

3.归并排序：将数组不断二分，将相邻两个子数组排序后再合并成一个有序数组。

4.插入排序：从第二个元素开始，依次将元素插入已排序的子数组中。

二、查找算法查找算法可以帮助我们在一组数据中找到目标元素，从而解决一些需要查找特定数据的问题。

1.顺序查找：逐个扫描数据，直到找到目标元素或扫描结束为止。

2.二分查找：对已排序的数组进行查找，不断将数组二分直到找到目标元素的位置。

3.哈希查找：通过计算数据的哈希值找到对应的存储位置，实现快速查找。

三、字符串匹配算法字符串匹配算法可以帮助我们在一组字符串中寻找特定模式的子字符串，从而解决一些需要在字符串中查找其中一种规律的问题。

1.暴力匹配算法：对目标字符串的每个位置，逐个将模式串进行匹配，直到找到或匹配结束为止。

2.KMP算法：通过已匹配的部分信息，尽量减少字符比较的次数。

3. Boyer-Moore算法：通过预先计算模式串中每个字符最后出现位置的表格，以及坏字符规则和好后缀规则，来实现快速匹配。

目录1.河内之塔 .............................................................................................................. 错误!未定义书签。

Gossip: 费式数列 ................................................................................................. 错误!未定义书签。

3.巴斯卡三角形 ...................................................................................................... 错误!未定义书签。

Gossip: 三色棋 ..................................................................................................... 错误!未定义书签。

Gossip: 老鼠走迷官（一）.................................................................................. 错误!未定义书签。

Gossip: 老鼠走迷官（二）.................................................................................. 错误!未定义书签。

Gossip: 骑士走棋盘.............................................................................................. 错误!未定义书签。

ACM常用算法1）递推求解：首先，确认：能否容易的得到简单情况的解；然后，假设：规模为N-1的情况已经得到解决；最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。

例题1在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。

分析F(1)=2;F(n) = F(n-1)+n;化简后为F(n) = n(n+1)/2 +1;例题2 平面上有n条折线，问这些折线最多能将平面分割成多少块?分析把折线当作两天直线相交然后再减去交集延伸部分。

F= 2n ( 2n + 1 ) / 2 + 1 - 2n;2）贪心算法：在对问题求解时，总是作出在当前看来是最好的选择。

也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。

贪心算法的基本步骤包括1、从问题的某个初始解出发。

2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。

3、将所有部分解综合起来，得到问题的最终解。

例题1已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。

一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。

事件序列包含的事件数目，称为该事件序列的长度。

请编程找出一个最长的事件序列。

分析不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。

则原题的要求就是找一个最长的序列a1&lt;a2&lt;…&lt;an，满足：Begin[a1]&lt;End[a1]&lt;=…&lt;=Begin[an]&lt;End[an]；可以证明，如果在可能的事件a1&lt;a2&lt;…&lt;an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。

acm常用算法和数据结构1.引言1.1 概述概述部分是对整篇文章进行简要介绍，让读者了解本文的主题和内容。

下面是对1.1概述部分的内容的编写建议：概述部分旨在向读者介绍本文的主要内容和目的。

本文主要讨论ACM （算法竞赛）中常用的算法和数据结构。

ACM常用算法和数据结构是指在解决各类计算机编程竞赛或算法题目时经常使用的，被广泛验证和应用的算法和数据结构。

本文主要分为引言、正文和结论三个部分。

引言部分描述了本文整体的构架和目的，正文部分详细介绍了常用算法和数据结构的分类和特点，结论部分对本文进行总结，并探讨了这些常用算法和数据结构在实际应用中的前景。

在正文部分的常用算法中，我们将介绍一些经典的排序算法，如冒泡排序、插入排序和快速排序等，同时还会讨论一些常见的查找算法，如顺序查找和二分查找等。

这些算法都有着不同的时间复杂度和空间复杂度，以及各自适用的场景。

在数据结构部分，我们将详细介绍数组和链表这两种最基础的数据结构。

数组是一种线性存储结构，可以用于存储同一类型的一组数据，并且支持随机访问。

链表则是由一系列节点组成的，每个节点包含数据和指向下一个节点的指针，链表常用于实现队列、栈和链表等数据结构。

最后在结论部分，我们将对本文进行总结，强调常用算法和数据结构在实际应用中的重要性和价值。

并探讨这些算法和数据结构在日常编程工作中的应用前景，以帮助读者更好地理解和应用这些常用算法和数据结构。

通过本文的学习，读者将能够掌握ACM竞赛中的常用算法和数据结构的基本原理和应用方法，进一步提升算法思维和编程能力，为解决实际问题提供高效的解决方案。

文章结构部分的内容可以包括以下内容：文章结构旨在为读者提供对整篇文章内容的整体把握，方便读者在需要时能够快速定位和浏览特定的内容部分。

以下是本文的整体结构：1. 引言1.1 概述1.2 文章结构1.3 目的2. 正文2.1 常用算法2.1.1 排序算法2.1.2 查找算法2.2 数据结构2.2.1 数组2.2.2 链表3. 结论3.1 总结常用算法和数据结构3.2 应用前景在本文中，首先在引言部分对整篇文章进行了概述，说明了文章的目的和内容。

ACM常见算法ACM算法⼀、数论算法 1．求两数的最⼤公约数 2．求两数的最⼩公倍数 3．素数的求法 A.⼩范围内判断⼀个数是否为质数： B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：⼆、图论算法1．最⼩⽣成树A.Prim算法：B.Kruskal算法：(贪⼼) 按权值递增顺序删去图中的边，若不形成回路则将此边加⼊最⼩⽣成树。

2.最短路径 A.标号法求解单源点最短路径： B.Floyed算法求解所有顶点对之间的最短路径： C. Dijkstra 算法：3.计算图的传递闭包4．⽆向图的连通分量 A.深度优先 B 宽度优先（种⼦染⾊法）5．关键路径⼏个定义：顶点1为源点，n为汇点。

a. 顶点事件最早发⽣时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0; b. 顶点事件最晚发⽣时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n); c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表⽰，则Ee[I] = Ve[j]; d. 边活动最晚开始时间 El[I], 若边I由<j,k>表⽰，则El[I] = Vl[k] – w[j,k]; 若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。

求解⽅法： a. 从源点起topsort,判断是否有回路并计算Ve; b. 从汇点起topsort,求Vl; c. 算Ee 和 El;6．拓扑排序找⼊度为0的点，删去与其相连的所有边，不断重复这⼀过程。

例寻找⼀数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.7.回路问题 Euler回路(DFS) 定义：经过图的每条边仅⼀次的回路。

（充要条件：图连同且⽆奇点） Hamilton回路定义：经过图的每个顶点仅⼀次的回路。