国家集训队论文集何林.ppt

每次让两个人坐上一条船 树始终保持连通 假设树中有n个点，[(n+1)/2]条船即可容纳所有人。 这无疑是最优解。 设森林中有m棵树，所有树的规模是n1, n2, …, nm。 对每棵树分别处理。 答案是∑(i=1..m)[(ni+1)/2] 图?树，树?序列。 有时候不需要包罗万象的所有信息 合理的组织数据之间的关系 利用简化数据关系实现数据的有序化 简化后的关系更明了，有利于窥见本质矛盾。 红：DFS序列中节点v后比他小的数的个数 蓝：逆DFS序列中节点v后比他小的数的个数 黄：v的直系祖先中比v小的节点个数 全部：v-1 蓝：逆DFS序列中节点v后比他小的数的个数 问题：已知一个序列(逆DFS序列)，求每个数后面有多少个数比他小。 解答：用线段树即时更新。时间复杂度O(nlogn)。 树简化成线性结构后带来的“序”关系 红：DFS序列中节点v后比他小的数的个数 蓝：逆DFS序列中节点v后比他小的数的个数 黄：v的直系祖先中比v小的节点个数 全部：v-1 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 7 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 7 10 7 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 2 7 10 14 7 10 7 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 7 1 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 7 1 7 9 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 7 1 7 9 7 9 11 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 7 1 7 9 7 9 11 7 9 6 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 7 1 7 9 7 9 11 7 9 6 7 9 6 5 黄：v的直系祖先中比v小的节点个数 7 10 1 9 3 4 11 6 8 5 15 2 14 13 7 10 14 13 7 10 14 2 7 10 14 7 10 7 7 1 7 9 7 9 11 7 9 6 7 9 6 5 13的直系祖先 5的直系祖先 深度优先有哪些信誉好的足球投注网站中要用到一个栈来存储节点（比如递归）。 任意时刻，栈顶元素的直系祖先就是栈中其余的节点。 用一棵线段树来维护这个栈。求每个节点的直系祖先中有多少个比他本身小就能用O(nlogn)的时间复杂度实现。 * * 长沙雅礼中学 何林 常用的数据关系：线性序列，树，图 1 2 4 3 6 5 1(1,1) 2(2,1) 4(3,1) 3(4,4) 5(5,4) 6(6,4) 1 2 3 4 5 7 8 1 2 4 2 5 8 5 2 7 2 1 3 1 坐船问题 雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。 学校希望每个同学都坐上船，同时学校想要租用最少的船。请问：学校至少要租多少船？ 伍昱 伍平 何林 何刚 黄刚 何凡 伍昱 伍平 黄刚 何刚 何林 何凡 伍昱 伍平 黄刚 何刚 何林 何凡 最优解 伍昱 伍平 黄刚 何刚 何林 何凡 一个包含n个点的无向图 同名或者同姓的人之间连一条边 最小边覆盖 伍昱 伍平 何林 何刚 黄刚 何凡 伍昱 伍平 黄刚 何刚 何林 何凡 一片森林 每个节点和左孩子同姓 每