ACM竞赛中所用到的数据结构_非常不错_和大家分享汇总

格式：ppt
大小：1.82 MB
文档页数：68

下载文档原格式

ACM竞赛中所用到的数据结构

678.html
后缀数组
/view/1240197.htm
调整的整个过程称之为重构(restructuring)
AVL的使用 AVL的使用
因为旋转的过程较为复杂，需要较大的编码量，在实际比赛中，我们一般使用C++ STL（在实际比赛中，我们一般使用C++ STL（Standard Template Library）标准模板库。 Library）标准模板库 <map>
长度为m的母串S, 匹配长度为n的子串A 长度为m的母串S, 匹配长度为n的子串A 求母串S中有多少个子串A 求母串S中有多少个子串A 求母串S中第1个子串A 求母串S中第1个子串A的位置
KMP算法的复杂度为O(m+n) KMP算法的复杂度为O(m+n) 总体思想
O(n)线性时间预处理子串，求出前缀函数 O(n)线性时间预处理子串，求出前缀函数 O(m)线性时间扫描母串求出匹配 O(m)线性时间扫描母串求出匹配
随机查找第k 随机查找第k小元素
随机第k 随机第k小元素 int select(int *a,int b,int e,int k){ if(b==e) return a[b]; int x=a[b+rand()%(e-b+1)],i=b-1,j=e+1,tmp; x=a[b+rand()%(e-b+1)],i=bwhile (i<j){ while(a[++i]<x); while(a[--j]>x); while(a[--j]>x); if (i<j) tmp=a[i],a[i]=a[j],a[j]=tmp; } if (j==e) j--; j--; i=j-b+1; i=jif (k<=i) return select(a,b,j,k); else return select(a,j+1,e,k-i); select(a,j+1,e,k}

Acm竞赛常用算法与数据结构

• 每次用堆取出x进行计算，O(mnlogmn)。
28
哈希表(Hash)
• 理论上查找速度最快的数据结构之一 • 缺点：需要大量的内存需要构造Key
29
Hash表的实现
• 数组 • 冲突解决法 • 开散列法 • 闭散列法 C++ sgi stl 实现
30
Hash Key的选取
• 数值： • 方法一：直接取余数（一般选取质数M最为除数） • 方法二：平方取中法，即计算关键值的平方， 2 r 的表再取中间r位形成一个大小为
7
常见题型
•Dynamic Programming(动态规划) •Greedy(贪心) •Complete Search(穷举) •Flood Fill (种子填充)
8
常见题型
• Shortest Path (最短路径) • Recursive Search Techniques (回溯） • Minimum Spanning Tree （最小生成树） • Knapsack（背包）
22
Parity(ceoi99)
• 从整个01序列肯定是无法入手的，因为它的长度高达109。 • 从范围比较小的n入手。也就是说我们需要对信息进行一些特殊的处理。 • a b even/odd，那么将元素b指向a-1，边的权值是even/odd。 • 下面我们由样例来说明一下这个处理方法。
23
11
12
枚举法
• 又叫穷举法，它利用了计算机计算速度快且准确的特点，是最为朴素和有效的一种算法。
• 不是办法的办法
• 但有时却是最好的办法
13
Pizza Anyone? （ZOJ 1219）
• 题目大意：你需要为你和你的朋友们订一个皮萨。每个朋友都会告诉你他们想和不想放进皮萨里的东西。你是否能订一个皮萨，让他满足每个人至少一个条件。假设一共有16种东西可以放进皮萨。

栈与队列(ACM)讲解

数制转换
数制转换
标准输入输出
题目描述：
数制转换。(要求采用栈实现,练习进栈入栈函数的编写)
输入：输入的第一行包含两个数,n,d n表示要转换的数的个数 d表示要转换成的进制数接下来是n个十进制数

输出：对每一测试用例，用一行输
输入样例： 2 8 123 213 输出样例： 173 325
后序表达式求值
后续表达式(逆波兰式)的特点：没有括号。
从前向后扫，遇到操作数压栈；遇到操作符，从栈中取出2个操作数运算，结果压栈。最终栈中所剩的数为结果。
我们先来定义运算符的优先级： ( +,*,/,% 从上到下依次升高
中序表达式求值
中序表达式求值
准备2个栈，一个专门存放运算符，另一个专门存放操作数。 1.遇到)，那么退栈计算到(为止.结果压栈。 2.遇到运算数.那么压栈。 3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈. 4.否则压栈.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()

{
string cmd, url;
stack<string> s1, s2; //定义了两个栈
//栈1用作存储操作队列，而栈2则用作临时保存栈1出栈的数据
N=3时，输出
样例
123 132 213 231 321
算法
生成所有 1,2...n的排列，再依次判断是否符合要求。
判断序列是否可行时调用上一题算法。输出可行解。

ACM必须掌握的算法

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 程序设计竞赛入门：第4讲简单数据结构

2020/12/10
7
1. 并查集
初始状态： {1} {2} {3} {4} {5} {6} {7} {8} {9}
输入关系分离集合
(2,4)
{2,4}
•最后我们得到3 个集合{1,2,3,4},
(5,7) (1,3) (8,9) (1,2) (5,6)
{2,4} {5,7} {1,3} {2,4} {5,7} {1,3} {2,4} {5,7} {8,9} {1,2,3,4} {5,7} {8,9} {1,2,3,4} {5,6,7} {8,9}
两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。
2020/12/10
3
1. 并查集
1.1 引例
输入格式 (Input Format):
输入的第一行是一个整数N(2<=N<=1000)，表示强盗的个数（从1编号到N）。第二行 M(1<=M<=5000)，表示关于强盗的信息条数。以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敌人。输入数据保证不会产生信息的矛盾。
第四讲简单数据结构
2020/12/10
1
主要内容
并查集树状数组线段树
2020/12/10
2
1. 并查集
1.1 引例
题目描述：
1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：
我朋友的朋友是我的朋友。
我敌人的敌人也是我的朋友。
效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过lgk

[acm]数据结构

3.并查集的查找操作，带路径压缩
二．区间信息的维护与查询 1.树状数组(动态连续和查询问题) 支持两种操作：ADD( x,d )让 Ax 增加 d; Query( L,R ):计算 AL+...+AR。 Lowbit(x)为 x 的二进制表达式中最右边的 1 所对应的值。 (补码特性)(x&-x) 对于节点 i，若是左节点，父节点为 i+lowbit(i)；右节点为 i-lowbit(i)。每个点对应一段连续和 Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+...+Ai 。
struct node { }; inline void pushdown(int p,int row) { } } else if (st[row][p].Add>0){ st[row][p<<1].Add +=st[row][p].Add; st[row][p<<1|1].Add +=st[row][p].Add; if (st[row][p].Set>=0) { st[row][p<<1].Set = st[row][p<<1|1].Set = st[row][p].Set; st[row][p<<1].Add = st[row][p<<1|1].Add = st[row][p].Add; int L,R; int Sum,Min,Max; int Set,Add; node(int sum=0,int c_min=INF,int c_max=0):Sum(sum),Min(c_min),Max(c_max) {}

acm大牛总结的资料

ACM资料（一）不可能都完全记住那么多的算法.常用算法,拿过来就可以写出来不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过).对以前没有记过的算法,就不好说了,难的可能要研究好几天.这样就可以了.应该熟练掌握的常用的算法应该有:各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）线性表(一般的线性表,栈,队列)的插入和删除二叉树的遍历（前序，中序，后序）图的遍历（深度优先，广度优先）二分法查找，排序二叉树，Hash查找（处理冲突的方法）。

（二）分析一个东西,你可以用不同的眼光去看待,有很多时候,就跟自己生活一样,觉得小时候看待问题很幼稚,现在看问题全面了,而且方式不一样了,为什么,就是成长吧,就跟这个一样的,你对算法,比如写一个程序,可能直接写很简单,可是可以有一些有趣的方式,比如通过什么样来表达,怎么样更高效..等等吧（三）于大学里把基本的专业课学扎实就ok，如：数据结构，离散，操作系统等。

碰到一些基本的数据结构和算法，如查找排序要根据原理马上能写出相应的代码就行了，我个人是这样理解的，对于更深层次的东西，也是建立在自己熟练的基础之上的吧（四）算法与数据结构考验试题精析》第2版机械工业出版社如果你想练习的话，这里有N多的题可以来练习，但实际中能用到的比较少，除非搞一些高端的玩意，不过平时也可以在自己的项目中结合使用（五）数据结构在平时可能用不上，但数据结构可以培养你程序时如果注意效率的意识，一个学过数据结构的人和一个没有学过数结构的人写出来的程序可能在效率上有差别。

（六）搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的.竞赛组织竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。

参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。

acm竞赛知识点

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法大赛知识点总结

算法大赛知识点总结算法大赛是针对计算机科学和编程领域的竞赛活动，旨在选拔和培养具有优秀算法设计和编程实施能力的人才。

参加算法大赛需要具备丰富的算法知识、编程技巧和解决问题的能力。

下面将对算法大赛涉及到的知识点进行总结，包括数据结构、常用算法、动态规划、图论等方面的知识。

一、数据结构1. 数组数组是一种最基本的数据结构，它可以存储一组相同类型的数据。

在算法大赛中，经常需要使用数组来存储数据，并进行相关的操作，比如查找、排序、插入、删除等。

2. 链表链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

在算法大赛中，链表可以用来实现队列、栈等数据结构。

3. 栈和队列栈是一种后进先出（LIFO）的数据结构，只允许在一端进行操作。

队列是一种先进先出（FIFO）的数据结构，允许在两端进行操作。

在算法大赛中，栈和队列经常用来解决相关问题。

4. 树和二叉树树是一种抽象数据结构，它由一系列节点组成，每个节点最多有两个子节点。

二叉树是一种特殊的树结构，每个节点最多有两个子节点。

在算法大赛中，树和二叉树是重要的数据结构，可以用来解决很多问题。

5. 堆和优先队列堆是一种特殊的树结构，可以用来实现优先队列。

在算法大赛中，堆和优先队列通常可以用来解决一些优先级相关的问题。

6. 哈希表哈希表是一种常用的数据结构，可以实现快速的查找、插入和删除操作。

在算法大赛中，哈希表通常可以用来解决一些查找和去重的问题。

7. 图图是一种非常重要的数据结构，它由一系列顶点和边组成。

在算法大赛中，图的相关算法和数据结构经常可以用来解决很多问题，比如最短路径、最小生成树、网络流等问题。

二、常用算法1. 排序算法排序算法是一种非常基础和常用的算法，它可以将一组数据按照一定的顺序排列。

在算法大赛中，常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。

2. 查找算法查找算法是一种用来在一组数据中寻找指定元素的算法。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

堆栈Stack
#include<stack> using namespace std; //STL stack <int> S;
链表list
特点：
插入O(k)
删除O(k)
查找O(k)
最坏情况下都是O(n)
实现方法：
链表
数组->改进块状数组
STL
链表list
#include<list> using namespace std; //STL list<int> S;
串的模式匹配--BM
算法的关键和 KMP 类似，也是构造一个辅助数组，不过，不同于KMP算法的是，BM算法的辅助数组大小只和匹配串的字符集大小相关（一般情况下也就是ASCII字符集，256个字符），其内容和模式串相关，辅助数组的内容即是模式串的索引： position[patten[i]]=i; 也是相当简单的辅助数组构造。
关于堆 Heap
二叉堆（又名最大/最小堆）二项堆映射2分堆 Fibonacci堆 Interval heap 左偏树Leftist Tree
队列Queue
特点：
先进先出 FIFO 入队O(1), 出队O(1) 不能随机访问中间的元素
实现方法：
链表数组 STL
队列Queue
串的模式匹配--KMP
// start matching pattern T in S[i..)
// return match pos or longest match length with corresponding pos
int kmp(char *s, int ls, char *t, int lt, int i,int &longest,int &lp)
ACM竞赛中所用到的数据结构
唐陈兴 2007.12.26
基本数据结构
基础：队列、堆栈、链表排序与检索：快速排序和归并排序的思想串的模式匹配：KMP, Boyer-Moore, Trie(*), 有
限状态自动机(*) 树：左儿子右兄弟表示法, AVL(用STL实现),
哈夫曼树,Splay Tree(*), 树状数组，线段树，PQ树(***) 字典：Hash、并查集(*)、可并优先队列，堆
}
return -1;
}
串的模式匹配--BM
快速的字符串查找算法 Boyer-Moore算法 BM 算法是一个较优的模式匹配算法。一般，如果
不考虑模式串的长度，一个具有时间复杂度O(n)的算法应该是最优的了，但是事实不是如此。BM算法可以实现更高效率的模式匹配。分析和实验说明， BM匹配算法对于那些字符集比较大，而模式串中出现的字符比较少的时候，工作效率最快。而且，考虑KMP匹配方式的优化，可以结合KMP匹配和 BM匹配，进一步提高效率。
随机查找第k小元素
随机第k小元素
int select(int *a,int b,int e,int k){
if(b==e) return a[b];
int x=a[b+rand()%(e-b+1)],i=b-1,j=e+1,tmp;
while (i<j){
while(a[++i]<x);
while(a[--j]>x);
具体可以见
http://www-igm.univ-mlv.fr/~lecroq/string/node14.html 另外，动态演示程序见附件
二叉搜索树
BST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系
{
longest = lp = 0; --s; --t;
for(int j=1; i<=ls; i++,j++) {
while( j>0 && s[i]!=t[j] ) j=fail[j];
if( j>longest ) { longest = j; lp = i-j; }
if( j==lt ) return i-lt;
if (i<j) tmp=a[i],a[i]=a[j],a[j]=tmp;
ቤተ መጻሕፍቲ ባይዱ
}
if (j==e) j--;
i=j-b+1;
if (k<=i) return select(a,b,j,k);
else return select(a,j+1,e,k-i);
}
串的模式匹配--KMP
由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法
链表list
排序
排序
快速排序 O(n*log(n)) 堆排序（稳定排序）O(n*log(n)) 选择排序,冒泡排序 O(n^2) 桶排序 O(M)
O(n)随机查找第k小元素
std:sort
STL #include<algorithm> using namespace std; int a[M],b[M]; sort(a,a+n); sort(a,a+n,cmp); bool cmp(const int x,const int y){ return x>y; //return b[x]<b[y]; }
朴素的串模式匹配的复杂度是O(m*n)
长度为m的母串S, 匹配长度为n的子串A 求母串S中有多少个子串A 求母串S中第1个子串A的位置
KMP算法的复杂度为O(m+n) 总体思想
O(n)线性时间预处理子串，求出前缀函数 O(m)线性时间扫描母串求出匹配
串的模式匹配--KMP
//KMP 求前缀函数 int fail[maxlen]; void makefail( char *t, int lt ) { --t; for(int i=1,j=0;i<=lt;i++,j++){ fail[i]=j; while(j>0 && t[i]!=t[j]) j=fail[j]; } }
#include<queue> using namespace std; queue <int> Q; Member Functions:
//STL queue
堆栈Stack
特点：
先进后出 FILO 入队O(1), 出队O(1) 不能随机访问中间的元素
实现方法：
链表数组 STL

ACM竞赛中所用到的数据结构_非常不错_和大家分享汇总

合集下载