《算法合集之《基本数据结构在信息学竞赛中的应用》》由会员分享，可在线阅读，更多相关《算法合集之《基本数据结构在信息学竞赛中的应用》（38页珍藏版）》请在金锄头文库上搜索。
1、基本数据结构在信息学竞赛中的应用,安徽省芜湖市第一中学 朱晨光,IOI2006中国国家集训队论文,安徽省芜湖市第一中学 朱晨光,引言,题目难应用高级数据结构,基本数据结构！,本篇论文将介绍几种基本数据结构在信息学竞赛中的应用，并通过几道例题集中体现这些数据结构的重要作用。,编程复杂度高,容易出错,第一部分基本数据结构的介绍,一、线性表（线性表的顺序存储结构）,线性表,二、线性表的链式存储结构,线性链表：,线性表的链式存储结构,循环链表：,线性表的链式存储结构,双向链表：,栈,队列,第二部分基本数据结构的应用,栈的应用 例1 求01矩阵中最大的全零矩形 线性表的应用 例2 营业额统计 队列的应用
2、 例3 瑰丽华尔兹,线性表的应用营业额统计,给定N（1N32767）天的营业额a1,a2,an. 定义一天的最小波动值等于min|该天以前某一天的营业额-该天营业额| 特别地，第一天的最小波动值即为a1试求N天的最小波动值之和,例如：N=3,a1=9,a2=3,a3=8，则各天最小波动值依次为9，6，1，和为16,分析,这道题目的规模很大，如果简单地用两重循环解决，时间复杂度高达O(N2)，难以满足要求。,算法低效的原因在于没有高效地将数据组织起来，而是松散地存储在数组中，导致对于每一个营业额都需要检查前面所有的营业额。,分析,实际上，有一种高级数据结构平衡树可以解决这个问题。我们可以在将一天
3、的营业额插入平衡树的过程中得到该天的最小波动值。方法是求出所有在插入路径上的数字与改天营业额差的绝对值，从中取出最小值。这种算法的时间复杂度为O(Nlog2N).,进一步改进,平衡树左旋，右旋，双旋 高效 高出错率,Yes!,那么，基本数据结构能否在这里得到应用呢？,应用基本数据结构双向链表,将这N个元素进行排序，得到序列c，同时记录原来第i个元素在排序后的位置bi,将排序后的序列在静态数组中建成一个双向链表,按照从an到a1的顺序依次处理每个元素,双向链表,对于an，查看bn的前驱prebn与后继nextbn所指的数 最小波动值必然是an与这两个数中的某一个的差的绝对值 处理完an后，我们把
4、它从双向链表中删除，接着处理an-1,动画演示,最小波动值为min|8-3|,|8-9|=min6,1=1,最小波动值为min|3-9|=6,9,最小波动值为9,最小波动值总和为1+6+9=16,时间复杂度分析,排序,O(Nlog2N),建表,O(N),处理,O(N),O(Nlog2N),小结,平衡树,编程复杂度高,基本数据结构双向链表,没有增加时间复杂度,大大降低编程复杂度,思路清晰,见解独到,队列的应用瑰丽华尔兹,给定一个N行M列的矩阵，矩阵中的某些方格上有障碍物。有一个人从矩阵中的某个方格开始滑行。每次滑行都是向一个方向最多连续前进ci格（也可以原地不动）。但是这个人在滑行中不能碰到障碍
5、物。现按顺序给出K次滑行的方向（东、南、西、北中的一个）以及ci ，试求这个人能够滑行的最长距离（即格子数）。数据范围：1N,M200，K200， 40000,样例,障碍,分析,本题是一个求最值的问题。根据题目中K次滑行的有序性以及数据范围，可以很容易设计出这样一种动态规划算法：,动态规划的状态转移方程如下 ：（这里只给出向右滑行的转移方程） f(0,startx,starty)=0 f(k,x,y)=maxf(k-1,x,y),f(k-1,x,y-1)+1,f(k-1,x,y-2)+2,f(k-1,x,y)+y-y （其中y为满足y=1或(x,y-1)上有障碍或y=y-ck的最大值）,令f(
6、k,x,y)=此人k次滑行后到达(x,y)方格时已经滑行的最长距离。,时间复杂度分析,现在来分析这个动态规划算法的时间复杂度：,显然，状态总数为O(KMN)，而每次状态转移在最坏情况下的时间复杂度为O(maxM,N)，因此总的时间复杂度为O(KMN*maxM,N)=O(1.6*109)，难以承受。,因此，我们需要对这个动态规划算法进行优化!,分析,分析,对于一个具体的例子k=2，x=1，c2=2可以列出如下等式：f(2,1,1)=maxf(1,1,1)f(2,1,2)=maxf(1,1,1)+1,f(1,1,2)f(2,1,3)=maxf(1,1,1)+2,f(1,1,2)+1,f(1,1,3
7、)f(2,1,4)=maxf(1,1,2)+2,f(1,1,3)+1,f(1,1,4),分析,如果我们定义一个序列a，使得ai=f(1,1,i)-i+1，则以上等式可以写成：f(2,1,1)=maxa1=maxa1f(2,1,2)=maxa1+1,a2+1=maxa1,a2+1f(2,1,3)=maxa1+2,a2+2,a3+2=maxa1,a2,a3+2f(2,1,4)=maxa2+3,a3+3,a4+3=maxa2,a3,a4+3,分析,现在，让我们加入对障碍物的考虑,分析,线段树专门计算区间内数据的最值,建立 O(M),查找 O(log2M),算法时间复杂度 O(KMNlog2M,N),
8、编程复杂度高,时间复杂度仍不能令人满意,应用基本数据结构队列,若ij且ai aj，则插入aj后可以将ai从队列中删除,队列中所有元素呈严格递减顺序,队列的操作,删除,队头指针加一,插入,查找,队头元素即为最大值,从队尾开始，依次删除所有不大于ai的a值，再将ai插入队尾,动画演示,(设ck=3),时间复杂度分析,一个元素最多被插入一次，删除一次,在一行中，插入与删除的总时间复杂度为O(maxM,N),每次询问最大值的时间复杂度仅为O(1),此算法的时间复杂度为O(KMN),非常优秀的算法,小结,动态规划,状态转移的时间复杂度太高,线段树,编程复杂度高,时间复杂度仍不能令人满意,队列,降低了时间
9、复杂度,减少了编程错误的可能性,总结,基本数据结构,易于实现,普遍适用,昨天,数据结构中的精华,理论经过数十年时间的检验,应用于算法中的诸多方面,今天,巧妙地解决了诸多问题,明天,现在还不为人所知的基本数据结构的应用将被发现和研究,总结,基本数据结构,高级数据结构,基本数据结构,回归,摒弃,局限性,灵活掌握基本数据结构及其操作,对某些高级数据结构有所了解,辨证关系,螺旋式发展,知识与思想得到升华,对整个数据结构知识的深刻领悟,谢谢！,欢迎大家提问！,算法步骤,输入N，a1，a2，a3，an 将a1，a2，a3，an按照从小到大的顺序排序，得到序列c1，c2，c3，cn，并记录下每个ai在新序列中的位置bi 在新的序列上建立双向链表 按照从an到a1的顺序依次处理每个元素 输出结果,算法步骤,以滑行次数K作为阶段进行动态规划 状态转移时，对于矩阵中的每一行： 队列置空 遇到障碍：队列置空，处理下一个元素 若队头元素与当前元素的下标相差大于ck ,删除队头元素 删除队尾所有不大于当前a值的元素 在队尾插入a值 队头a值即为队列中所有元素最大值 处理下一个元素,
