国家集训队2005论文集 黄源河

左偏树的特点及其应用

广东省中山市第一中学黄源河

【摘要】

本文较详细地介绍了左偏树的特点以及它的各种操作。

第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。

【关键字】左偏树可并堆优先队列

【目录】

一、引言 (2)

二、左偏树的定义和性质 (2)

2.1 优先队列，可并堆 (2)

2.1.1 优先队列的定义 (2)

2.1.2 可并堆的定义 (2)

2.2 左偏树的定义 (3)

2.3 左偏树的性质 (4)

三、左偏树的操作 (5)

3.1 左偏树的合并 (5)

3.2 插入新节点 (7)

3.3 删除最小节点 (8)

3.4 左偏树的构建 (8)

3.5 删除任意已知节点 (9)

3.6 小结 (12)

四、左偏树的应用 (13)

4.1 例——数字序列（Baltic 2004） (13)

五、左偏树与各种可并堆的比较 (15)

5.1 左偏树的变种——斜堆 (15)

5.2 左偏树与二叉堆的比较 (16)

5.3 左偏树与其他可并堆的比较 (16)

六、总结 (18)

【正文】

一、引言

优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。

二、左偏树的定义和性质

在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。

2.1优先队列，可并堆

2.1.1优先队列的定义

优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。

2.1.2可并堆的定义

可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作：

H ← Merge(H1,H2)

Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。

前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。

左偏树(Leftist Tree)是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针( left, right )外，还有两个属性：键值和距离(dist)。键值上面已经说过，是用于比较节点的大小。距离则是如下定义的：

节点i称为外节点(external node)，当且仅当节点i的左子树或右子树为空( left(i) = NULL或right(i) = NULL )；节点i的距离(dist(i))是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0；而空节点的距离规定为-1 (dist(NULL) = -1)。在本文中，有时也提到一棵左偏树的距离，这指的是该树根节点的距离。

左偏树满足下面两条基本性质：

[性质1] 节点的键值小于或等于它的左右子节点的键值。

即key(i)≤key(parent(i)) 这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1，我们可以知道左偏树的根节点是整棵树的最小节点，于是我们可以在O(1) 的时间内完成取最小节点操作。

[性质2] 节点的左子节点的距离不小于右子节点的距离。

即dist(left(i))≥dist(right(i)) 这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作（插入节点、删除最小节点）进行后维持堆性质。在后面我们就会看到它的作用。

这两条性质是对每一个节点而言的，因此可以简单地从中得出，左偏树的左右子树都是左偏树。

由这两条性质，我们可以得出左偏树的定义：左偏树是具有左偏性质的堆有序二叉树。

下图是一棵左偏树：

在前面一节中，本文已经介绍了左偏树的两个基本性质，下面本文将介绍左偏树的另外两个性质。

我们知道，一个节点必须经由它的子节点才能到达外节点。由于性质2，一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数，也就是说，我们有

[性质3] 节点的距离等于它的右子节点的距离加1。

即dist( i ) = dist( right( i ) ) + 1外节点的距离为0，由于性质2，它的右子节点必为空节点。为了满足性质3，故前面规定空节点的距离为-1。

我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。从图中我们可以看到它并不平衡，由于性质2的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。

下面我们来讨论左偏树的距离和节点数的关系。

[引理1] 若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。

证明：由性质2可知，当且仅当对于一棵左偏树中的每个节点i，都有dist(left(i)) = dist(right(i)) 时，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。

[定理1] 若一棵左偏树的距离为k，则这棵左偏树至少有2k+1-1个节点。

证明：由引理1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2k+1-1，所以距离为k的左偏树至少有2k＋1-1个节点。

作为定理1的推论，我们有：

[性质4] 一棵N个节点的左偏树距离最多为?log(N+1)? -1。

证明：设一棵N个节点的左偏树距离为k，由定理1可知，N ≥2k+1-1，因此k ≤?log(N+1)? -1。

有了上面的4个性质，我们可以开始讨论左偏树的操作了。

三、左偏树的操作

本章将讨论左偏树的各种操作，包括插入新节点、删除最小节点、合并左偏树、构建左偏树和删除任意节点。由于各种操作都离不开合并操作，因此我们先讨论合并操作。

3.1左偏树的合并

C ← Merge(A,B)

Merge( ) 把A,B两棵左偏树合并，返回一棵新的左偏树C，包含A和B中的所有元素。在本文中，一棵左偏树用它的根节点的指针表示。

在合并操作中，最简单的情况是其中一棵树为空（也就是，该树根节点指针为NULL）。这时我们只须要返回另一棵树。

若A和B都非空，我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树right(A) 和B了。

right(A) ← Merge(right(A), B)

合并了right(A) 和B之后，right(A) 的距离可能会变大，当right(A) 的距离大于left(A) 的距离时，左偏树的性质2会被破坏。在这种情况下，我们只须要交换left(A) 和right(A)。

若dist(left(A)) > dist(right(A))，交换left(A) 和right(A)

最后，由于right(A) 的距离可能发生改变，我们必须更新A的距离：

dist(A) ← dist(right(A)) + 1

不难验证，经这样合并后的树C符合性质1和性质2，因此是一棵左偏树。至此左偏树的合并就完成了。

下图是一个合并过程的示例：

合并流程

我们可以用下面的代码描述左偏树的合并过程：

下面我们来分析合并操作的时间复杂度。从上面的过程可以看出，每一次递归合并的开始，都需要分解其中一棵树，总是把分解出的右子树参加下一步的合并。根据性质3，一棵树的距离决定于其右子树的距离，而右子树的距离在每次分解中递减，因此每棵树A或B被分解的次数分别不会超过它们各自的距离。根据性质4，分解的次数不会超过?log(N1+1)? + ?log(N2+1)? -2，其中N1和N2分别为左偏树A和B的节点个数。因此合并操作最坏情况下的时间复杂度为O( ?log(N1+1)? + ?log(N2+1)? -2) = O(log N1 + log N2)。

3.2插入新节点

单节点的树一定是左偏树，因此向左偏树插入一个节点可以看作是对两棵左偏树的合并。下面是插入新节点的代码：

由于合并的其中一棵树只有一个节点，因此插入新节点操作的时间复杂度是O(logn)。

3.3 删除最小节点

由性质1，我们知道，左偏树的根节点是最小节点。在删除根节点后，剩下的两棵子树都是左偏树，需要把他们合并。删除最小节点操作的代码也非常简单：

由于删除最小节点后只需进行一次合并，因此删除最小节点的时间复杂度也为O(log n)。

3.4 左偏树的构建

将n 个节点构建成一棵左偏树，这也是一个常用的操作。

算法一

暴力算法——逐个节点插入，时间复杂度为O(n log

n)。

算法二 仿照二叉堆的构建算法，我们可以得到下面这种算法：

将n 个节点（每个节点作为一棵左偏树）放入先进先出队列。

不断地从队首取出两棵左偏树，将它们合并之后加入队尾。

当队列中只剩下一棵左偏树时，算法结束。

构建流程

下面分析算法二的时间复杂度。假设n=2k ，则：

前

2

n 次和并的是两棵只有1个节点的左偏树。 接下来的4

n 次合并的是两棵有2个节点的左偏树。 接下来的8n 次合并的是两棵有4个节点的左偏树。 ……

接下来的

i n 2

次合并的是两棵有2i-1个节点的左偏树。

合并两棵2i 个节点的左偏树时间复杂度为O(i )，因此算法二的总时间复杂

