Hungary 算法（音译为“匈牙利算法”）是用来解决二分图匹配问题的利器。它的基本思想是通过DFS在二分图中找“交错轨”。但事实上，我认为掌握这个算法甚至根本不需要理解“交错轨”这个概念，它似乎和“决策树”“隐式图”类似，只是为了理解算法的本质而抽象出来的一种东西，在代码中不会出现，也不影响对代码的浅层理解和记忆。

算法的核心是bool find(int v)函数，它的作用是：寻找顶点v可能匹配的顶点。对于每个可以与v匹配的顶点j，假如它未被匹配，可以直接使用j与v匹配；假如j已与某顶点x匹配，那么只需调用find(x)来求证x是否可以与其它顶点匹配，如果返回true的话，仍可以使j与v匹配；这就是一次DFS。每次DFS时，要标记访问到的顶点（vis[j]=true），以防死循环和重复计算；每次DFS开始前所有的顶点都是未标记的。

主过程只需对每个左侧的顶点调用find，如果返回一次true，就对最大匹配数加一；一个简单的循环就求出了最大匹配的数目。

示例程序：
ural1109
stall4(usaco)

Treap = Tree + Heap;

正如它的名字解释的那样，treap是binary  search tree与heap的混血儿。每个节点除了有element域外还有一个priority域，在保证element满足bst性质的同时，priority需要满足堆序，即父节点的priority需要小于子节点。

插入以递归的方式进行，每次从子节点的递归层次返回后检查该子节点的优先级是否满足要求，若不满足就将其旋转上移一层。

这种递归的先自顶向下再自底向上的方法很方便一些依赖于子节点的辅助域的保存，例如size（这颗子树的节点总数）。这信息可以用来进行rank（取某值当前的序数）、select（取某序数对应的值）等经常用到的操作。

程序：ural1090.cpp

虚二叉树是处理统计问题的一种利器，它的最大优势就是编程无比简单。在需要统计的数据严格在某一范围内时，使用虚二叉树可以大大简化编程，但这也是虚二叉树的弱点，就是必须知道事先的数据范围，而且这个范围不能太大，必须能开一个相当的数组。

虚二叉树一般的应用方法在每个节点处保存其左子树加上自身的节点数。在插入时，采用非常类似二分查找的实现方法，若目标节点在当前节点的左子树或自身(x<=m)，则++tree[m]；在统计某节点的rank时，若目标节点在当前节点的右子树或自身(x>=m)，则++tot。

2002年李睿的论文讲到了这个，说的还是很明了的。

程序：star.cpp
(Ural 1028 )

Splay Tree 是信息学竞赛中应用很广泛的一种平衡树。Splay在应用中的一个缺点是树的层次没有保证，比如说若顺序插入所有数据，树就变成了一条链。虽然说这样还是不影响均摊复杂度，但由于一般的实现的Insert、Splay等操作都要用到递归，故在特别设计的数据中可能会遇到递归栈溢出等不希望看到的现象。

自顶向下伸展树可以解决这个问题，在它的实现中可以做到不存在任何递归。现简析其思路：

我们的目标是将被Splay的节点通过单旋和双旋移动到根，那么只要将目标节点“上面”的部分先适当地放到一边去，等目标节点作为根暴露出来之后再将刚才放到一边的子树合并起来。

具体过程有点难以用语言描述，所以我就不描述了。

但自顶向下splay有一个致命的缺点：无法将维护size域的操作轻易地结合在程序中（事实上我认为由自顶向下的前提这是不可能做到的），也就无法实现重要的Rank操作。在需要Rank操作时，还是写Treap之类好了。

程序：pro.cpp
( POI2000 Promotion)

问题：

给定一个字符串s[1...n]，求它的所有后缀中最小的一个。（本文中字符串之“大”“小”均对字典序而言。）

算法：

定义v[1..n]，其中v[i]=k表示s[i..i+k-1]在s的所有长度为k的字串中最小。我们求出每个v[i]最大的取值，再找到所有的v[i]中最大的一个，s[i..n]就是问题的答案。

基本思想是这样的（先不设计实现时的数据结构）：先将所有的1..n都保存在一个列表里。每次扫描列表里所有的i，若其v[i+v[i]]>0，则可以将i+v[i]从列表里删去，v[i]+=v[i+v[i]]；若其v[i+v[i]==0，则v[i]++当且仅当s[i+v[i]]在所有s[k+v[k]]中最小（其中k是当前列表里的值）。 然后删去所有链表中不等于v[i]最大值的v[i]。这基本上是一个不断合并/扩大区间的过程。当所有v[i]值不再变化时结束。

上述“列表”需要支持按下标查找、按下标删除、顺序枚举的操作。我采用数组模拟的双链表实现。（如果用单链表，在不知道前导节点编号的情况下，似乎无法实现“按下标删除”的功能。）

将完整的算法描述一遍。将1-n串在双链表里（也就是说next[i]=i+1，prev[i]=i-1之类）。每次循环时需要四次扫描链表里的每个i。第一遍，找到所有s[i+v[i]]中最小的。第二遍，考察每个v[i+v[i]]，根据其大于0或者等于刚才得出的最小值进行前述赋值与删除的操作。第三遍，找到v[i]的最大值。第四遍，进行前述删除操作。（其中二、三两遍扫描可以一次完成。）当链表仅剩一个元素时就得出了答案。

实现中的一个技巧是在保存s的数组的最后一个元素之后的位置放上一个比所有字符都要小的值，可以防止越界。

算法的时间复杂度是O(n)。可以采用记账方法严格证明。但我现在没时间写下来。

示例程序：
hidden.cpp

（USACO Training Secition 5.5 PROB Hidden Passwords）

去年研读了《算法导论》，对我而言书中一个“循环不变式”的概念很新颖。当时并未体会到这个概念的用处，似乎只是用来证明算法正确性而已。直到昨天做USACO上Fence Rails那道题的时候，我突然发现循环不变是在算法实现或者说程序书写时也很有帮助。

首先，我觉得maigo的程序里那个二分答案写得不好——有可能某个ok(m+1)要被检查两次，而这很有可能成为TLE的原因！真的要在每次检查ok(m)后紧接着检查ok(m+1)吗？也许可以避免吧。

这时我想到了循环不变式。我们需要的是找到一个明晰的界限x，满足ok(x)为true而ok(x+1)为false。 那么我们设计如下循环不变式：ok(l)为true，ok(r)为false。而每一次迭代都严格的缩小r-l，当r-l==1时便结束。当然为了满足初始条件，初始时l=0，r=R+1。有了这个循环不变式，在写代码时的思考也就减轻了：m=(l+r)/2；如果ok(m)为false，那么l=m；反之r=m。循环不变式就这样得到保持。最后的程序非常简洁高效（至少在二分答案这一环上是比maigo的程序简洁高效的）。

把这种思想用到其它类型的二分查找里，比如说需要实现C++里的upper_bound类似的东西。欲查找对象为x，查找的数组是s。那么循环不变式就是：s[l]<=x，s[r]>s。每次循环中，s[m]<=x则l=m，反之则r=m。同样是r-l==1时终止返回l。

我们看出， 在程序实现过程中试图设计循环不变式有以下好处：1. 使编程思路明晰，不易出低级错误。这是最重要的。 2. 保证程序正确性。 3. 使程序简洁，而且往往比较高效。4. 降低写代码时的思考强度，加快书写速度。

什么时候应该往循环不变式的方面想呢？我目前只想到了一条：当你写出了一个for( ; ; )的时候。这个有待进一步研究和补充。