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