度为：∑==+-==?+++k i k i n O k n O i n O O n O n O n 1)())222(*()2*()3(*8)2(*4)1(*2。

3.5 删除任意已知节点

接下来是关于删除任意已知节点的操作。之所以强调“已知”，是因为这里所说的任意节点并不是根据它的键值找出来的，左偏树本身除了可以迅速找到最小节点外，不能有效的搜索指定键值的节点。故此，我们不能要求：请删除所有键值为100的节点。

前面说过，优先队列是一种容器。对于通常的容器来说，一旦节点被放进去以后，容器就完全拥有了这个节点，每个容器中的节点具有唯一的对象掌握它的

拥有权（ownership）。对于这种容器的应用，优先队列只能删除最小节点，因为你根本无从知道它的其它节点是什么。

但是优先队列除了作为一种容器外还有另一个作用，就是可以找到最小节点。很多应用是针对这个功能的，它们并没有将拥有权完全转移给优先队列，而是把优先队列作为一个最小节点的选择器，从一堆节点中依次将它们选出来。这样一来节点的拥有权就可能同时被其它对象掌握。也就是说某个节点虽不是最小节点，不能从优先队列那里“已知”，但却可以从其它的拥有者那里“已知”。

这种优先队列的应用也是很常见的。设想我们有一个闹钟，它可以记录很多个响铃时间，不过由于时间是线性的，铃只能一个个按先后次序响，优先队列就很适合用来作这样的挑选。另一方面使用者应该可以随时取消一个“已知”的响铃时间，这就需要进行任意已知节点的删除操作了。

我们的这种删除操作需要指定被删除的节点，这和原来的删除根节点的操作是兼容的，因为根节点肯定是已知的。上面已经提过，在删除一个节点以后，将会剩下它的两棵子树，它们都是左偏树，我们先把它们合并成一棵新的左偏树。

p ← Merge(left(x), right(x))

现在p指向了这颗新的左偏树，如果我们删除的是根节点，此时任务已经完成了。不过，如果被删除节点x不是根节点就有点麻烦了。这时p指向的新树的距离有可能比原来x的距离要大或小，这势必有可能影响原来x的父节点q的距离，因为q现在成为新树p的父节点了。于是就要仿照合并操作里面的做法，对q的左右子树作出调整，并更新q的距离。这一过程引起了连锁反应，我们要顺着q的父节点链一直往上进行调整。

新树p的距离为dist(p)，如果dist(p)+1等于q的原有距离dist(q)，那么不管

p是q的左子树还是右子树，我们都不需要对q进行任何调整，此时删除操作也

就完成了。

如果dist(p)+1小于q的原有距离dist(q)，那么q的距离必须调整为dist(p)+1，而且如果p是左子树的话，说明q的左子树距离比右子树小，必须交换子树。由于q的距离减少了，所以q的父节点也要做出同样的处理。

剩下就是另外一种情况了，那就是p的距离增大了，使得dist(p)+1大于q 的原有距离dist(q)。在这种情况下，如果p是左子树，那么q的距离不会改变，

此时删除操作也可以结束了。如果p是右子树，这时有两种可能：一种是p的距离仍小于等于q的左子树距离，这时我们直接调整q的距离就行了；另一种是p 的距离大于q的左子树距离，这时我们需要交换q的左右子树并调整q的距离，交换完了以后q的右子树是原来的左子树，它的距离加1只能等于或大于q的原有距离，如果等于成立，删除操作可以结束了，否则q的距离将增大，我们还要对q的父节点做出相同的处理。

删除任意已知节点操作的代码如下：

下面分两种情况讨论删除操作的时间复杂度。

情况1：p的距离减小了。在这种情况下，由于q的距离只能缩小，当循环结束时，要么根节点处理完了，q为空；要么p是q的右子树并且dist(p)+1=dist(q)；如果dist(p)+1>dist(q)，那么p一定是q的左子树，否则会出现q的右子树距离缩小了，但是加1以后却大于q的距离的情况，不符合左偏树的性质3。不论哪种情况，删除操作都可以结束了。注意到，每一次循环，p的距离都会加1，而在循环体内，dist(p)+1最终将成为某个节点的距离。根据性质4，任何的距离都不会超过logn，所以循环体的执行次数不会超过log n。

情况2：p的距离增大了。在这种情况下，我们将必然一直从右子树向上调整，直至q为空或p是q的左子树时停止。一直从右子树升上来这个事实说明了循环的次数不会超过log n（性质4）。

最后我们看到这样一个事实，就是这两种情况只会发生其中一个。如果某种情况的调整结束后，我们已经知道要么q为空，要么dist(p)+1 = dist(q)，要么p

是q 的左子树。这三种情况都不会导致另一情况发生。直观上来讲，如果合并后的新子树导致了父节点的一系列距离调整的话，要么就一直是往小调整，要么是一直往大调整，不会出现交替的情况。

我们已经知道合并出新子树p 的复杂度是O(logn)，向上调整距离的复杂度也是O(logn)，故删除操作的最坏情况的时间复杂度是O(log n)。如果左偏树非常倾斜，实际应用情况下要比这个快得多。

3.6 小结

本章介绍了左偏树的各种操作，我们可以看到，左偏树作为可并堆的实现，它的各种操作性能都十分优秀，且编程复杂度比较低，可以说是一个“性价比”十分高的数据结构。左偏树之所以是很好的可并堆实现，是因为它能够捕捉到具有堆性质的二叉树里面的一些其它有用信息，没有将这些信息浪费掉。根据堆性质，我们知道，从根节点向下到任何一个外节点的路径都是有序的。存在越长的路径，说明树的整体有序性越强，与平衡树不同（平衡树根本不允许有很长的路径），左偏树尽大约一半的可能保留了这个长度，并将它甩向左侧，利用它来缩短节点的距离以提高性能。这里我们不进行严格的讨论，左偏树作为一个例子大致告诉我们：放弃已有的信息意味着算法性能上的牺牲。下面是最好的左偏树：有序表（插入操作是按逆序发生的，自然的有序性被保留了）和最坏的左偏树：平衡树（插入操作是按正序发生的，自然的有序性完全被放弃了）。

1

2

3

4

5

6

7

有序表 平衡树 1 2

3 4 5 6 7

四、左偏树的应用

4.1例——数字序列（Baltic 2004）

[问题描述]*

给定一个整数序列a1, a2, … , a n，求一个不下降序列b1≤ b2≤…≤ b n，使得数列{a i}和{b i}的各项之差的绝对值之和|a1 - b1| + |a2 - b2| + … + |a n - b n| 最小。

[数据规模] 1 ≤ n ≤ 106, 0 ≤ a i≤ 2*109

[初步分析]

我们先来看看两个最特殊的情况：

1．a[1]≤a[2]≤…≤a[n]，在这种情况下，显然最优解为b[i]=a[i]；

2．a[1]≥a[2]≥…≥a[n]，这时，最优解为b[i]=x，其中x是数列a的中位数?。

于是我们可以初步建立起这样一个思路：

把1…n划分成m个区间：[q[1],q[2]-1]，[q[2],q[3]-1]，……，[q[m],q[m+1]-1]?。每个区间对应一个解，b[q[i]] = b[q[i]+1] = … = b[q[i+1]-1] = w[i]，其中w[i] 为a[q[i]], a[q[i]+1], ... , a[q[i+1]-1] 的中位数。

显然，在上面第一种情况下m=n，q[i]=i；在第二种情况下m=1，q[1]=1。

这样的想法究竟对不对呢？应该怎样实现？

若某序列前半部分a[1], a[2], …, a[n] 的最优解为(u,u,…,u)，后半部分a[n+1], a[n+2], ... , a[m] 的最优解为(v,v,…,v)，那么整个序列的最优解是什么呢？若u≤v，显然整个序列的最优解为(u,u,…,u,v,v,…,v)。否则，设整个序列的最优解为(b[1],b[2],…,b[m])，则显然b[n]≤u（否则我们把前半部分的解(b[1],b[2],…,b[n]) 改为(u,u,…,u)，由题设知整个序列的解不会变坏），同理b[n+1]≥v。接下来，我们将看到下面这个事实：

对于任意一个序列a[1],a[2],…,a[n]，如果最优解为(u,u,…,u)，那么在满足u≤u′≤b[1] 或b[n]≤u′≤u的情况下，(b[1],b[2],…,b[n]) 不会比(u′,u′,…,u′) 更优。

我们用归纳法证明u≤u′≤b[1] 的情况，b[n]≤u′≤u的情况可以类似证明。

当n=1时，u=a[1]，命题显然成立。

当n>1时，假设对于任意长度小于n的序列命题都成立，现在证明对于长度为n的序列命题也成立。首先把(b[1], b[2], … b[n]) 改为(b[1], b[1], … b[1])，这一改动将不会导致解变坏，因为如果解变坏了，由归纳假设可知a[2],a[3],…,a[n]的中位数w>u，这样的话，最优解就应该为(u,u,…,u,w,w,…,w)，矛盾。然后我们再把(b[1],b[1],…,b[1])改为(u′,u′,…,u′)，由于| a[1]- x | + | a[2]- x | + … + | a[n]- x | 的几何意义为数轴上点x到点a[1], a[2], … a[n]的距离之和，且

*题目来源：Baltic OI 2004 Day 1, Sequence 本文对原题略微做了改动

?为了方便讨论和程序实现，本文中提到的中位数，都是指数列中第?n/2?大的数

?这里我们认为q[m+1] = n+1

u≤u′≤b[1]，显然点u′到各点的距离之和不会比点b[1]到各点的距离之和大，也就是说，(b[1],b[1],…,b[n]) 不会比(v,v,…,v) 更优。（证毕）

再回到之前的论述，由于b[n]≤u，作为上述事实的结论，我们可以得知，将(b[1],b[2],…,b[n])改为(b[n],b[n],…,b[n])，再将(b[n+1],b[n+2],…,b[m])改为(b[n+1],b[n+1],…,b[n+1])，并不会使解变坏。也就是说，整个序列的最优解为(b[n],b[n],…,b[n],b[n+1],b[n+1],…,b[n+1])。再考虑一下该解的几何意义，设整个序列的中位数为w，则显然令b[n]=b[n+1]=w将得到整个序列的最优解，即最优解为(w,w,…,w)。

分析到这里，我们一开始的想法已经有了理论依据，算法也不难构思了。

[算法描述]

延续我们一开始的思路，假设我们已经找到前k个数a[1], a[2], … , a[k] (kw[m+1]，我们需要将最后两个区间合并，并找出新区间的最优解（也就是序列a中，下标在这个新区间内的各项的中位数）。重复这个合并过程，直至w[1]≤w[2]≤…≤w[m]时结束，然后继续处理下一个数。

这个算法的正确性前面已经论证过了，现在我们需要考虑一下数据结构的选取。算法中涉及到以下两种操作：合并两个有序集以及查询某个有序集内的中位数。能较高效地支持这两种操作的数据结构有不少，一个比较明显的例子是二叉检索树(BST)，它的询问操作复杂度是O(logn)，但合并操作不甚理想，采用启发式合并，总时间复杂度为O(n log2n)。

有没有更好的选择呢？通过进一步分析，我们发现，只有当某一区间内的中位数比后一区间内的中位数大时，合并操作才会发生，也就是说，任一区间与后面的区间合并后，该区间内的中位数不会变大。于是我们可以用最大堆来维护每个区间内的中位数，当堆中的元素大于该区间内元素的一半时，删除堆顶元素，这样堆中的元素始终为区间内较小的一半元素，堆顶元素即为该区间内的中位数。考虑到我们必须高效地完成合并操作，左偏树是一个理想的选择*。左偏树的询问操作时间复杂度为O(1)，删除和合并操作时间复杂度都是O(logn)，而询问操作和合并操作少于n次，删除操作不超过n/2次（因为删除操作只会在合并两个元素个数为奇数的堆时发生），因此用左偏树实现，可以把算法的时间复杂度降为O(n log n)。

[小结]

这道题的解题过程对我们颇有启示。在应用左偏树解题时，我们往往会觉得题目无从下手，甚至与左偏树毫无关系，但只要我们对题目深入分析，加以适当的转化，问题终究会迎刃而解。这需要我们具有敏捷的思维以及良好的题感。

用左偏树解本题，相比较于前面BST的解法，时间复杂度和编程复杂度更低，这使我们不得不感叹于左偏树的神奇威力。这不是说左偏树就一定是最好的解法，就本题来说，解法有很多种，光是可并堆的解法，就可以用多种数据结构来实现，但左偏树相对于它们，还是有一定的优势的，这将在下一章详细讨论。

*前面介绍的左偏树是最小堆，但在本题中，显然只需把左偏树的性质稍做修改，就可以实现最大堆了

五、左偏树与各种可并堆的比较

我们知道，左偏树是一种可并堆的实现。但是为什么我们要用左偏树实现可并堆呢？左偏树相对于其他可并堆有什么优点？本章将就这个问题展开讨论，介绍各种可并堆的特点，并对它们做出比较。

5.1左偏树的变种——斜堆

这里我们要介绍左偏树的一个变种——斜堆(Skew Heap)。斜堆是一棵堆有序的二叉树，但是它不满足左偏性质，或者说，斜堆根本就没有“距离”这个概念——它不需要记录任何一个节点的距离。从结构上来说，所有的左偏树都是斜堆，但反之不然。

类似于左偏树，斜堆的各种操作也是在合并操作的基础上完成的，因此这里只介绍斜堆的合并操作，其他操作读者都可以仿照左偏树完成。

斜堆合并操作的递归合并过程和左偏树完全一样。假设我们要合并A和B 两个斜堆，且A的根节点比B的根节点小，我们只需要把A的根节点作为合并后新堆的根节点，并将A的右子树与B合并。由于合并都是沿着最右路径进行的，经过合并之后，新堆的最右路径长度必然增加，这会影响下一次合并的效率。为了解决这一问题，左偏树在进行合并的同时，检查最右路径节点的距离，并通过交换左右子树，使整棵树的最右路径长度非常小。然而斜堆不记录节点的距离，那么应该怎样维护最右路径呢？我们采取的办法是，从下往上，沿着合并的路径，在每个节点处都交换左右子树。

下面是斜堆合并操作的代码：

斜堆的这种维护方法也是行之有效的。通过不断交换左右子树，斜堆把最右路径甩向左边了。可以证明，斜堆合并操作的平摊时间复杂度为O(log n)。这里略去详细的复杂度分析，感兴趣的读者可以自行参考相关的资料。

前面说过，斜堆的其他各种操作都和左偏树类似，因此斜堆各项操作的平摊时间复杂度都与左偏树相同。在空间上，由于斜堆不用记录节点的距离，因此它比左偏树的空间需求小一点。至于编程复杂度，两者都十分的低，不过斜堆的代码还是要比左偏树稍微简洁一些。至于斜堆的不足，大概可以算是它单次合并操

作的时间复杂度可能退化为O(n)，不过通常这并不影响算法的总时间复杂度。

总的来说，斜堆作为左偏树的变种，与左偏树并无优劣之分。在斜堆能派上用场的地方，左偏树同样能出色地实现算法。斜堆与左偏树之间的关系，可以类比于伸展树与A VL树之间的关系，只不过前两者的编程复杂度，并没有多大的差别。

5.2左偏树与二叉堆的比较

二叉堆大概是我们最常用的一种优先队列了，它具有简洁，高效的特点，应用十分广泛。二叉堆和左偏树相比，除了合并操作外的各种操作，时间复杂度都一样，但在实际测试中，二叉堆往往比左偏树快一些。在空间上，由于二叉堆是完全二叉树，用数组表示法，可以剩下左右子树指针的空间，在这点上左偏树又吃了一亏。

介绍了二叉堆的优点，下面的这两个缺点也是不容忽视的：

1．在进行插入、删除等操作后，二叉堆中元素的物理位置会发生改变。

2．二叉堆的合并操作太慢，时间复杂度高达O(n)。

当元素本身所占空间比较大时，频繁地移动元素物理位置将会影响时间效率。而有些时候，我们需要随时掌握某些元素的物理位置，以便对它进行访问或修改（比如实现删除任意已知节点操作），这时，二叉堆的第一个缺点将给我们造成一定的麻烦，我们不得不通过增加元素指针等手段来解决这个问题。而二叉堆合并效率的低下则是由其本身性质所造成的，采用启发式合并可以作为大多数情况下的一个优化，但效果仍不能令人满意。

至于二叉堆空间上的优势，也不是绝对的。数组表示法并不是在任何场合都适用的，比如当我们需要动态维护多个优先队列的时候，二叉堆不得不使用传统的指针表示法，这时二叉堆和左偏树在空间上就相差无几了。

二叉堆的上述特点，决定了它不适合作为可并堆的实现。客观的说，需要实现可并堆的题目在竞赛中并不多见，不过当我们遇到这类题目或者某些特殊的情况时，左偏树将会是比二叉堆更好的选择。

5.3 左偏树与其他可并堆的比较

前面已经提到过，可并堆可以用多种数据结构实现，左偏树并非唯一的选择。二项堆，Fibonacci堆都是时间效率十分优秀的可并堆。

二项堆是由若干棵深度不同的二项树组成的森林。深度为k的二项树B k由两棵二项树B k-1连接根节点而成，有2k个节点，并且满足堆性质。二项树组成二项堆的形式可以看作总节点数n的二进制表示形式，两个二项堆的合并可以看作二进制数的加法，这点很有启发意义。与左偏树类似，二项堆的各种操作也是在合并操作的基础上完成的。二项堆的结构和性质决定了它可以很高效地完成合

并操作，与左偏树相比，虽然复杂度相同，但一般实际情况下二项堆比较快。但二项树实现取最小节点操作需要检查所有二项树的根节点，因此这项操作时间复杂度比左偏树高*。

Fibonacci堆是一个很复杂的数据结构，与二项堆一样，它也是由一组堆有序的树构成的。所不同的是，Fibonacci堆的树不一定是二项树，而且这些树是无序的，且树中兄弟节点的联系用双向循环链表来表示。Fibonacci堆实现插入操作和合并操作只是简单地将两个Fibonacci堆的根表连在一起，因此这两个操作比其他可并堆都快。但在删除操作时，我们需要对Fibonacci堆进行维护，合并所有度数相同的树，这一步异常复杂，并且是最慢的。

有关二项堆和Fibonacci堆的详细介绍，有兴趣的读者可以参考相关资料，本文不再赘述。下表列出了各种可并堆的各项操作的时间复杂度?，已及它们的空间需求和编程复杂度。

从表中我们可以看出，Fibonacci堆的时间复杂度非常低，如果我们不需要进行频繁的删除操作，用Fibonacci堆实现可并堆将会降低算法的时间复杂度。但实际上，删除操作往往是很重要的操作，而Fibonacci堆的删除操作比表中其它可并堆都慢，至于它的空间需求，也大得使人望而却步。更槽糕的是Fibonacci 堆的编程复杂度太高了，在竞赛中使用实在是不理智的行为。

至于二项堆，虽然各项操作的时间效率都十分优秀，但空间需求和编程复杂度仍然比不上左偏树。和左偏树相比，二项堆在时间效率上的优势微乎其微，用左偏树代替二项堆，的确会牺牲一些算法性能，但换来的却是简洁的代码，便于实现和调试的程序。在时间有限的竞赛中，左偏树无疑是更好的选择。

最后，我们应该认识到，虽然二项堆和Fibonacci堆某些操作的时间复杂度比左偏树低，但是在实际应用中，那些时间复杂度较高的操作往往会成为算法的瓶颈。比如前面的例题《数字序列》，改用二项堆或Fibonacci堆实现，总时间复杂度仍为O(n log n)，并不能起到降低算法时间复杂度的作用，实现难度反而增加了不少。

*这里其实有一个办法可以解决这个问题，就是随时记录最小节点，并只在插入、删除以及合并等操作进行的时候更新该记录，这样二项堆的取最小节点操作时间复杂度可以降为O(1)

?表中Fibonacci堆的“删除最小节点”和“删除任意节点”两个操作的时间复杂度均为平摊时间复杂度，而二项堆“插入”操作的平均时间复杂度为O(1)，表中给出的是最坏时间复杂度

六、总结

至此，我们已经对左偏树有了深刻的认识。左偏树在时间效率上不如二项堆和Fibonacci堆，在空间效率上不如二叉堆，这样看来左偏树没有任何独树一帜的地方，似乎是个相当平庸的数据结构，但其实这正是左偏树的优势所在。正所谓“鱼与熊掌不可兼得”，时间复杂度、空间复杂度和编程复杂度，这三者之间很多时候是矛盾的。Fibonacci堆时间复杂度最低，但编程复杂度让人无法接受；二叉堆的空间复杂度和编程复杂度都很低，但时间复杂度却是它的致命弱点。左偏树很好地协调了三者之间的矛盾，并且在存储性质上，没有二叉堆那样的缺陷，因此左偏树的适用范围十分广。左偏树不但可以高效方便地实现可并堆，更可以作为二叉堆的替代品，应用于各种优先队列，很多时候甚至比二叉堆更方便。

【感谢】

感谢余江伟同学及阮志远老师的热心帮助和修改意见。

【参考文献】

[1] 傅清祥，王晓东算法与数据结构（第二版）电子工业出版社

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

Introduction to Algorithms (Second Edition)The MIT Press

[3] Mark Allen Weiss Data Structures and Algorithm Analysis in C (Second

Edition) Pearson Education

【附录】

附录I ：例题《数字序列》的原题

SEQUENCE

Short formulation. The number sequence is given. Your task is to construct the increasing sequence that approximates the given one in the best way. The best approximating sequence is the sequence with the least total deviation from the given sequence.

More precisely. Let t1, t2, …, t N is the given number sequence. Your task is to construct the increasing number sequence z1 < z2 < …< z N .

The sum |t1 - z1| + |t2 - z2| + … + |t N - z N| should be a minimal feasible.

Input

There is the integer N (1≤N≤1000000) in the first line of input file seq.in. Each of the next N lines contains single integer – the given sequence element. There is t K in the (K+1)-th line. Any element is satisfying t o relation 0≤t K≤2000000000.

Output

The first line of output file seq.out must contain the single integer –the minimal possible total deviation. Each of the next N lines must contain single integer – the recurrent element of the best approximating sequence.

If there are several solutions, your program must output any one sequence with a least total deviation.

Example

附录II ：例题《数字序列》左偏树解法的程序

PROGRAM Seq_LeftistTree;

TyPe

node=

record

dist:byte;

key,left,right:longint;

end;

VaR

nd:array[0..1000000]of node;

stk,q:array[0..1000000]of longint;

n,cl,i:longint;

Function merge(a,b:longint):longint;

var

c:longint;

begin

if (a=0)or(b<>0)and(nd[a].key

begin

c:=a;

a:=b;

b:=c;

end;

merge:=a;

if b=0 then exit;

nd[a].right:=merge(nd[a].right,b);

if nd[nd[a].left].dist

c:=nd[a].left;

nd[a].left:=nd[a].right;

nd[a].right:=c;

end;

nd[a].dist:=nd[nd[a].right].dist+1;

end;

Procedure print;

var

tot,i,j:longint;

begin

tot:=0;

for i:=1 to cl do

for j:=q[i-1]+1 to q[i] do

inc(tot,abs(nd[j].key-nd[stk[i]].key));

writeln(tot);

end;

国家集训队2004论文集 肖天

“分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。

国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营

国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营许可证》换发及变更的通知 【法规类别】旅游综合规定 【发文字号】旅管理函[2008]16号 【发布部门】国家旅游局 【发布日期】2008.02.02 【实施日期】2008.02.02 【时效性】现行有效 【效力级别】部门规范性文件 国家旅游局质量规范与管理司关于进一步规范《国际旅行社业务经营许可证》换发及变 更的通知 （旅管理函〔2008〕16号） 各省、自治区、直辖市旅游局（委）： 为了进一步规范《国际旅行社业务经营许可证》的换发和变更，现根据《旅行社管理条例》及实施细则，就有关事项通知如下： 一、《国际旅行社业务经营许可证》有效期为三年，国际旅行社应当在《国际旅行社业务经营许可证》到期之日前的三个月内，持许可证到原颁证机关（国家旅游局）换发。 二、《国际旅行社业务经营许可证》在有效期内需要变更许可证载明事项内容的，应当在完成工商部门的变更登记之日起的相关规定期限内，持相关材料和许可证到原颁证机

关申请换发。 三、《国际旅行社业务经营许可证》损坏的，应当在相关规定期限内将损坏《国际旅行社业务经营许可证》正、副本上交颁证机关申请换发。 四、《国际旅行社业务经营许可证》遗失的，应当在遗失之日起的相关规定期限内在当地公开发行的报纸上刊登启事，并提供报纸原件向颁证机关申请换发。 五、《国际旅行社业务经营许可证》涉及变更事项的，各省（自治区、直辖市）旅游局须认真审验相关材料，并在《国际旅行社变更事项备案登记表》内签章。 附件：1、《国际旅行社业务经营许可证》变更事项所需提供材料的具体规定 2、国际旅行社变更事项备案登记表 国家旅游局质量规范与管理司 2008年2月2日附件1： 《国际旅行社业务经营许可证》变更事项 所需提供材料的具体规定

NOI国家集训队论文分类(至2008)(摘抄自C博客)

摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Pólya原理及其应用》 2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 - 周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Pólya计数法的应用》 数位问题 2009 - 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004 - 薛矛：《解决动态统计问题的两把利刃》 2007 - 余江伟：《如何解决动态统计问题》 博弈 2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》2007 - 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》 母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007 - 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005 - 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003 - 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题 2003 - 张宁：《猜数问题的研究:<聪明的学生>一题的推广》

2006 - 龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 - 何林：《数据关系的简化》 2006 - 朱晨光：《基本数据结构在信息学竞赛中的应用》 2007 - 何森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001 - 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 - 黄刚：《数据结构的联合》 块状链表 2005 - 蒋炎岩：《数据结构的联合——块状链表》 2008 - 苏煜《对块状链表的一点研究》 动态树 2006 - 陈首元：《维护森林连通性——动态树》 2007 - 袁昕颢：《动态树及其应用》 左偏树 2005 - 黄源河：《左偏树的特点及其应用》 跳表 2005 - 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009 - 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree》 线段树 2004 - 林涛：《线段树的应用》 单调队列 2006 - 汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 - 杨思雨：《伸展树的基本操作与应用》

国家集训队2001论文集 毛子青

动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。

国家旅游局关于印发《导游IC卡发放管理办法(试行)》的通知

国家旅游局关于印发《导游IC卡发放管理办法(试行)》的通 知 【法规类别】旅游服务机构导游人员管理 【发文字号】旅办发[2010]198号 【修改依据】国家旅游局办公室关于修订《导游IC卡发放管理办法(试行)》等事项的通知 【发布部门】国家旅游局 【发布日期】2010.12.28 【实施日期】2010.12.28 【时效性】已被修改 【效力级别】部门规范性文件 国家旅游局关于印发《导游IC卡发放管理办法（试行）》的通知 （旅办发（2010）198号） 各省、自治区、直辖市旅游局（委）： 为规范和加强导游IC卡发放管理工作，健全导游IC卡使用管理制度，现将《导游IC卡发放管理办法（试行）》，印发给你们，并就有关事项通知如下： 一、自2011年1月1日起，由各省、自治区、直辖市和新疆生产建设兵团旅游局（委）（以下简称“省级旅游局”）负责本地区（系统）导游IC卡的制作、颁发和监督检查工作；原有A版制版系统城市不再发放和制作导游IC卡，继续承担IC卡年审职责，系统

保留年审功能；原有B版系统的城市职责和系统功能不变。 二、请各省级旅游局通知并督促使用A版系统城市旅游局立即停止制作发放IC卡，协调配合系统开发维护单位完成对系统软硬件的调整和剩余导游IC卡的清理回收工作，于2010年12月31日前将清理情况书面报告我局。 三、自本通知发出之日起，我局只向各省级旅游局发放导游IC卡，请各省级旅游局在开展导游IC卡系统调整和IC卡清理回收工作的同时，研究制订相关管理办法，与清理工作一并报我局备案。 四、换卡、补卡收取成本费的标准为30元/张（含卡、卡套和加工制作、邮寄等全部费用），汇付账户和具体方式另行通知。 五、我局将对各省导游IC卡发放管理工作进行不定期抽查和调研工作。 《导游IC卡发放管理办法（试行）》和此通知执行中有重要情况和意见，请及时报告我局。 特此通知。 联系人：卓超美 联系电话：（010）65201338 国家旅游局办公室 二Ｏ一Ｏ年十二月二十八日 导游IC卡发放管理办法（试行） 第一条依据《导游人员管理条例》，为规范导游IC卡的发放管理，制定本办法。

国家集训队2005论文集 黄源河

左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (5) 3.1 左偏树的合并 (5) 3.2 插入新节点 (7) 3.3 删除最小节点 (8) 3.4 左偏树的构建 (8) 3.5 删除任意已知节点 (9) 3.6 小结 (12) 四、左偏树的应用 (13) 4.1 例——数字序列（Baltic 2004） (13) 五、左偏树与各种可并堆的比较 (15) 5.1 左偏树的变种——斜堆 (15) 5.2 左偏树与二叉堆的比较 (16) 5.3 左偏树与其他可并堆的比较 (16) 六、总结 (18)

【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。

国家旅游局公告2006年第1号——欠缴质保金的旅行社名单

国家旅游局公告2006年第1号——欠缴质保金的旅行社名单 【法规类别】旅游服务机构导游人员管理 【发文字号】国家旅游局公告2006年第1号 【发布部门】国家旅游局 【发布日期】2006.01.04 【实施日期】2006.01.04 【时效性】现行有效 【效力级别】XE0303 国家旅游局公告 （2006年第1号） 根据我局《关于进一步做好旅行社质量保证金回收工作的通知》（[2005]105号）的要求，各地旅行社补缴质量保证金的工作基本结束。目前，全国仍有74家旅行社未能按时补齐质保金，其中组团社有16家，国际社有58家。现将74家旅行社的名单公示如下。请上述旅行社在2006年2月28日前补齐质保金，逾期将按有关规定给予降类或注销处理。 特此公告。 附：欠缴质保金的旅行社名单 国家旅游局

二00六年一月四日 附： 一、组团社名称及许可证编号（16家） 1 珠海经济特区环球国际旅行社L-GD-GJ00024 2 台山中国旅行社L-GD-GJ00139 3 湛江市旅游总公司L-GD-GJ00017 4 黑龙江省中国青年旅行社L-HLJ-GJ00009 5 伊春中国国际旅行社L-HLJ-GJ00011 6 海南港澳国际旅行社有限公司L-HAN-GJ00006 7 包头中国国际旅行社L-NMG-GJ00008 8 喀什国际旅行社有限责任公司L-XJ-GJ00006 9 开封中国国际旅行社L-HEN-GJ00006 10 广西玉林国际旅行社有限公司L-GX-GJ00024 11 北海中国国际旅行社有限公司L-GX-GJ00005 12 青海省中国青年旅行社有限责任公司L-QH-GJ00003 13 甘肃海外旅游总公司L-GS-GJ0

国家旅游局32号令

国家旅游局32号令：《旅游投诉处理办法》自2010年7月1日起施行2010-5-19 15:12:43国家旅游局政策法规司字号：[大中小]选择背景色： 国家旅游局令 第32号 《旅游投诉处理办法》已经2010年1月4日国家旅游局第1次局长办公会议审议通过。现予公布，自2010年7月1日起施行。 国家旅游局局长：邵琪伟 二○一○年五月五日 旅游投诉处理办法 第一章总则 第一条为了维护旅游者和旅游经营者的合法权益，依法公正处理旅游投诉，依据《中华人民共和国消费者权益保护法》、《旅行社条例》、《导游人员管理条例》和《中国公民出国旅游管理办法》等法律、法规，制定本办法。 第二条本办法所称旅游投诉，是指旅游者认为旅游经营者损害其合法权益，请求旅游行政管理部门、旅游质量监督管理机构或者旅游执法机构（以下统称“旅游投诉处理机构”），对双方发生的民事争议进行处理的行为。 第三条旅游投诉处理机构应当在其职责范围内处理旅游投诉。 地方各级旅游行政主管部门应当在本级人民政府的领导下，建立、健全相关行政管理部门共同处理旅游投诉的工作机制。 第四条旅游投诉处理机构在处理旅游投诉中，发现被投诉人或者其从业人员有违法或犯罪行为的，应当按照法律、法规和规章的规定，作出行政处罚、向有关行政管理部门提出行政处罚建议或者移送司法机关。 第二章管辖 第五条旅游投诉由旅游合同签订地或者被投诉人所在地县级以上地方旅游投诉处理机构管辖。 需要立即制止、纠正被投诉人的损害行为的，应当由损害行为发生地旅游投诉处理机构管辖。 第六条上级旅游投诉处理机构有权处理下级旅游投诉处理机构管辖的投诉案件。 第七条发生管辖争议的，旅游投诉处理机构可以协商确定，或者报请共同的上级旅游投诉处理机构指定管辖。 第三章受理

历年国家集训队论文题目

1999年 陈宏- 数据结构的选择与算法效率——从IOI98试题PICTURE谈起 来煜坤- 把握本质，灵活运用——动态规划的深入探讨 齐鑫- 搜索方法中的剪枝优化 邵铮- 数学模型的建立、比较和应用 石润婷- 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性睢》?- 准确性、全面性、美观性——测试数据设计中的三要素 周咏基- 论随机化算法的原理与设计 2000年 陈彧- 信息学竞赛中的思维方法 方奇- 动态规划 高寒蕊- 递推关系的建立及在信息学竞赛中的应用 郭一- 数学模型及其在信息学竞赛中的应用 江鹏- 探索构造法解题模式 李刚- 动态规划的深入讨论 龙翀- 解决空间规模问题的几种常用的存储结构 骆骥- 数学模型的建立和选择 施遥- 人工智能在围棋程序中的应用 肖洲- 数据结构的在程序设计中的应用 谢婧- 规模化问题的解题策略 徐串- 论程序的调试技巧 徐静- 图论模型的建立与转化 杨江明- 论数学策略在信息学问题中的应用 杨培- 非最优化算法初探 张辰- 动态规划的特点及其应用 张力- 类比思想在解题中的应用 张一飞- 冗繁削尽留清瘦——浅谈信息的充分利用 2001年 高寒蕊- 从圆桌问题谈数据结构的综合运用 符文杰- Pólya原理及其应用 高岳- 中等硬度解题报告 江鹏- 从一道题目的解法试谈网络流的构造与算法 刘汝佳- 搬运工问题的启示 李益明- 计算几何的相关问题 李源- 树的枚举 骆骥- 由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性毛子青- 动态规划算法的优化技巧 俞玮- 基本动态规划问题的扩展 张一飞- 求N!的高精度算法 2002年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用

国家旅游局关于放宽旅行社设立服务网点政策有关事项的通知

国家旅游局关于放宽旅行社设立服务网点政策有关事项的通知 (旅发〔2015〕211号) 各省、自治区、直辖市旅游委、局，新疆生产建设兵团旅游局： 为贯彻落实《关于促进旅游业改革发展的若干意见》(国发〔2014〕31号)精神，现就放宽旅行社设立服务网点政策有关事项通知如下： 一、放宽设立服务网点区域范围 允许设立社在所在地的省(市、区)行政区划内及其分社所在地的设区的市的行政区划内设立服务网点，不受数量限制。 在设立社所在地的省(市、区)行政区划内设立服务网点的，设立社向服务网点所在地工商行政管理部门办理服务网点设立登记后，应当在3个工作日内，持设立社营业执照副本、设立社旅行社业务经营许可证副本、服务网点的营业执照、服务网点经理的履历表和身份证明向服务网点所在地与工商登记同级的旅游主管部门备案。 旅行社在其分社所在地的设区的市的行政区划内设立服务网点的，设立社向服务网点所在地工商行政管理部门办理服务网点设立登记后，应当在3个工作日内，持设立社营业执照副本、设立社旅行社业务经营许可证副本、分社的营业执照、旅行社分社备案登记证明、服务网点的营业执照、服务网点经理的履历表和身份证明向服务网点所在地与工商登记同级的旅游主管部门备案。 二、落实分社和服务网点设立政策 各地要认真学习贯彻《国务院关于促进旅游业改革发展的若干意见》(国发〔2014〕31号)，切实按照《旅行社条例》及本通知要求，依法依规做好分社和服务网点的备案工作，不得增设或变相增设旅行社设立分社、服务网点的政策障碍。

各省级旅游主管部门要积极开展针对市、县级旅游主管部门的培训指导和监督检查，发现不依法依规开展分社和服务网点备案工作的，要及时予以纠正。 三、加强对旅行社分社和服务网点的服务监管 各地要进一步引导旅行社增强风险管控意识，审慎确定分支机构设立的数量和规模;督促设立社切实加强对分社和服务网点的管理和人员培训，依法承担经营活动的责任和后果;要加强旅游质监执法人员的培训，建立健全对旅行社分社、服务网点的事中事后监管机制，改进服务监管手段，提升服务监管水平，对发现的违法违规行为，要主动协同设立社所在地旅游主管部门进行依法查处。 国家旅游局此前发布的相关规定与本通知不一致的，依照本通知执行。 国家旅游局 2015年9月22日

NOI国家集训队论文分类(至2008)(摘抄自C博客)

NOI国家集训队论文分类（至2008） 摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Polya原理及其应用》 2003 -许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 -周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Polya计数法的应用》 数位问题 2009 -高逸涵《数位计数问题解法研究》 2009 -刘聪《浅谈数位类统计问题》 动态统计 2004 -薛矛：《解决动态统计问题的两把利刃》 2007 -余江伟：《如何解决动态统计问题》 博弈 2002 -张一飞：《由感性认识到理性认识一一透析一类搏弈游戏的解答过程》2007 -王晓珂：《解析一类组合游戏》 2009 -曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 -方展鹏《浅谈如何解决不平等博弈问题》 2009 -贾志豪《组合游戏略述一一浅谈SG游戏的若干拓展及变形》母函数 2009 -毛杰明《母函数的性质及应用》 拟阵 2007 -刘雨辰：《对拟阵的初步研究》 线性规划 2007 -李宇骞：《浅谈信息学竞赛中的线性规划一一简洁高效的单纯形法实现与应用》 置换群 2005 -潘震皓：《置换群快速幕运算研究与探讨》 问答交互 2003 -高正宇：《答案只有一个一一浅谈问答式交互问题》 猜数问题 2003 -张宁：《猜数问题的研究：< 聪明的学生> 一题的推广》

2006 -龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 -何林：《数据关系的简化》 2006 -朱辰光:《基本数据结构在信息学竞赛中的应 用》 2007 -何森：《浅谈数据的合理组织》 2008 -曹钦翔《数据结构的提炼与压缩》 结构联合 2001 -高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 -黄刚：《数据结构的联合》 块状链表 2005 -蒋炎岩：《数据结构的联合——块状链表》 2008 -苏煜《对块状链表的一点研究》 动态树 2006 -陈首元：《维护森林连通性——动态树》 2007 -袁昕颢：《动态树及其应用》 左偏树 2005 -黄源河：《左偏树的特点及其应用》 跳表 2005 -魏冉：《让算法的效率跳起来”——浅谈跳跃表”的相关操作及其应用》2009 -李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Bala nee Tree 》 线段树 2004 -林涛：《线段树的应用》 单调队列 2006 -汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 -杨思雨：《伸展树的基本操作与应用》

国家集训队2005论文集 潘震皓

置换群快速幂运算 研究与探讨 江苏省苏州中学 潘震皓 [关键词] 置换 循环 分裂 合并 [摘要] 群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。 [正文] 一、引言 置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得O(k*乘法)或是O(logk*乘法)的算法；而对于分数幂运算，则找不到较好的方法实现。 二、置换群的整幂运算 2.1 整幂运算的一个转化 在置换群中有一个定理：设e T k =， （T 为一置换，e 为单位置换（映射函数为x x f =)(的置换）），那么k 的最小正整数解是T 的拆分的所有循环长度的最小公倍数。 或者有个更一般的结论：设e T k =， （T 为一循环，e 为单位置换），那么k 的最小正整数解为T 的长度。 我们知道，单位置换就是若干个只含单个元素的循环．．．．．．．．．的并。也就是说，长度为l 的循环，l 次的幂，把所有元素都完全分裂了。这是为什么呢？ 我们来做一个试验：(下面的置换均以循环的连接表示) 设n=6，那么3 26 )(T T =。任取一T=(1 3 5 2 4 6)，来做一遍乘法： ()() 36 2 45 1 34 126565432134 1 2 6 51265431265436543211265436543211265436543212 =???? ??=???? ?????? ??=???? ?????? ??=T 分裂成了2份！而且这2份恰好是T 的奇数项和偶数项！（注意可以写成(1 5 4)(3 2 6)）

国家旅游局《旅行社公告暂行规定》文档

旅行社公告暂行规定 第一条为规范有关旅行社的公告发布行为，加强对企业经营和旅游行政管理的指导服务，根据《旅行社条例》和《旅行社条例实施细则》，制订本暂行规定。 第二条旅行社公告事项如下： （一）旅行社业务经营许可证的颁发、变更、注销、吊销； （二）许可或暂停、停止旅行社经营出境、边境旅游业务； （三）旅行社经营或暂停、停止经营赴台旅游业务； （四）旅行社分社、服务网点设立与撤销备案； （五）旅行社委托代理招徕旅游者业务备案； （六）旅行社的违法经营行为； （七）旅行社的诚信记录； （八）旅游者对旅行社投诉信息； （九）旅行社质量保证金交存、增存、补存、降低交存比例和被执行赔偿等情况； （十）旅行社统计调查情况； （十一）全国和地区旅行社经营发展情况； （十二）旅游行政管理部门认为需要公开发布的其他有关旅行社的事项和情况信息。 第三条旅行社业务经营许可证颁发、变更公告，由颁发旅行社业务经营许可证和办理旅行社业务经营许可证变更事项的旅游行政管理部门发布。 旅行社业务经营许可证颁发公告，项目内容应该包括旅行社名称、

许可证编号、出资人、法定代表人、经营场所、许可经营业务、许可文号（附件1）。 旅行社业务经营许可证变更公告，项目内容应该包括旅行社许可证编号和变更前与变更后的名称、出资人、法定代表人、经营场所（附件2）。 第四条旅行社业务经营许可证注销、吊销公告，由办理注销旅行社业务经营许可证备案手续和作出吊销旅行社业务经营许可证决定的旅游行政管理部门发布。 旅行社业务经营许可证注销公告，项目内容应该包括旅行社名称、许可证编号、经营场所（附件3）。 旅行社业务经营许可证吊销公告，项目内容应该包括旅行社名称、许可证编号、主要负责人(附件4)。 第五条暂停旅行社业务公告，由作出暂停决定的旅游行政管理部门发布。 暂停旅行社业务公告，项目内容应该包括旅行社名称、许可证编号、经营场所、暂停时间期限(附件5)。 第六条许可或暂停、取消旅行社经营出境旅游业务公告，由国家旅游局或其委托出境旅游业务许可的省、自治区、直辖市旅游行政管理部门发布。 许可旅行社经营出境旅游业务公告，项目内容应该包括旅行社名称、原许可证编号、新许可证编号、出资人、法定代表人、经营场所、许可文号（附件6）。 暂停旅行社经营出境旅游业务公告，项目内容应该包括旅行社名称、许可证编号、经营场所、暂停时间期限（附件7）。 取消旅行社经营出境旅游业务公告，项目内容应该包括旅行社名

国家集训队2009论文集浅谈数位类统计问题

浅谈数位类统计问题 山东省青岛第二中学刘聪 【摘要】 在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。 【关键字】 数位区间统计递推树二进制 【正文】 在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。 【例题1】Amount of degrees (ural 1057) 题目大意： 求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意： 17 = 24+20， 18 = 24+21， 20 = 24+22。 输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。 输出：只包含一个整数，表示满足条件的数的个数。 数据规模：1 ≤ X ≤ Y ≤ 231?1，1 ≤ K ≤ 20，2 ≤ B ≤ 10。 分析： 所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。 很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。

国家旅游局公告2017年第21号――许可旅行社经营出境旅游业务公告

国家旅游局公告2017年第21号――许可旅行社经营出境旅 游业务公告 【法规类别】旅游综合规定 【发文字号】国家旅游局公告2017年第21号 【发布部门】国家旅游局 【发布日期】2017.09.12 【实施日期】2017.09.12 【时效性】现行有效 【效力级别】部门规范性文件 国家旅游局公告 （2017年第21号） 许可旅行社经营出境旅游业务公告 按照《旅行社条例》和《中国公民出国旅游管理办法》，许可以下70家旅行社经营出境旅游业务： 旧许可证编号新许可证 编号 出资人 法 定 代 表 经营场所许可文号

人 L-FJ50023 L-FJ-CJ00127 福建中旅旅 行社有限公 司 王丽美 南平市滨江大道商联大 厦一楼（府前路1号） 旅发 ﹝2017﹞86 号 2 武夷山中旅旅行社有限 公司 L-FJ50001 L-FJ-CJ00128 福建省中国 旅行社 陈萍 福建省武夷山市度假区 武夷宫 旅发 ﹝2017﹞86 号 3 厦门友客国际旅行社有 限公司 L-FJ20202 L-FJ-CJ00129 厦门欣欣信 息有限公司 赖 润 星 厦门市海沧区海景东路 2号9C5楼 旅发 ﹝2017﹞86 号 4 厦门青普国际旅行社有 限公司 L-FJ20216 L-FJ-CJ00124 北京青普旅 游文化发展 有限公司 杨雪山 中国（福建）自由贸易 试验区厦门片区湖里大 道24号海山商务中心 1202-E 单元 旅发 ﹝2017﹞76 号 5 山西大唐航 空国际旅行 社有限公司 L-SX00983 L-SX-CJ117 唐中诗 唐中诗 晋中市太谷县西环中路 53号 旅发 ﹝2017﹞ 105号 6 温州市教育旅游有限公 司 L-ZJ00726 L-ZJ-CJ00236 董滨/叶芬 董滨 温州市鹿城区惠民路上陡门教育新村综合楼121-123号 旅发﹝2017﹞76号 7 北京奥阿希斯旅游有限 公司 L-BJ01192 L-BJ-CJ00861 姚强、魏红日、刘亚杰 姚 强 北京市朝阳区阜通东大街6号院5号楼10层1108 旅发 ﹝2017﹞82号 8 北京四海之旅国际旅行社有限责任公司 L-BJ01052 L-BJ-CJ00862 金峦、肖季 红、任亚全 肖 季 红 北京市朝阳区霞光里66 号院1号楼3层09号 旅发﹝2017﹞82 号 9 凯撒（北京）国际会议展览有限责任公司 L-BJ01717 L-BJ-CJ00863 北京凯撒国 际旅行社有 限责任公司 魏 灵 北京市朝阳区东三环中 路25号16层1616室 旅发 ﹝2017﹞82 号 10 神州假期国际旅行社（北京）有限公司 L-BJ01779 L-BJ-CJ00864 赵林、曲超 赵 林 北京市朝阳区石门村路二院（库区）24幢4层430室 旅发 ﹝2017﹞82号 11 北京鑫路国 际商务旅行社有限公司 L-BJ01433 L-BJ-CJ00865 王庆波 王 庆波 北京市东城区东兴隆街 58号6层609 旅发﹝2017﹞82 号 12 联盟平台L-L-BJ-赵洋、王怀 赵 北京市朝阳区左家庄15旅发

国家集训队2004论文集_林涛

线段树的应用 广西柳铁一中林涛 【摘要】 在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。 线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。 本文通过3个例子：《蛇》、《空心长方体》、《战场统计系统》，讲述线段树中基本的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维的推广。 关键字：线段树二分子树收缩叶子释放面积树 【正文】 1. 线段树的定义及特征 定义1：线段树 一棵二叉树，记为T (a,b)，参数a,b表示该节点表示区间[a,b]。区间的长度b-a记为L。递归定义T[a,b]： 若L>1 ：[a, (a+b) div 2]为T的左儿子 [(a+b) div 2,b]为T的右儿子。 若L=1 ：T为一个叶子节点。 表示区间[1, 10]的线段树表示如下： (以下取对数后均向上取整) 定理1：线段树把区间上的任意一条线段都分成不超过2log L条线段 证明：(1)在区间(a，b)中，对于线段(c，d)，如果(c<=a) 或(d>=b)，那么线段在(a，b)中被分为不超过log(b-a)。 用归纳法证明，如果是单位区间，最多被分为一段，成立。 如果区间(a，b)的左儿子与右儿子成立，那么如果当c<=a时， 1．若d<=(a+b)div2那么相当与其左儿子分该线段，所分该线段数树不超过log((a+b)div 2-a)，即不超过log(b-a),成立。

2．若d>(a+b) div 2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过1+log(b-(a+b) div 2),也不超过 log(b-a)，成立。 对于d>=b的情况证明类似，不再赘述。 (2)在区间(a,b)中，对于任意线段也用归纳法证明。 对于单位区间，最多分为一段，成立。 若(a，b)的左儿子与右儿子均成立，则对于线段(c，d) 1．若d<=(a+b)div 2 则该区间所分该线段等于其左儿子区间所分该线段，线段数小于log((a+b) div 2-a)<2log(b-a)，成立。 2．若c>(a+b) div 2 则该区间所分该线段等于其右儿子区间所分该线段，线段数小于log(b-(a+b) div 2)<2log(b-a)，成立。 3．若1、2均不成立，则此线段在左儿子区间分该线段满足d>V.Lson.b,分该线段数不超过log(b-(a+b) div 2)，而在右儿子区间分该线段满 足c<=V.Rson.a,分该线段不超过log((a+b) div 2-1)，所以在该区间 分该线段不超过2log(b-a)，成立。 这个结论为线段树能在O(log L)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据。 【例题一】蛇1 在平面上有N个点，现在要求一些线段，使其满足以下要求： a．这些线段必须闭合 b．线段的端点只能是这N个点 c．交于一点的两条线段成90度角 d．线段都必须平行于坐标轴 e．所有线段除在这N个点外不自交 f．所有线段的长度之和必须最短 如果存在这样的线段，则输出最小长度，否则输出0。 【问题分析】 从该题的要求入手，先构出符合要求的图，再解决线段长度之和最小的问题。1．题目显然要求一个以给定的N个点为顶点的N多边形。所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。 2．将所有点排序后发现，在同一水平线上的点中，设这些点为P1，P2，P3，P4……Pn，P1要有一条平行于X轴的线段与其相连，就必须连它右边的点——P2，而P3如果再连P2，P2就有两条平行于X轴的线段和它相连，所以P3只能连P4，P5只能连P6……，同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。 3．由于解是唯一的，而是否相连只要广度扩展就可以判断了，所以关键在于判断由上述方法所构出线段是否合法——满足线段不在N个点之外自交： 1Saratov State University Problem Archive, 1028, Snake. 本题考查了基本的插入、删除和查找

NOI国家集训队论文分类(至2008)(摘抄自C博客)

NOI 国家集训队论文分类（至2008） 摘抄自 C 博客 组合数学 计数与统计 2001- 符文杰：《Pólya 原理及其应用》 2003- 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007- 周冬：《生成树的计数及其应用》 2008- 陈瑜希《Pólya 计数法的应用》 数位问题 2009- 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004- 薛矛：《解决动态统计问题的两把利刃》 2007- 余江伟：《如何解决动态统计问题》博弈 2002- 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》 2007- 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG 游戏的若干拓展及变形》母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007- 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005- 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003- 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题

2003- 张宁：《猜数问题的研究:< 聪明的学生> 一题的推广》2006 - 龙《一类猜数问题的研究》 数据结 构 数据结 构 2005 - 何 林：《数据关系的简化》 2006 - 朱晨 光：《基本数据结构在信息学竞赛中的应用》 2007 - 何 森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001- 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005- 黄刚：《数据结构的联合》 块状链表 2005- 蒋炎岩：《数据结构的联合——块状链表》 2008- 苏煜《对块状链表的一点研究》动态树 2006- 陈首元：《维护森林连通性——动态树》 2007- 袁昕颢：《动态树及其应用》左偏树 2005- 黄源河：《左偏树的特点及其应用》 跳表 2005- 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009- 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree 》线段树 2004- 林涛：《线段树的应用》 单调队列 2006- 汤泽：《浅析队列在一类单调性问题中的应用》哈希表2005- 李羽修：《Hash 函数的设计优化》 2007- 杨弋：《Hash 在信息学竞赛中的一类应用》 Splay 2004- 杨思雨：《伸展树的基本操作与应用》 图论 图论 2005- 任恺：《图论的基本思想及方法》

国家集训队2004论文集 杨思雨

伸展树的基本操作与应用 安徽省芜湖一中杨思雨 目录 【关键字】 (2) 【摘要】 (2) 【引言】 (2) 【伸展树的基本操作】 (2) 伸展操作Splay(x,S) (3) 伸展树的基本操作 (4) 时间复杂度分析 (5) 【伸展树的应用】 (7) 【总结】 (8) 【参考书目】 (9) 【附录】 (9)

【关键字】 伸展树基本操作应用 【摘要】 本文主要介绍了伸展树的基本操作以及其在解题中的应用。全文可以分为以下四个部分。 第一部分引言，主要说明了二叉查找树在信息学竞赛中的重要地位，并且指出二叉查找树在某些情况下时间复杂度较高，进而引出了在时间复杂度上更为优秀的伸展树。 第二部分介绍了伸展树的基本操作。并给出了对伸展树时间复杂度的分析和证明，指出伸展树的各种基本操作的平摊复杂度均为O(log n)，说明伸展树是一种较平衡的二叉查找树。 第三部分通过一个例子介绍了伸展树在解题中的应用，并将它与其它树状数据结构进行了对比。 第四部分指出了伸展树的优点，总结全文。 【引言】 二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。 作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n 各节点的完全二叉树，这些操作的最坏情况运行时间为O(log n)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为O(n)。而有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、A VL树等等。 本文将要介绍的伸展树（Splay Tree），也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。 【伸展树的基本操作】 伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。