无聊随手翻，翻到了一个这样的好东西——据结构的提炼与压缩：
为了防止以后忘记，这里把论文里的题目都纪录一下吧。
1．二维结构的化简
问题一：ural 1568 Train car sorting
定义一个对序列的操作：将这个序列分成两个，然后首尾连起来（我知道我描述得不清楚，自己想一下就好），例子：5 3 2 4 1分成3 4 1和5 2，然后变成3 4 1 5 2。
求将一个排列变成一个升序序列需要进行的操作次数。
我觉得不需要像论文一样弄一个什么母矩阵。我觉得可以给一个序列中每个元素一个高度（其实本质还是一样的，囧），比如5 3 2 4 1就有
5---
-3-4
--2-
---1
我们要让最高的高度越小，并且每一行都是一个升序序列。
然后论文就给出了一个算法，但没有说怎样思考得来的。这个算法确实很美妙。什么，你问我算法是什么？在论文里。时间复杂度：\(O(n \log n)\)
问题二：CEOI 2007 Day 2 Necklaces
我就觉得这题就是一个Trie的进化版。
2．树形结构的化简
问题三：浙江2007年省选 捉迷藏
将树变成括号序列。
比如这棵树：
我们可以得到一个这样的序列：[A[B[E][F[H][I]]][C][D[G]]]
然后就可以用线段树搞搞了。时间复杂度：\(O(n \log n)\)
问题四：2005年国家集训队何林论文 树的统计
这题的算法太美妙了！
我们求这棵树的DFS序和逆DFS序。
DFS序：7 10 14 2 13 1 9 11 6 5 8 3 15 12 4
逆DSF序：7 4 3 12 15 9 6 8 5 11 1 10 14 13 2
然后用神奇的加减法就可以得到\(t(v)\)了：
\(t(v)=f(v,\)DFS序列中\(v\)之后的部分\()+f(v,\)逆DFS序列中\(v\)之后的部分\()+f(v,\)\(v\)的所有祖先\()-v+1\)
然后用个栈和树状数组搞搞就算出来了。时间复杂度：\(O(n \log n)\)
其实我觉得可以用DFS序和Splay就可以搞出来了，囧。
问题五：问题二的遗留问题
说实话，我觉得论文里的”超级父亲“好像比较显然。
3．图结构的化简
问题六：ural 1557 Network Attack
先做一棵DFS树，满足条件的两条边有且只有以下两种情况：
问题七：ural 1569 Networking the “Iset”
首先有个很有价值的结论：当属的直径长为偶数，树的中心是唯一；当树的直径长为奇数，树的中心是唯二的。
奇数同理。
然后我们可以枚举中心了，之后来一个BFS树即可。