资源描述：
《国家集训队2005论文集 何林》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据关系的简化长沙雅礼中学何林常用的数据关系：线性序列，树，图1243651(1,1)2(2,1)4(3,1)3(4,4)5(5,4)6(6,4)12345781242585272131坐船问题雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。学校希望每个同学都坐上船，同时学校想要租用最少的船。请问：学校至少要租多少船？伍昱伍平何林何刚黄刚何凡伍昱伍平黄刚何刚何林何凡伍昱伍平黄刚何刚何林何凡最优解OR图-->树伍昱伍平黄刚何刚何林何凡一个包含n个点的无向图同名或者同姓的人之间连一条边图模型最小边
2、覆盖任意图最大匹配！伍昱伍平何林何刚黄刚何凡伍昱伍平黄刚何刚何林何凡树结构一片森林每个节点和左孩子同姓每个节点和右孩子同名树的构造首先假设所有人是一个连通图黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师树的构造首先假设所有人是一个连通图雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛黄刚张药师没有左儿子了树的构造首先假设所有人是一个连通图雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛黄刚张药师树的构造首先假设所有人是一个连通图黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师欧阳涛树的构造首先假设所有人是一个连通图黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷
3、震子黄药师周涛张药师欧阳涛没有右儿子树的构造首先假设所有人是一个连通图黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师欧阳涛树的匹配黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师欧阳涛分析叶子节点独子！树的匹配黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师欧阳涛独子的情况他们坐一条船剩下的树依然是连通的树的匹配黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师张药师分析叶子节点落单！树不连通！不是独子树的匹配黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师张药师分析叶子节点树的匹配非独子的情况每次让两个人坐上一条船树始终保持连通假设树中有n个
4、点，[(n+1)/2]条船即可容纳所有人。这无疑是最优解。树的匹配设森林中有m棵树，所有树的规模是n1,n2,…,nm。对每棵树分别处理。答案是∑(i=1..m)[(ni+1)/2]森林的匹配图-->树小结伍昱伍平黄刚何刚何林何凡任意图最大匹配！伍昱伍平黄刚何刚何林何凡简单贪心O(n2)或O(n3)的时间复杂度编程复杂度很高O(n)的时间复杂度编程复杂度很低树的统计一棵树含有n个节点。节点编号为1,2,3,…,n。定义t(v)为v的后代中所有编号小于v的节点个数。求t(1),t(2),t(3),…,t(n)。树-->线性树-->线性710193
5、411685151221413t(9)=3t(10)=1t123456789101112131415000001603100020对每个点，逐个检查其后代。时间复杂度O(n2)。当n>=30000就不可承受。树-->线性后代如何把这个“先后”顺序表现出来呢树-->线性710193411685151221413线性一个序列中元素之间的先后关系十分明显710142131911658315124树-->线性710193411685151221413线性一个序列中元素之间的先后关系十分明显710142131911658315124对应后代多出来的部分9
6、树-->线性710193411685151221413线性逆序DFS遍历710142131911658315124树-->线性710193411685151221413线性对应后代多出来的部分9710142131911658315124树-->线性710193411685151221413710142131911658315124743121596851111014132DFS遍历逆DFS遍历树-->线性710193411685151221413710142131911658315124743121596851111014132DFS遍历逆DF
7、S遍历后代！重叠-->容斥原理树-->线性710193411685151221413710142131911658315124743121596851111014132DFS遍历逆DFS遍历9的直系祖先红+蓝+黄=全部+后代树-->线性710193411685151221413710142131911658315124743121596851111014132DFS遍历逆DFS遍历红+蓝+黄=全部+后代红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1树-->线性红+
8、蓝+黄=全部+后代红：DFS序列中节点v后比他小的数的个数蓝：逆DFS序列中节点v后比他小的数的个数黄：v的直系祖先中比v小的节点个数全部：v-1红：
