题外话：这一年的noip应该是最受大众关心的，以至于在百度上输入noip第三个关键字就是noip2007。主要是由于这篇文章：http://www.zhihu.com/question/21107274/answer/18452037
第一题：统计数字
排序/平衡二叉树
受上面这篇文章的影响，我没有用快排，而是用了STL的multiset的count函数来统计出现次数。但事实证明STL的sort足以应付此题。另外的解法是用Treap实现的名次树，效率不及sort但高于multiset。
第二题：字符串的展开
模拟
虽然是模拟题但是可惜没有1次AC。原因出在我没有考虑到连续的两个展开，比如：
1 1 1
a-c-e
展开后应该是：abcde。而我的策略是处理掉一个「展开」操作后就马上输出前面的部分并删除，这就导致输出的结果是：abc-e。实际上应该保留后面的这个字符，以便作为另一个展开操作的开头。
第三题：矩阵取数游戏
动态规划、高精度
不得不承认我一开始确实想不到思路。看了网上的题解，发现主要是两种方法：（以下描述均针对矩阵的每一行，最终结果即各行结果之和）
-
f(i, j) 表示在左边取i个数、在右边取j个数能得到的最大分数，则
f(i, j) = max{ f(i, j-1)+w(m-j+1)*2^(i+j), f(i-1, j)+w(i)*2^(i+j) }
-
f(i, j) 表示从第i个格子取到第j个格子能得到的最大分数，则
f(i, j) = 2*max{ f(i+1, j)+w(i), f(i, j-1)+w(j) }
其中第二种方法很巧妙地避开了高精度乘法，用2在状态转移的时候进行累乘。最后，高精度最好用加法 char[] 而不要用 string，两者速度相差太明显了（几乎是超时与无压力AC的区别）。
第四题：树网的核
DFS
这道题目的特点是用大量的概念、定义来吓唬人。
几乎所有网络上的题解都说「只要对于一条直径进行计算即可」，但是我想不明白。那就姑且承认这个结论。
首先，在树上找到一条直径。方法如下：
- 从树上任意一点 u 出发，找到距其最远的点 v；
- 从 v 出发，找到距其最远的点 x。
路径 v -> x 即树网的直径。（证明见注释）
然后找核。枚举直径上的每个点，向单方向扩展出一段长度小于等于 s 的「核」，然后对于「核」上的每一个结点，求出它到每个点的最短距离。在所有这些最短距离中找出最大值，这个值就是现在这个「核」的偏心距。找到所有偏心距中最小的一个即可。
注释：关于用两次遍历求出直径的方法的正确性，证明如下：
首先，我们要证明从树上任意一点 u 出发找到的最远结点 v 必然是直径的一个端点。如果能够得到这个结论，整个方法的正确性就显然了。
先假设我们找到的 v 结点不是直径的端点。
我们可以证明 u->v 必然与直径 a->b 有交叉点。
如果没有交叉点，任选两条路径的两个端点相连就能得到一条更长的路径。如下图。
所以，既然有交叉点，设交叉点为 x，由 u->v 大于 u->a，可以推出 x->v 大于 x->a，那么路径 v->x->b 比 a->b 更长，a->b 不是直径，矛盾。
所以 v 只能是直径的端点。