《树结构在程序设计中的运用》由会员分享，可在线阅读，更多相关《树结构在程序设计中的运用（126页珍藏版）》请在金锄头文库上搜索。
1、树结构在树结构在程序设计中的运用程序设计中的运用上海市控江中学王建德上海市控江中学王建德浙江省浙江省4年年NOI组队赛组队赛目录引言引言树结构在程序设计中的运用树结构在程序设计中的运用 20032003年竞赛的知识结构分布年竞赛的知识结构分布 竞赛竞赛试题试题算法算法NOIP乒乓球乒乓球数据统计数据统计NOIP数字游戏数字游戏动态程序设计动态程序设计NOIP栈栈回溯法或组合数学的回溯法或组合数学的Catalan数数NOIP麦森数麦森数高精度运算高精度运算NOIP神经网络神经网络图的递归运算图的递归运算NOIP侦探推理侦探推理回溯法回溯法NOIP加分二叉树加分二叉树递归的动态程序设计递归的动态程
2、序设计NOIP传染病扩展传染病扩展回溯法回溯法 竞赛竞赛试题试题算法算法IOI可视边界线段树IOI代码转换程序语句在满足加法交换率和变量名改换情况下的匹配IOI猜牛游戏贪心或类博弈树算法IOI路径维护在无向图的生成过程过程中计算最小生成树IOI逆向输出开放性试题IOI机器人宽度优先搜索20032003年竞赛的知识结构分布年竞赛的知识结构分布 竞赛竞赛试题试题算法算法NOI木棒游戏枚举搜索NOI文本编辑器 数据结构NOI卫星探测二分查找NOI草莓后序遍历NOI数据生成器 前序遍历和后序遍历NOI智破连环阵 回溯法20032003年竞赛的知识结构分布年竞赛的知识结构分布试题特点试题特点1、强强调调
3、基基础础知知识识的的灵灵活活应应用用。每一轮竞赛都有基础知识题，但对灵活应用基础知识的要求愈来愈高。例如IOI的路径维护在逐边添入无向图的过程中计算最小生成树；文本编辑器要求设计多样的数据结构。例如线性表、非线性的树和图；NOIP的加分二叉树采用的动态程序设计是递归形式的；NOI的数据生成器必须综合使用前序遍历和后序遍历2、首次出现了线段树和可以选择类博弈树算法的试题、首次出现了线段树和可以选择类博弈树算法的试题3、近近似似算算法法类类的的试试题题增增加加。例如IOI的猜牛游戏、逆向输出、机器人、NOI的卫星探测、草莓、智破连环阵等。由于这些例题视程序逼近最优解和最优效率的程度给分，因此拓展了
4、选手思维的空间，易启发选手的创造性。但反过来说，由于近似算法类的选题空间比较大，因此有可能使得题目的难度加大。试题特点试题特点4、树树形形结结构构类类的的问问题题增增多多。例如NOI的卫星探测通过二分查找构造一棵隐形的二叉树；草莓和数据生成器使用了人们容易被忽视的后序遍历；IOI的路径维护要求计算最小生成树；5、可可“一一题题多多解解”和和开开放放性性的的试试题题增增多多。例如，IOI的逆向输出就是一道没有固定模式和经典算法可套用、需要量身定制合适算法的试题；猜牛游戏既可以采用贪心法，亦可以采用类博弈树的算法；NOIP的栈既可以通过回溯法计算，亦可以通过组合数学的Catalan数计算；6、出出
5、现现一一些些“陷陷阱阱题题”。例如NOIP的传染病扩展极易诱导选手错误地使用贪心法或动态程序设计，实际上该问题不具备最优子结构的特征，正确的算法是回溯搜索。启示启示培养内省智力培养内省智力充分利用网络资源充分利用网络资源以问题为出发点、以自主探究为途以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、径、以构造网络式思维模式为基础、以创新为目的组织集训以创新为目的组织集训培养内省智力培养内省智力入门入门自信心自信心提高提高自省力自省力自信心和自知之明是对立的统一。自信心和自知之明是对立的统一。自信心倘若不是建立在自知之明自信心倘若不是建立在自知之明的基础上，则会变成一种无知的的基础上
6、，则会变成一种无知的自负，不可能取得持续的成功。自负，不可能取得持续的成功。v科学精神的核心是怀疑和批评。这种态度既对他人又对自己，“知人者智，自知者明”，“知常曰明”v不能用看书取代上机实践，经常要想“自己怎样面对这个问题的挑战；如果由自己当场独立解题的话，会得到怎样的结果”。“纸上得来终觉浅，绝知此事要躬行”。看懂了不稀奇，会做有灵气，能讲清原理、提出质疑、拓延思路、探索新知才算了不起v在挑选练习题时，既不要因为轻视而放弃基础题；也不要因为畏难而放弃大题难题。充分利用网络上与信息学活动相关的信息资源充分利用网络上与信息学活动相关的信息资源1、由于网络上大量的算法知识和试题的出现，使得学生学
7、习的大部分时间和空间由课堂转移到网上学习，自主性显著提高，学习方式发生了根本性的变化2、学习的效率取决于如何在浩如烟海的网上信息中选择适应于竞赛需要和个性发展的东西3、千万不要有“太易了不屑做、太难了不愿做”的主观随意性充分利用网络上与信息学活动相关的信息资源充分利用网络上与信息学活动相关的信息资源编程解题能力是在长期的上机实践中积累起来的。如果长期的无所事事、无所作为，迟早会落得了“小题做不对、大题难题不会做”的可悲结局应该对试题本身有一个科学的价值判断：“这道题是不是有利于夯实基础，或者这道题是不是引出带规律性的东西，能不能派生出更多类似的问题”，真正从提高自身的算法认知水平和编程能力的高
8、度，来决定练习题的取舍。以问题为出发点、以自主探究为途径、以构造网以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训络式思维模式为基础、以创新为目的组织集训第一步：界界定定问问题题。即明确试题要求我们做什么,解决什么问题，输出怎样的结果第二步：明明确确出出发发点点，即明确试题的初始状态是什么，给出了哪些求解条件，其中哪些是显性的，哪些是隐性的，必须无一漏失。第三步：寻寻找找怎怎样样做做的的创创意意。即要求学生独立思考，尽可能多地收集相关资料，尝试各种组合，调动所有的灵感和思考方式。第四步：集集中中测测试试。每人设计三组测试数据,分别从一般情况、边界情况、扩大问题
9、规模三个角度测试程序的正确性、时间效率和空间效率。然后交流测试数据，学生间进行互测。这样做既能测出自己程序的正确程度，又能在改善程序的时空效率上取长补短。建立知识信息网络建立知识信息网络归纳概括归纳概括通过对相关问题（即形式不同、本质类似的一类问题）的归纳，揭示内在的联系，概括出解决类似问题的一般规律，并得到高度抽象、概括的模型，为以后分析问题、设计算法进行指导。触类旁通、联想外推触类旁通、联想外推 通通过过举举一一反反三三、由由此此及及彼彼、触触类类旁旁通通，从从一一个个问问题题拓拓广广出出许许多多新新问问题题。在在解解决决这这些些新新问问题题的的过过程程中中，进进一一步步锻锻炼炼思思维维，
10、并并通通过过联联想想的的线线索索将将新新问问题题、新新模模型型、新新算算法并入知识网法并入知识网近年来，由于各种竞赛纷纷采用free-pascal，因此对于算法来说，空间效率上的要求降低了，而对时间效率却提出了更高的要求。这使得选手不仅要娴熟地掌握常规算法，而且要大胆创新，构造更高效的算法来解决问题。在以往的程序设计中，链式结构采用得较多。的确链式结构有编程复杂度低、简单易懂等优点，但有一个致命的弱点：相邻的两个元素间的联系并不明显。而树结构却能很好的做到这一点。选手对树的先根遍历十分娴熟，但对后根遍历却不能像先根遍历那样应用自如。树结构在程序设计中的运用树结构在程序设计中的运用一并查集二线段
11、树三解决动态统计的静态方法四、二叉树应用的拓广五、先根遍历与后根遍历的应用小结并查集并查集 竞赛中会经常遇到这样的题目：给出各个元素之间的竞赛中会经常遇到这样的题目：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集对集合的合并和查找，因此将这种集合称为并查集。链结构的并查集链结构的并查集树结构的并查集树结构的并查集链结构的链结构的并查集并查集链表被普通用来计算并查集链表被普通用来计算并查集. .表中
12、的每个元素设两个指表中的每个元素设两个指针：一个指向同一集合中的下一个元素；另一个指向针：一个指向同一集合中的下一个元素；另一个指向表首元素。表首元素。 采用链式存储结构，在进行集合查找时的算法复杂度仅采用链式存储结构，在进行集合查找时的算法复杂度仅为为O O（1 1）；）；但合并集合时的算法复杂度却达到但合并集合时的算法复杂度却达到了了O O（n n）。）。如果我们希望两种基本操作的时间效率都比如果我们希望两种基本操作的时间效率都比较高的话，链式存储方式就较高的话，链式存储方式就“力不从心力不从心”了。了。树结构的并查集树结构的并查集采采用用树树结结构构支支持持并并查查集集的的计计算算能能够
13、够满满足足我我们们的的要要求求。并并查查集集与与一一般般的的树树结结构构不不同同，每每个个顶顶点点纪纪录录的的不不是是它它的的子子结结点点，而而是是将将它它的的父父结结点点记记录录下下来来。下下面面我我介介绍绍一一下下树树结结构构的的并并查查集集的两种运算方式的两种运算方式直接在树中查直接在树中查询询边边查查询边询边“路径压缩路径压缩”对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低；时间效率高。 返回直接在树中查直接在树中查询询集合的合并算法很简单，只要将两棵树的根结集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要点相连即可，这步操作只要O O（1 1）时间复杂
14、度。算时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为要的时间复杂度平均为O O（logNlogN）。）。但在最坏情况但在最坏情况下，树退化成为一条链，使得每一次查询的算法复下，树退化成为一条链，使得每一次查询的算法复杂度杂度为为O O（N N）。）。边边查查询边询边“路径压缩路径压缩” 其其实实，我我们们还还能能将将集集合合查查找找的的算算法法复复杂杂度度进进一一步步降降低低：采采用用“路路径径压压缩缩”算算法法。它它的的想想法法很
15、很简简单单：在在集集合合的的查查找找过过程程中中顺顺便便将将树树的的深深度度降降低低。采采用用路路径径压压缩缩后后，每每一一次次查查询询所所用用的的时时间间复复杂杂度度为为增增长长极极为为缓缓慢慢的的ackermanackerman函函数数的的反反函函数数（x x）。对对于于可可以以想想象象到到的的n n，（n n）都是在都是在5 5之内的。之内的。银河英雄传说银河英雄传说【问题描述问题描述】公元五八公元五八一年，地球居民迁移至金牛座一年，地球居民迁移至金牛座第二行星，在那里发表银河联邦第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。创立宣言，同年改元为宇宙
16、历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在宇宙历七九九年，银河系的两大军事集团在巴米利恩星域巴米利恩星域爆发战争。泰山压顶集团派爆发战争。泰山压顶集团派宇宙舰队司令宇宙舰队司令莱因哈特莱因哈特率领十万余艘战舰出征，气吞山河集团点名将率领十万余艘战舰出征，气吞山河集团点名将杨威利杨威利组织麾下三万组织麾下三万艘战舰迎敌。艘战舰迎敌。 杨杨威威利利擅擅长长排排兵兵布布阵阵，巧巧妙妙运运用用各各种种战战术术屡屡次次以以少少胜胜多多，难难免免恣恣生生骄骄气气。在在这这次次决决战战中中，他他将将巴巴米米利利恩恩星星域域战战场场划划分分成成3000030000列列，每每列列依
17、依次次编编号号为为1 1， 2 2， ， 3000030000。之之后后，他他把把自自己己的的战战舰舰也也依依次次编编号号为为1 1， 2 2， ， 3000030000，让让第第i i号号战战舰舰处处于于第第i i列列(i (i = = 1 1， 2 2， ， 30000)30000)，形形成成“一一字字长长蛇蛇阵阵”，诱诱敌敌深深入入。这这是是初初始始阵阵形形。当当进进犯犯之之敌敌到到达达时时，杨杨威威利利会会多多次次发发布布合合并并指指令令，将将大大部部分分战战舰舰集集中中在在某某几几列列上上，实实施施密密集集攻攻击击。合合并并指指令令为为M Mijij，含含义义为为让让第第i i号号战
18、战舰舰所所在在的的整整个个战战舰舰队队列列，作作为为一一个个整整体体（头头在在前前尾尾在在后后）接接至至第第j j号号战战舰舰所所在在的的战战舰舰队队列列的的尾尾部部。显显然然战战舰舰队队列列是是由由处处于于同同一一列列的的一一个个或或多多个个战战舰舰组组成成的的。合合并并指指令令的的执执行行结结果果会会使使队队列列增增大大。然然而而，老老谋谋深深算算的的莱莱因因哈哈特特早早已已在在战战略略上上取取得得了了主主动动。在在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了
19、解当前杨威利的战舰分布情在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：况，也会发出一些询问指令：C Cijij。该指令意思是，该指令意思是，询问电脑，杨威利的第询问电脑，杨威利的第i i号战舰与第号战舰与第j j号号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经
20、展开，银河的历史又翻过了一页最终的决战已经展开，银河的历史又翻过了一页【输入文件】输入文件galaxy.in的第一行有一个整数T（1T500，000），表示总共有T条指以下有T行，每行有一条指令。指令有两种格式：1.Mij：i和j是两个整数（1i ， j30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。2.Cij：i和j是两个整数（1i ， j30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。【输出文件】输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：如果是杨威
21、利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。设var Father，Count，Behind：array1.maxn of integer；在同一队列中的战舰组成一个树型结构的并查集。Fatherx 战舰x的父指针。Fatherx=x，表明战舰x为根节点。路径压缩后，树中所有子节点的父指针指向根节点；Countx 以节点x为根的树的节点数；Behindx 战舰x在列中
22、的相对位置；初始时，我们为每一艘战舰建立一个集合，即Fatherx=x Countx=1 Behindx=0（1x30000) 1、查找根节点并进行路径压缩、查找根节点并进行路径压缩function Find_Father(x：integer)：integer；查找节点x所在树的根节点，并进行路径压缩var i，j，f，next：integer；begin ix； 找出节点x所在树的根节点f while Fatherii do iFatheri； fi；ix； while if do 按照自下而上的顺序处理x的祖先节点 begin nextFatheri；FatherIf；把节点i的父节点设为
23、f，完成路径压缩 jnext； repeat BehindiBehindi+Behindj；迭代求出路径上每一个子节点相对于f的相对位置 jFatherj； until Fatherj=j； inext； end；while find_Fatherf； 返回x所在树的根节点end； Find_Father 2、计算合并指令、计算合并指令procedure MoveShip(x，y：integer)；把x所在的集合合并入y所在的集合var fx，fy：integer；begin fxfind_Father(x)；计算x所在树的根节点fx fyfind_Father(y)；计算y所在树的根节点fy
24、 Fatherfxfy；将fx的父节点设为fy BehindfxCountfy；计算fx的相对位置为Countfy CountfyCountfy+Countfx；计算新集合的节点数end； MoveShip 3、计算询问指令、计算询问指令procedure CheckShip(x，y：integer)；计算x节点和y节点的相对位置情况var f1，f2：integer；begin f1Find_Father(x)；计算x所在树的根f1 f2Find_Father(y)；计算y所在树的根f2 if f1f2 若x，y不在一棵树中，则返回-1，否则返回x和y间隔的战舰数then writeln(-
25、1)else writeln(abs(Behindx-Behindy)-1)；end； CheckShip 由此得出主程序：由此得出主程序： for i1 to maxn do 初始时为每一艘战舰建立一个并查集 begin Fatheri i； Counti 1； Behindi 0； end；for readln(CmdCount)； 读指令数 for i1 to CmdCount do 顺序处理每一条指令 begin read(ch)；读第i条指令的类型 case ch of M：begin readln(x，y)；MoveShip(x，y)； end；处理合并指令 C：begin rea
26、dln(x，y)；CheckShip(x，y)； end；处理询问指令 end；case end；for线段树线段树动态处理可以映射在一个坐标轴上的一些固定线段，例如求并区间的总长度，或者并区间的个数等等。优点：随时插入一个区间或删除一个已有区间，并同时用低耗费维护需要的性质。线段树线段树- -构造思想构造思想下图显示了一个能够表示1，10的线段树：特点特点1、叶结点表示一个初等区间：a,b=a+1;每一个内部结点b-a1;2、根为a,b的线段树为T(a,b),其左子树为T(a,(a+b)/2),右子树为T(a+b)/2,b),直至细分为一个初等区间（叶结点）为止。线段树的存储结构线段树的存储
27、结构1、动态数据结构TypeTnode=Treenode;Treenode=recordB,E:integer;该区间为B,ECount:integer;记录覆盖到B,E区间的线段条数LeftChild,Rightchild:Tnode;左右子树的根End;2 2、静态数据结构、静态数据结构用数组B，E，C，LSON，RSON。设一棵线段树的根为v。那么Bv,Ev就是它所表示区间的界。Cv记录覆盖到B,E区间的线段的条数。LSONv，RSONv分别表示了它的左儿子和右儿子的根编号。线段树的运算线段树的运算1、建树、建树从根对应的区间a，b出发，每次分成两个部分，分别建立对应的左右子树，直到面临
28、一个初等区间x,x+1。设一个全局变量n，来记录一共用到了多少结点。开始n=0procedureBUILD(a,b)Beginnn+1；vn；Bva；Evb；Cv0；ifba1thenbeginLSONvn+1；BUILD(a,（a+b）div2)；RSONvn+1；BUILD(（a+b）div2,b);end;end;2、插入线段、插入线段将区间c,d插入线段树T(a,b),并设T(a,b)的根编号为vprocedureINSERT(c，d，v)Beginmid=(Bv+Ev)div2;计算（a,b）的中间点ifcBvandEvd若(c,d)覆盖（a,b），则区间数+1thenCvcv+1e
29、lsebegin若（若（c,d）位于位于(a,b)的左半区间，则递归插的左半区间，则递归插入入v的左子树；若（的左子树；若（c,d）位于位于(a,b)的右半区间，则递归的右半区间，则递归插入插入v的右子树的右子树ifcmidthenINSERT(c,d;RSONv);end;end3、删除线段、删除线段在线段树T(a,b)中删除区间c,d,并设T(a,b)的根编号为v：procedureDELETE(c,d;v)beginifcBvandEvd若(c,d)覆盖（a,b），则区间数-1thenCvCv-1elsebegin若（若（c,d）位于位于(a,b)的左半区间，则递归删除的左半区间，则递归
30、删除v的左子树；若（的左子树；若（c,d）位于位于(a,b)的右半区间，则递归删除的右半区间，则递归删除v的右子树的右子树ifc(Bv+Ev)div2thenDELETE(c,d;RSONv);end；end特别注意：只有曾经插入过的区间才能够进行删除。这样才能保证线段树的维护是正确的。线段树的动态维护线段树的动态维护1、计算测度、计算测度结点的测度结点的测度Mv Mv 指的是结点指的是结点v v所表示区间中线段覆盖过的长度所表示区间中线段覆盖过的长度。Cv0,Mv = Ev-Bv;Cv0,Mv = Ev-Bv;Cv=0 Cv=0 且且v v是叶子结点，是叶子结点，Mv=0Mv=0；Cv=0
31、Cv=0 且且v v是内部结点，是内部结点，Mv=MLSONv+MRSONv; Mv=MLSONv+MRSONv; 连续线段数连续线段数linevlinev指的是区间中互不相交的线段条数。指的是区间中互不相交的线段条数。连续线段数并不能像测度那样将两个子结点中的连续线段数连续线段数并不能像测度那样将两个子结点中的连续线段数简单相加。于是我们引进了两个量简单相加。于是我们引进了两个量lbdvlbdv ，rbdrbd v v ，分别分别表示区间的左右两端是否被线段覆盖。表示区间的左右两端是否被线段覆盖。 1 (1 (左端点被线段覆盖到左端点被线段覆盖到) )lbdvlbdv = 0 ( = 0 (
32、左端点不被线段覆盖到左端点不被线段覆盖到) ) 1 ( 1 (右端点被线段覆盖到右端点被线段覆盖到) )rbdvrbdv = 0 ( = 0 (右端点不被线段覆盖到右端点不被线段覆盖到) )2、计算连续线段数、计算连续线段数Lbd=1rbd=1line可以根据lbd，rbd定义如下： 1 (count 0) 0 (count=0 且结点为叶结点) Line= lch.Line + rch.Line - 1 (count=0 且结点为内部结点，lchrbd、 rchlbd都为1) lch.Line + rch.Line (count=0且结点为内部结点，hrbd, rchLbd不同时为1) 线段
33、树的变形线段树的变形对点统计对点统计原线段数记录基数的Cv这时就可以用来计算落在定区间内的点个数了。原搜索路径也发生了改变，不存在“跨越”的情况。同时插入每个点的时候都必须深入到叶结点，因此一般来说都要有logn的复杂度。应用这样的线段树一方面是方便计数。另一方面由于它实际上是排序二叉树，所以容易找出最大和最小来。例一例一商品促销商品促销一位顾客要进行n（1n5000）天的购物，每天他会有一些帐单。每天购物以后，他从以前的所有帐单中挑出两张帐单，分别是面额最大的和面额最小的一张，并把这两张帐单从记录中去掉。剩下的帐单留在以后继续统计。输入的数据保证，所有n天的帐单总数不超过1000000并且每
34、份帐单的面额值是1到1000000之间的整数。保证每天总可以找到两张帐单。建立点线段树，范围是1，1000000，即每种面额的帐单设为一个叶结点。如果CLSONv0,那么树v中的最小值一定在它的左子树上。如果CRSONv0，它的最大值在右子树上；线段树的深度为log1000000=20改进的办法改进的办法 用hash来保存每一种面额的帐单数目，然后对于一个具体的帐单（面额V），在线段树中保存V/100的值，即把连续的100种面额的帐单看成是一组。由于V的范围是1.1000000，所以线段树中有10000个点。在找最大的数的时候，首先找到最小的组，然后在hash里对这个组进行搜索，显然这个搜索的
35、规模不会超过100。由于线段树变小了，所以树的深度只有14左右，整个问题的复杂度极限为N*14+n*14*100*2，对于问题的规模来说，仍然是高效率的。但这样做比前种方法在一定程度上节省了空间。同时实际上也提醒了我们对线段树应该加以灵活的应用。 农夫Don要监察他的N米乘N米(2N500,000)的正方形田园的围栏。该围栏的一角在原点(0，0)上，另一对角則在坐标点(N，N)上,围栏的边平行於X轴及Y轴。围栏上有些支柱,這些支柱分別立在围栏的四個角上及围栏的每条边上每隔1米的地方,因此整个围栏上就有4N根支柱。這些支柱是垂直的，而且可以认为其半径为0。农夫Don希望知道，当他站在田园中的某一
36、点时他可以看到的支柱的数量。 农夫Don的田园內有R块巨石(1R30,000)阻碍他的视线。因為他不夠高，无法从巨石上面望过去，因此有些支柱看不到。巨石的底部是一个面积不为零的凸多边形,而多边形的端点坐标均为整数。巨石垂直地立在地上。巨石之間不重叠，互相之間不接触，巨石与农夫Don或围栏也不接触。农夫Don所站立的地方也不接触围栏，他也不会站在巨石內或巨石上。 给定农夫Don的围栏大小,其內的巨石的位置及形状，以及农夫Don所站立的位置,求出Don在该位置上可以看到的支柱数量。如果一根支柱在农夫Don的视线上刚好和巨石的边重叠，则农夫Don是看不到该支柱的。可视边界可视边界将统计将统计农夫农夫
37、位置位置“可视可视”的正方形四条边界上的整点的正方形四条边界上的整点总数问题，简化为计算农总数问题，简化为计算农夫夫站立位置到正方形下边界站立位置到正方形下边界线的可视点数的问题线的可视点数的问题。 我们按逆时针顺序枚举多边形i的每一个顶点（1ir），不断调整最左端的顶点序号min和最右端的顶点序号max，并按照下述方法计算区间lt、rt若第j个顶点位于农夫位置的上方(yijy01)，则分析：若第j个顶点位于农夫位置的左方（xijx01），则设区间左端点lt为0；否则设区间右端点rt为n-1若第j个顶点位于农夫位置的下方(yijy01)，则计算截点的x坐标（hv为截点存在标志）x0=x01+*
38、y01）lt=rt=如果正方形下边界线上不存在截点（hv=false），是不是意味着正方形下边界线上的顶点都是可视点呢？不一定即过农夫位置引垂直于X轴的射线，如果与凸多边形i最左的顶点min、最右的顶点max所连线段不相交，则凸多边形i不挡住正方形下边界线上的任何整点；否则凸多边形i挡住了正方形下边界线。相相交的标志是农夫位置的交的标志是农夫位置的x坐标位于顶点坐标位于顶点min的的x坐标坐标和顶点和顶点max的的x坐标之间坐标之间（(ximinx01ximax)）且交点且交点在农夫位置之下（在农夫位置之下（yimin+*(x01-ximin)y01）构建区间表构建区间表xx和和tp 区区间间
39、表表xxxx。xx存储正方形下边界线上被r个凸多边形挡住的所有区间；区间表元素的类型区间表元素的类型tptp。其中tpi=1，表明排序前的xxi为区间左端点的x坐标；tpi=-1，表明排序前的xxi为区间右端点的x坐标， lg:=0;区间表的长度清零 for i:=1 to r do依次处理每个凸多边形 begin 计算正方形下边界线被凸多边形计算正方形下边界线被凸多边形i i挡住的区间挡住的区间 lt,rtlt,rt xxlg+1:=lt; xxlg+2:=rt;将lt,rt存入区间表 tplg+1:=1; tplg+2:=-1; inc(lg,2)end;for计算计算正方形正方形下边界线
40、上被挡住的整点数下边界线上被挡住的整点数a1目标是计算正方形下边界线上被各个区间的线段覆盖过的长度a1（简称a1为测度）。这里有两种做法：建立线段树，最后统计测度；将xx和tp中所有区间的端点lt,rt进行排序，根据tp表自左而右扫描一遍，利用统计点值的和s统计测度a1： sort(1,lg);对区间表进行分治排序 s:=0; al:=0;初始化点值和与测度 for i:=1 to lg do(从左到右扫描区间表的每一个元素) if tpi=1一个新区间开始 then begin if s=0 then lt:=xxi;若点值和为0，则该截点作为连续区间的左端点 inc(s) 点值和+1 en
41、dthen else begin(若当前区间结束，统计测度) if s=1 then al:=al+trunc(xxi)-trunc(lt-zero)+ord(lt1e-6); dec(s) 点值和-1end;else显然，正方形下边界线上的可视点数为n-a1。主程序主程序 输入信息； ans:=0; for t:=1 to 4 do分别处理正方形四条边 begin 构建区间表构建区间表xxxx和和tptp； 计算计算正方形正方形下边界线上被挡住的整点数下边界线上被挡住的整点数a1a1； ans:=ans+n-al;将农夫所能看到的正方形t边上的支柱数n-a1记入ans for i:=0 to
42、 r do将每一个凸多边形逆时针转90度，以便将下一条边旋转至下底边 for j:=1 to pi do begin x0:=xij;y0:=yij;xij:=n-trunc(y0); yij:=trunc(x0) endfor end;for 输出农夫Don所能看到的支柱数ans；线段树的总结线段树的总结1、线段树经过左右分割以后具有二叉排序树的性质；2、线段树的建立方式非常适用于处理线段，对于点的问题，亦可以推广应用3、线段树上的一个结点分裂为两个半区间的时候实际上是通过一个中间点来分割的；4、在线段树上需要设立左右指针；结点表示区间，但处理点的时候不需要保留这样的区间。一定范围内计数问题
43、的特点一定范围内计数问题的特点1描述简单描述简单2要求对数据动态维护，动态计算要求对数据动态维护，动态计算3解决手段：特殊的统计模式和结解决手段：特殊的统计模式和结构构怎样用怎样用静态方法解决动态统计的静态方法解决动态统计的问题？问题？一种静态统计方法一种静态统计方法例题IOI2001MOBILES：在一个N*N的方格中，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子矩阵(x1,y1)-(x2,y2)中所有元素的和；修改的规则是指定某一个格子(x,y)，在(x,y)中的格子元素上加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1N1024
44、,提问和修改的总数可能达到60000条。一维一维序列求和序列求和设序列的元素存储在a中，a的下标是1.n的正整数，需要动态地更新某个ax的值，同时要求出ax1到ay1这一段所有元素的和（sum(1,y1)-sum(1,x1-1)）。对于序列对于序列a1.na1.n，设一个数组设一个数组C1.nC1.n其中Ci=ai-2k+1+aik为i在二进制下末尾0的个数。例如1001010110010000k=4C1001010110010000=a1001010110000001+a1001010110010000计算Cx对应的2kLOWBIT（x）=2k=xand(xxor(x-1)修改一个ax的值与
45、C的哪些下标变量p相关？例如x=76=(1001010)2，从形式上进行观察，可以得到：p1=1001010p2=1001100p3=1010000p4=1100000p5=10000000修改修改Cp1,Cp2,procedureUPDATA(x,A)beginpxwhile(p0)dobeginansans+Cppp-LOWBIT(p)endreturnansendCp=ap-2k+1+ap下一个下一个p=x-2k推广为原来的二维问题，把C构造成Cx，y，其每一维定义与原来相同。推广后算法：两层嵌套，一次维护费用为O(log2n)在解决点统计问题时，多考虑在解决点统计问题时，多考虑静态二叉
46、排序树静态二叉排序树二分法的虚拟实现树二分法的虚拟实现树集合3，4，5，8，19，6静态二叉排序统计树实现静态二叉排序统计树实现是把所有要处理的点坐标离散化，形成一个排序的映射，例如我们称为X映射，并且设其中一共有n个不同的对象。例如在上例中，X=3，4，5，6，8，19，n=6。第一个点第一个点静态二叉排序统计树静态二叉排序统计树与一般二叉排序树的区别与一般二叉排序树的区别1、一般二叉排序树的结构由输入顺序决定的2、静态二叉排序统计树的结构由区间中间点决定，因此需要预先排序把X映射中的点值填入到树中，使它有上面的构造。这里我们选择静态结构作为对二叉树的支持。将二叉树的结点从上到下，从左到右进
47、行编号，并令根结点的编号为1。即上图中对应的编号应该是：对于任何一个编号为i的结点，它的左儿子编号自然为i*2，右儿子编号为i*2+1。现在要把X的映射填入到数组V中去。V1.n应该保存相应位置上的点值。注意到对V对应的二叉树进行中序遍历的结果就对应X中的映射，所以可以通过递归的方法建立V：构造过程构造过程1 1 递归递归：建立所有点坐标的映射Xp0作为X映射中的指针procedureBUILD(ID:integer)beginif(ID*2n)thenBUILD(ID*2);pp+1；VID=Xp；if(ID*2+1n)thenBUILD(ID*2+1);end在主程序中调用BUILD(1)
48、构造过程构造过程2 2 非递归非递归方法，依次找出当前点的后继点的下标第一个点first一定为最下层最左边的一个位置,若n个点有L层,则first=2L-1functionfirst:integerbeginlevel1,tot=2while(tot-1n)dobeginlevellevel+1；tottot*2endreturntotdiv2end若当前的点位置为now：如果它有右儿子，即now*2+1x)thennownow*2x在在now的左子树方的左子树方向向elsenownow*2+1x在在now的右子树的右子树方向方向untilfalseEnd删除的方法是类似的2 2、插入时，计算
49、每个结点以及其左子树上顶点的、插入时，计算每个结点以及其左子树上顶点的总数总数设 LESS表 示 值 小 于 等 于 根 结 点 值 的 总 数 (LESSI=SUMI-SUMI*2+1)：procedureINSERT1(x)Beginnow1repeatif(xx)thennownow*2计算左儿子指针elsenownow*2+1计算右儿子指针untilfalseend利用二叉排序统计树解决利用二叉排序统计树解决MOBILESMOBILES问题问题这个过程与前一个大同小异。实际上LESSI=SUMI-SUMI*2+1。举这个例子在于说明利用二叉排序树的结构，是很容易结合具体的问题进行变化的
50、。我们对其变化，甚至也可以利用来解决MOBILES问题。只要将刚才LESS的定义作一点变化，令它为根及其左树上所有点上的权和。如果要在ax上增加A。可以很容易得到：procedureINSERT2(x,A)beginnow1repeatif(xx)thennownow*2elsenownow*2+1untilfalseend求求a1.x的元素和的元素和SUM(x)functionSUM(x):longintbeginans0now1repeatif(Vnowx)thennownow*2elsenownow*2+1untilfalsereturnansend例题例题采矿采矿(KOP)金矿的老师傅
51、年底要退休了。经理为了奖赏他的尽职尽责的工作，决定送他一块长方形地。长度为S，宽度为W。老师傅可以自己选择这块地。显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上，它也应当被计算在内。任务：读入采金点的位置。计算最大的价值。输 入 ： 文 件 KOP.IN的 第 一 行 是 S和 W，(1=s,w=10000);他们分别平行于OX坐标和OY坐标，指 明 了 地 域 的 尺 寸 。 接 下 来 一 行 是 整 数 n(1=n=15000)，表示采金点的总数。然后是n行，每行两个整数，给出了一个采金点的坐标。坐标范围是(-30000=x,y=
52、30000)。输出：一个整数，最多的采金点数。样例图示样例图示初步，对初步，对X离散化后，图示离散化后，图示1、对于每一种坐标y，建立成两个点事件(y,+1),(y+w+1,-1)，例如在一个带状区域内有5个点的纵坐标分别是5，3，9，1，9，w=2，标成(1,+1),(4,-1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1),(9,+1),(12,-1),2、将他们按照y的坐标排序，得(1,+1),(3,+1),(4,-1),(5,+1)，(6,-1),(8,-1),(9,+1),(9,+1),(12,-1),(12,-1)3、把后面的标号反映在一个y
53、坐标的映射上，然后从低到高求和坐标下的求和，这些和中最大的一个就是该带状区域中一个包含最多点数的矩形在插入或者删除一个点事件之后，能够维持坐标下的值；能够在很短时间内得到中最大的一个值。实现：实现：SUMnow对应子树上所有+1，-1标号的和。实现极简单MAXSUMnow，子树上和最大的一个前缀值。MAXSUM1是一种状态下得到最优解。如何维护？MAXSUM有哪几种可能？1最大值在左树上；2最大值正好包含根结点；3最大值在右树上。自下而上维护树的特性自下而上维护树的特性procecureprocecure INSERT(y,k) INSERT(y,k)beginbegin now 1 now
54、1repeat repeat 向下找到向下找到y y所在的结点所在的结点 if Vnow=y then breakif Vnow=y then breakif Vnowy then nownow*2+1if Vnowy then nownow*2+1 else nownow*2 else nownow*2until false;until false;Repeat再再向向上上，对对路路径径上上的的每每个个点点的的SUM和MAXSUM进进行修改行修改 SUMnowSUMnow+kMAXSUMnowMax对取得连续和最大值的3种情况进行决策MAXSUMnow*2, 最大值在左树上SUMnow-SU
55、Mnow*2+1,最大值正好包含根结点SUMnow-SUMnow*2+1+MAXSUMnow*2+1最大值在右树上nownowdiv2untilnow=0End;二分法虚拟实现树二分法虚拟实现树二叉树使用之前必须构造出一个空的二叉树对于任何一个有序表，在对其进行二分查找时，实际上就等于在一个二叉树上进行查找对于一个有序表1，3，4，8，9的二分查找，等价于在如下图的二叉排序树上进行查找：m取中间位置值，即为一棵树的树根，它左边的所位置值即取中间位置值，即为一棵树的树根，它左边的所位置值即l,m-1构成了其左子树上的形态，而构成了其左子树上的形态，而m+1,r构成了右子树上的形态构成了右子树上的
56、形态。等价的二叉排序树是平衡二叉树。最多等价的二叉排序树是平衡二叉树。最多lognlogn次查找就可以指定次查找就可以指定的结点。的结点。举插入结点的例子，来说明这种虚实现的方法举插入结点的例子，来说明这种虚实现的方法设设LESS表示根及其左树上结点的个数：表示根及其左树上结点的个数：procedureINSERT(x)beginl1,rnwhile(l=r)dobeginm=(l+r)div2ifx=VmthenLESSmLESSm+1ifx=VmthenbreakifxVmthenrm1elselm+1endend例例4在在一一个个平平面面直直角角坐坐标标系系上上有有n个个点点，n最最多多
57、为为15000，要要求求每每个个点点的的左左下下方方有有多多少少个个点点，也也就就是是说说对于每个点对于每个点xi,yi，求满足求满足xjxi并且并且yjyi的的j的个数的个数。1、按照x为第一关键字、y为第二关键字的顺序对所有点进行升序排列2、对排好序的y坐标建立映射关系，放在V数组中，并按照先前点排序的顺序依次把各个y插入到计数用的LESS中去，同时就可以得到一个点左下方的值。 functionINSERT-AND-GET(y):integerbeginl1,rnans0while(l=r)dobeginm=(l+r)div2ify=Vmthenansans+LESSmify=Vmthen
58、breakifyVmthenrm1elselm+1endreturnansEnd复杂度为O(logn) 例题例题 最长下降序列最长下降序列给定一个整数序列a，求最长下降序列的长度。设mi为ai的前缀中（包括ai）的最长下降序列的长度。该序列中ai前的整数为api1 1、最基本的解决方法最基本的解决方法O（n2)对P进行特殊的限制，即在所有等价的(相同长度)决策j中，P选择aj最大的那一个在处理完a1.x-1之后，对于所有长度为Mx-1的下降序列，Px的决策只跟其中末尾最大的一个有关。用另外一个动态变化的数组b，当我们计算完了ax之后，a1.x中得到的所有下降序列按照长中得到的所有下降序列按照长
59、度分为度分为L类类，每一类中只需要一个作为代表，这个代表在这个等价类中末尾的数最大，我们把它记为bj,1jL。处理当前的一个数ax，我们无需和前面的aj（1jx-1）作比较，只需要和bj（1jL)进行比较。首首先先，如如果果ax=b1，这时这时ax仅能仅能构成长度为构成长度为1的下降序列，同时它又必然是的下降序列，同时它又必然是最大的，所以它作为最大的，所以它作为b1的代表的代表,b1=ax。如果前面的情况都不存在，我们肯定可以如果前面的情况都不存在，我们肯定可以找到一个找到一个j,2jL,有有bj-1ax,bjax，这时分析，这时分析，ax必然接在必然接在bj-1后面，行成后面，行成一个新的
60、长度为一个新的长度为j的序列。的序列。 这几种情况实际上都可以归结为：处理这几种情况实际上都可以归结为：处理axax，令，令bL+1bL+1为无穷小，为无穷小，从左到右找到第一个位置从左到右找到第一个位置j j，使，使bjax,bjax,然后则只要将然后则只要将bj=ax,bj=ax,如果如果j=L+1,j=L+1,则则L L同时增加。同时增加。x x处以前对应的最长下降序处以前对应的最长下降序列长度为列长度为Mx=jMx=j。顺序查找顺序查找L0；下降序列的最大长度初始化forx1tondobeginbL+1无穷小j1从左到右找到第一个使得bjax的位置jwhile(bjax)dojj+1b
61、jaxifjLthenLjend顺序查找更改成二分法查找顺序查找更改成二分法查找L0下降序列的最大长度初始化fori1tondobeginj1;kL;在b1.bL中二分法查找第一个使得bjax的位置jwhile(jk)do改为二分法查找beginm(j+k)div2;ifbmaithenjm+1elsekm-1;endifjLthenLL+1；bjaiend卫星探测（卫星探测（Detect）【问题描述问题描述】A国最近检测到了B国内有不正常的辐射，经调查发现，这是因为B国正在耗资百亿研制新式武器连环阵。可是，由于B国对此武器的高度保密措施，A国的间谍甚至无法确定出连环阵的具体位置。不过，A国的
62、卫星还是可以找出连环阵所在的基地的。我们现在知道该基地是一个边上含有放射性物质的凸多边形。经研究发现，在这个凸多边形所在的平面内，它具有如下性质：包含坐标原点；任意两条边不在同一直线上；没有和x轴或y轴平行的边；所有顶点的x坐标和y坐标都是整数。现在A国可以通过卫星发出无限大的扇形探测波，与该凸多边形所在平面交于一条直线。不过该直线不是与x轴平行，就是与y轴平行。通过反射信号，我们可以确定该直线与凸多边形的交点个数和所有交点的坐标（如果有的话）。现在，需要你写一个程序，通过控制卫星发出的探测波来确定这个凸多边形。1、通过二分法确定凸多边形的左端顶点和右端顶点、通过二分法确定凸多边形的左端顶点和
63、右端顶点我我们们通通过过readx（at，nm，y1，y2）过过程程询询问问直直线线x=at与与凸凸多多边边形形交交点点的的个个数数nm和和两两个个交交点点坐坐标标y1、y2。rcdat,1.3为为x=at与与凸凸多多边边形形交交点点的的y坐标和交点个数坐标和交点个数Procedure readx(at:longint;var nm:longint;var y1,y2:double);询问直线x=at与凸多边形的相交情况begin if rcdat,10 如果以前询问过，则直接返回询问结果 then begin nm:=round(rcdat,3);y1:=rcdat,1; y2:=rcdat
64、,2 endthen else begin nm:=ask_x(at,y1,y2);询问直线x=at与凸多边形的交点 if y1y2y1和y2按照递增排列 then begin y1:=y1+y2;y2:=y1-y2;y1:=y1-y2 end;then rcdat,1:=y1;rcdat,2:=y2; rcdat,3:=nm记录询问结果 endelseend;readxfillchar(rcd,sizeof(rcd),0); 询问结果初始化 hd:=-10000; tl:=0; md:=0;设定左端顶点所在的区间，交点个数初始化 while true do begin md:=(hd+tl)
65、 div 2;将询问的直线设在区间中点处 readx(md,nm,y1,y2);计算该直线与凸多边形的交点y1、y2和交点个数nm if nm=1 then break;若仅有一个交点，则退出循环 if nm=0 then hd:=md+1若没有交点，则取右区间 else tl:=md-1若有两个交点，则取左区间 end;while x1:=md;y1:=round(y1);确定左端顶点的坐标hd:=0; tl:=10000; md:=0;设定右端顶点所在的区间，交点个数初始化while true do begin md:=(hd+tl) div 2;将询问的直线设在区间中点处 readx(m
66、d,nm,y1,y2);计算该直线与凸多边形的交点y1、y2和交点个数nm if nm=1 then break;若仅有一个交点，则退出循环 if nm=2 then hd:=md+1若有两个交点，则取右区间 else tl:=md-1若没有交点，则取左区间 end;while显然，通过上述运算后，（x1，y1）为凸多边形最左方顶点的坐标；（md，y1）为凸多边形最右方顶点的坐标 2、按照先下方、后上方的顺序计算凸多边、按照先下方、后上方的顺序计算凸多边形的顶点坐标形的顶点坐标 在找出凸多边形的左端点和右端点之后，由左端点开始，沿着上方的路径和下方的路径，逐步找出凸多边形的其他顶点。其中每次从
67、当前顶点（X0，Y0）开始，先询问直线XX01确定下一条边的斜率tg=y-y0然后二分地寻找斜率开始发生变化的顶点，这个顶点就是下一个顶点 计算与凸多边形的下一个顶点相邻的两计算与凸多边形的下一个顶点相邻的两条直线条直线每次二分查找的边界不必定得过大。由于之前我们已经进行过了一些询问，询问的结果存储在rcd数组中。我们可以充分利用已得到的信息，通过rcd数组限制边界范围，即确定一个顶点在rcd数组中哪两条相邻直线之间，将这两条直线设为下一次询问的边界。设目前已得出凸多边形的第n个顶点为（xn，yn），尚待计算的下一个顶点在rcd数组中的直线x=lt和直线x=rt之间，这两条相邻直线与凸多边形相
68、交的情况存储在rcdlt和rcdrt中。凸多边形与直线x=lt的交点（lt，rcdlt，1）(计算上方顶点时交点为（lt，rcdlt，2）)连接（xn，yn）的直线斜率=tg；凸多边形与直线x=rt的交点（rt，rcdrt，1）(计算上方顶点时交点为（rt，rcdrt，2）)连接（xn，yn）的直线斜率tg。我们从xn+1出发，由左而右计算直线x=lt；从凸多边形的右端点的x坐标-1出发，由右而左计算直线x=rt：结合跨度结合跨度kd二分查找二分查找由于直线x=lt和直线x=rt是目前询问到的两条直线，因此其在x轴的间隔完全可能大于1。如何以尽可能少的询问次数找到位于两条直线间的凸边形顶点（x
69、n+1，yn+1）呢？凸边形的边（xn，yn），（xn+1，yn+1）经过点（xn+1，y），由此得出该边的斜率为tg=y-yn。由于凸边形顶点（xn+1，yn+1）的坐标为整数，因此位于x=xn与x=xn+1间的有些直线不会与斜率tg的直线交与整数坐标，这些直线不必询问。 为了尽可能将这些顶点从询问范围内剔除，我们将斜率tg化为一个既约分数A/B，把B（而不是1）作为询问的“跨度”，即每一次询问，x直线的间隔距离为B。这个B值可以枚举。我们通过函数get_kd(tg)计算询问的“跨度”Bfunction get_kd(x:double):longint;求跨度 var i:longint;
70、begin get_kd:=0; for i:=1 to 20000 do if abs(x*i-round(x*i)1e-6 then begin get_kd:=i; exit endend;get_kd按照先下方、后上方的顺序计算凸多边形的顶点坐标按照先下方、后上方的顺序计算凸多边形的顶点坐标 txtx:=:=md;nmd;n:=1; :=1; 记下记下凸多边形左端凸多边形左端的的x坐标坐标 repeat repeat从顶点从顶点1 1出发，计算凸多边形下方各边的顶点坐标出发，计算凸多边形下方各边的顶点坐标 readx(xn+1,nm,y1,y2); readx(xn+1,nm,y1,y
71、2);计算计算（xnxn，ynyn）至（至（xn+1xn+1，y1y1）的斜率的斜率tgtg tgtg:=y1-yn;kd:=:=y1-yn;kd:=get_kd(tgget_kd(tg););计算跨度计算跨度kdkd ltlt:=xn; :=xn; rtrt:=:=txtx; ; 与第与第n+1n+1个顶点相邻的两条直线初始化个顶点相邻的两条直线初始化 for i:=xn+1 to for i:=xn+1 to txtx do do由左而右搜索左邻直线由左而右搜索左邻直线x=x=ltlt if (rcdi,10) and (abs(rcdi,1-yn)/(i-xn)-tg)1e-6)then
72、 if (rcdi,10) and (abs(rcdi,1-yn)/(i-xn)-tg)1e-6)then ltlt:=i;:=i; for i:=tx-1 for i:=tx-1 downtodownto xn+1 do xn+1 do由右而左搜索右邻直线由右而左搜索右邻直线x=x=rtrt if (rcdi,10) and (abs(rcdi,1-yn)/(i-xn)-tg)1e-6)then if (rcdi,10) and (abs(rcdi,1-yn)/(i-xn)-tg)1e-6)then rtrt:=i;:=i; hdhd:=(:=(lt-xn+kdlt-xn+kd*10000)
73、 div kd-10000;*10000) div kd-10000;结合跨度求询问的范围结合跨度求询问的范围 tl:=(rt-xn+kd*10000)divkd-10000; while while hdhd tltl do do二分询问二分询问, ,确定第确定第n+1n+1个顶点个顶点的的x x坐标坐标 begin begin mdmd:=(hd+tl+1) div 2;:=(hd+tl+1) div 2;计算询问范围的中间点计算询问范围的中间点 readx(xn+mdreadx(xn+md*kd,nm,y1,y2); *kd,nm,y1,y2); 询问询问x1=x1=xn+mdxn+md
74、* *kdkd与凸多边形相交的情况与凸多边形相交的情况 if if abs(y1-yn)/(kd*abs(y1-yn)/(kd*md)-tgmd)-tg)1e-6)1e-6若若（x1,y1x1,y1）至至（xn,ynxn,yn）的的斜斜率率等等于于tgtg，则取右区间；否则取左区间则取右区间；否则取左区间 then then hdhd:=:=mdmd else else tltl:=md-1:=md-1 end;while end;while readx(xn+hdreadx(xn+hd*kd,nm,y1,y2);*kd,nm,y1,y2);询问询问x=x=xn+hdxn+hd* *kdkd与
75、凸多边形相交的情况与凸多边形相交的情况 inc(n); inc(n); xn:=xn-1+kd*xn:=xn-1+kd*hdhd; ; yn:=round(y1) yn:=round(y1) 凸凸多多边边形形的的第第n+1n+1个个顶顶点为点为（xn+hdxn+hd* *kdkd，y1y1） until xn=until xn=txtx;直至到达凸多边形的右端顶点为止直至到达凸多边形的右端顶点为止 m:=1; m:=1; 从顶点从顶点1 1出发，计算凸多边形上方各边的顶点坐标出发，计算凸多边形上方各边的顶点坐标 repeatrepeat readx(xm+1,nm,y1,y2); readx(
76、xm+1,nm,y1,y2); 计计算算（xnxn，ynyn）至至（xn+1xn+1，y2y2）的的斜斜率率tgtg y1:=y2; y1:=y2;取上方交点的取上方交点的y y坐标坐标 tgtg:=y1-ym;:=y1-ym; kdkd:=:=get_kd(tgget_kd(tg););计算跨度计算跨度kdkd ltlt:=xm; :=xm; rtrt:=:=txtx;与第与第n+1n+1个顶点相邻的两条直线初始化个顶点相邻的两条直线初始化 for i:=xm+1 to for i:=xm+1 to txtx do do由左而右搜索左邻直线由左而右搜索左邻直线x=x=ltlt if if (
77、rcdi,10) (rcdi,10) and and (abs(rcdi,2-ym)/(i-xm)-tg)1e-6)then (abs(rcdi,2-ym)/(i-xm)-tg)1e-6)then ltlt:=i;:=i; for i:=tx-1 for i:=tx-1 downtodownto xm+1 do xm+1 do由右而左搜索右邻直线由右而左搜索右邻直线x=x=rtrt if if (rcdi,10) (rcdi,10) and and (abs(rcdi,2-ym)/(i-xm)-tg)1e-6)then (abs(rcdi,2-ym)/(i-xm)-tg)1e-6)then r
78、trt:=i;:=i; hdhd:=(:=(lt-xm+kdlt-xm+kd*10000) div kd-10000;*10000) div kd-10000;结合跨度求询问的范围结合跨度求询问的范围 tltl:=(:=(rt-xm+kdrt-xm+kd*10000) div kd-10000;*10000) div kd-10000;while while hdhd tltl do do 二分询问二分询问, ,确定第确定第n+1n+1个顶点的个顶点的x x坐标坐标 begin begin mdmd:=(hd+tl+1) div 2;:=(hd+tl+1) div 2;计算询问范围的中间点计算
79、询问范围的中间点 readx(xm+mdreadx(xm+md*kd,nm,y1,y2);*kd,nm,y1,y2);询询问问直直线线x1=x1=xn+mdxn+md* *kdkd与与凸凸多多边边形形相相交的情况交的情况 y1:=y2; y1:=y2;取上方交点的取上方交点的y y坐标坐标 if if abs(y1-ym)/(md*abs(y1-ym)/(md*kd)-tgkd)-tg)1e-6)r then search:=1 else begin if fl,r=flag then若尚未计算出顶点l顶点r对应子树的最高分值 for i:=l to r do枚举每一个可能的子根i begin
80、 now:=search(l,i-1)*search(i+1,r)+fi,i;计算以i为根的子树的分值 if nowfl,r then若该分值为目前最高，则记入状态转移方程，并记下子根 begin fl,r:=now;wayl,r:=i;end;then end;for search:=fl,r;返回顶点l顶点r对应子树的最高分值 end;elseend; search 2、输出加分二叉树的前序遍历、输出加分二叉树的前序遍历递归调用递归调用search(1,n)后得出的后得出的way给出了加分二叉树的结构，其中给出了加分二叉树的结构，其中wayi,j为该树中顶点为该树中顶点i顶点顶点j的根序号
81、。由于二叉树中序遍历的的根序号。由于二叉树中序遍历的顺序为顺序为1n，因此因此1wayi,j-1为左子树，为左子树，wayi,j+1j为右子树为右子树。我们按照根。我们按照根左子树左子树右子树的顺序对加分二叉树进行前序遍右子树的顺序对加分二叉树进行前序遍历。历。procedure procedure writeout(l,rwriteout(l,r : : integer);integer);前前序序遍遍历历顶顶点点l l顶顶点点r r对对应应的子的子树树 begin begin if lr then exit; if lr then exit; if if firstwritefirstwr
82、ite then then firstwritefirstwrite:=false:=false else write( ); else write( );顶顶点点间间空格分开空格分开 write(wayl,r); write(wayl,r);输输出子根出子根 writeout(l,wayl,r-1); writeout(l,wayl,r-1); 前序遍前序遍历历左子左子树树 writeout(wayl,r+1,r); writeout(wayl,r+1,r);前序遍前序遍历历右子右子树树 end;writeoutend;writeout 3、主程序、主程序 read(n);read(n);读
83、顶点数读顶点数 for i:=1 to n do for i:=1 to n do状态转移方程初始化状态转移方程初始化 for j:=i to n do fi,j:=-1; for j:=i to n do fi,j:=-1; for i:=1 to n do for i:=1 to n do begin begin read(temp); read(temp);读顶点读顶点i i的分值的分值 fi,i:=temp;wayi,i:=i; fi,i:=temp;wayi,i:=i;顶点顶点i i单独成一棵子树单独成一棵子树 end;for end;for writeln(search(1,n);
84、 writeln(search(1,n);计算和输出最高加分计算和输出最高加分 firstwritefirstwrite:=true;:=true;设立首顶点标志设立首顶点标志 writeout(1,n); writeout(1,n);前序遍历二叉树前序遍历二叉树 writelnwriteln; ;草莓（草莓（Berry）尽尽管管不不少少人人都都吃吃过过鲜鲜美美的的草草莓莓，却却很很少少有有人人真真正正观观察察过过野野草草莓莓的的生生长长。它它们们从从自自己己的的枝枝上上伸伸出出一一根根根根长长长长的的触触须须，遇遇到到合合适适的的地地方方就就会会扎扎根根发发芽芽，长长出出一一株株新新的的草草
85、莓莓。所所以以，当当你你在在森森林林中中遇遇到到一一株株草草莓莓的的时时候候，通通常常就就意意味味着着你你会会在在它它的的周周围围找找到到一一片片草草莓莓田田。但但这这些些草草莓莓并并非非能能够够无无忧忧无无虑虑地地生生长长，树树林林中中穿穿梭梭的的鸟鸟儿儿和和偶偶尔尔路路过过的的鹿鹿群群都都喜喜欢欢吃吃这这种种美美味味的的浆浆果果。不不过过，草草莓莓最最大大的的威威胁胁却却是是来来自自那那些些贪贪吃吃的的棕棕熊熊。他他们们不不但但可可以以吃吃掉掉整整整整一一片片草草莓莓，而而且且还还会会粗粗鲁鲁地地把把一一片片草草莓莓田田搞搞得得乱乱七七八八糟糟。于于是是每每当当一一块块草草莓莓田田越越长长
86、越越大大之之后后，森森林林中中的的精精灵灵们们就就会会把把这这片片草草莓莓田田分分成成k块块种种到到k个个空空地地中中去去，以以免免被被粗粗鲁鲁的的棕棕熊熊搞搞乱乱。她她们们希希望望每每块块空空地地上上恰恰好好放放上上一一块块用用触触须须连连接接在在一一起起的的草草莓莓田田。不不过过，如如果果一一块块空空地地里里的的草草莓莓太太少少，它它们们就就会会感感到到孤孤单单，所所以以精精灵灵们们希希望望无无论论哪哪块块空空地地含含有有草草莓莓的的总总重重量量都都不不要要太太小小。可可是是天真的精灵并不知道怎样来做这件事情，你可以帮助她们吗？天真的精灵并不知道怎样来做这件事情，你可以帮助她们吗？【任务描
87、述任务描述】定义：定义：sumi表示第表示第i块草莓田中所有草莓重量的和（块草莓田中所有草莓重量的和（1 i k）。）。你的任务就是要把一片草莓田分割成你的任务就是要把一片草莓田分割成k块，且分割方案需要满足如下的条件：块，且分割方案需要满足如下的条件：l l每一块中的草莓必然是通过触须直接或者间接和其他草莓相连接的；每一块中的草莓必然是通过触须直接或者间接和其他草莓相连接的；l l这种分割方案所对应的这种分割方案所对应的x尽可能的大。尽可能的大。最后输出你的分割方案和结果。最后输出你的分割方案和结果。【输入说明输入说明】第一行为三个整数第一行为三个整数n、m及及k，n表示草莓的株数，表示草莓
88、的株数，m表示触须的数目，表示触须的数目，k为空地的数目。为空地的数目。接接下下来来的的n行行每每行行两两个个整整数数i及及bi，表表示示第第i株株草草莓莓的的重重量量是是bi克克。顺顺序序下下来来的的m行行每每行行两个整数两个整数p和和q，表示第表示第p株草莓和第株草莓和第q株草莓之间有一根触须相连接。株草莓之间有一根触须相连接。另另外外，在在所所有有这这些些数数据据的的最最后后还还有有单单独独的的一一行行包包括括一一个个整整数数d用用作作评评分分系系数数，有有关关d的说明，可以参看下面的评分方法。的说明，可以参看下面的评分方法。【输出说明输出说明】你你一一共共要要输输出出k+1行行。第第一
89、一行行为为一一个个整整数数，表表示示你你的的分分割割方方案案中中的的x。接接下下来来的的k行行，每每行行表表示示一一块块草草莓莓田田。每每行行的的第第一一个个整整数数为为ni，表表示示第第i块块田田中中的的草草莓莓株株数数。第第二二个个到第到第ni+1个整数为这些草莓的编号。请注意，这些草莓必然是通过触须相连接的。个整数为这些草莓的编号。请注意，这些草莓必然是通过触须相连接的。如何在一个链和环中计算最佳划分方案如何在一个链和环中计算最佳划分方案链：设wi为顶点i的权；si为链上的顶点1顶点i的权和，即si=；我们将链上的n个顶点划分成k个连续子区间上述方案中的x=第i块的权和=sii-sii-
90、1。显然，在所有可能的分割方案中，最大x对应的方案即为问题的解。我们采用动态程序设计方法来解决这个问题。设阶段i：待分块的顶点个数（1in）；状态j：前i个顶点待分割的块数（2jk）；决策l：将前i个顶点分割j块时，第j块首顶点的序号（jli）；fi，j为链上前i个顶点分割成j块的最大x；当最大x=fi，j时，第j块首顶点的序号l记入pi，j。显然状态转移方程为fi，1=sifi，j=minsi-sl-1，fl-1，j-1环的计算问题可以归结到链环的计算问题可以归结到链环是链首尾相接而形成的。如果选择每环是链首尾相接而形成的。如果选择每一个顶点作为链首顶点的话，则一个长一个顶点作为链首顶点的话
91、，则一个长度为度为n的环可以形成的环可以形成n条不同的链，其中条不同的链，其中在以在以st（1stn）为首顶点的链上，第为首顶点的链上，第i个顶点对应环上个顶点对应环上第第st+i-1+n*ord(st+i-1n)个顶点。我们枚举个顶点。我们枚举st（1stn），），计算以计算以st为首顶点的链的最大为首顶点的链的最大x。显然显然在在n个可能的链中，个可能的链中，x值最大的方案即为问值最大的方案即为问题的解。题的解。在一棵树中计算最佳划分方案在一棵树中计算最佳划分方案使用贪心法计算在每块权和不小于使用贪心法计算在每块权和不小于test的前提下分割的前提下分割的最多块数的最多块数 设当前分割方案
92、中每块权和的最小值为test。按照后序遍历的顺序计算每棵子树的权和。一旦一棵以x顶点为根的子树的权和“恰好”超过test，那么这棵子树的任何子树（不包括子树根）的权和都不到test，因此它们必定在一个块中（这些子树不足以构成权和至少为test的块，且子树中的任何顶点都有一条与x相连的路径），如果这个块还包含了子树外的其他顶点（这些顶点彼此间一定连通），则将这些顶点加入其它块，不会导致更差。我们给子根x设一个分离标志，表明以x顶点为根的子树可以作为单独的一块分离出树。设varvt,tk:array1.mxof boolean;vt为访问标志，其中vti=true标志顶点i已访问；vk为块的分离标
93、志，其中vkx=true，标志以顶点i为根的子树的顶点权和不小于test，这些顶点组成一个块function encode(x:integer):longint;后序遍历计算以顶点x为根的子树。计算子子树的权和不小于test的块数num和每块的分离标志tk var s0:longint; p:vtype; begin s0:=vlx; p:=gx.nt; vtx:=true;从顶点x出发，计算以其为根的子树的权和while pnil do begin if not vtp.y then s0:=s0+encode(p.y); p:=p.nt end;while if s0=test若子树的权和
94、不小于test，则块数+1，以顶点x为根的子树将进入新增加的一块，函数返回0 then begin inc(num); encode:=0; tkx:=true;endthen else encode:=s0否则返回子树的权和end;encode通过前序遍历树来计算分割方案通过前序遍历树来计算分割方案设bb:array1.1010,0.mxofinteger;最佳方案，其中bbi，0为第i块的顶点数，bbi，j为第i块中第j个顶点的序号procedure getans(x:integer);通过前序遍历树来计算分割方案var p:vtype; k:integer;begin vtx:=true
95、; p:=gx.nt;设顶点x访问标志，准备访问x的子顶点 if tkx then inc(hv);若以x为根的子树的权和不小于test，则增加一块 k:=hv;inc(bbk,0);bbk,bbk,0:=x;顶点x进入块中 while pnil do将子树中未访问的子顶点送入块中 begin if not vtp.y then getans(p.y); p:=p.nt endwhileend;getans通过二分法计算最大通过二分法计算最大x值值 设搜索区间的左指针为hd，右指针为tl。初始时hd=0，tl=s-1。我们每次设区间的中间点为x值，通过调用encode(1)计算最多分割出的块数
96、num。如果numk，则x取右区间的中间点；否则取左区间的中间点。这样依次类推，直至x=hd=tl为止，这个x值即为满足条件的最大x值。然后再次调用encode(1)，计算在最大x值下的分离标志tk，并通过调用getans（1）计算分割方案。最后，如果分割出的块数大于k，则将多余的块并入第一块。输入信息，构造树的邻接表； hd:=0; tl:=s-1;x值的搜索区间初始化 while hdtl do通过二分法计算每块权和不小于最大x值的分割方案 begin test:=(hd+tl+1) div 2;计算中间点 num:=0;块数初始化 fillchar(vt,sizeof(vt),0);顶点
97、的访问标志初始化 encode(1);递归计算块数num if num=k 若块数多于k，则取右区间；否则取左区间 then hd:=test else tl:=test-1 end;whilefillchar(vt,sizeof(vt),0);访问标志和分离标志初始化fillchar(tk,sizeof(tk),0);test:=hd; 记下最大x值num:=0; encode(1);递归计算最大x值下的分离标志tkfor i:=1 to k+1 do bbi,0:=0;每一块的顶点数设为0 hv:=0; tk1:=true;块序号初始化，顶点1首先被分离fillchar(vt,sizeof
98、(vt),0);访问标志初始化getans(1);计算分割方案while hvk do 将多余的块并入第一块 begin for i:=1 to bbhv,0 do bb1,i+bb1,0:=bbhv,i; bb1,0:=bb1,0+bbhv,0; dec(hv) 块数-1 end;while 输出块数hd；for i:=1 to hv do输出每一块的信息 begin 输出第i块的顶点数bbi,0； for j:=1 to bbi,0 do 输出第i块中顶点j的序号bbi,j； writeln end;for在一个完全无向图中计算最佳划分方案在一个完全无向图中计算最佳划分方案将将一一个个完完
99、全全无无向向图图分分成成两两部部分分的的问问题题即即为为所所谓谓的的“背背包包问问题题”。如如果果能能够够在在n个个顶顶点点中中选选取取若若干干顶顶点点，这这些些顶顶点点的的权权和和最最大大，则则被被选选中中的的顶顶点点组组成成第第一一块块，其其余余顶顶点点组组成成第第二二块块。问问题题是是，如如何何确确定定第第一一块块的的顶顶点。设点。设f，p，nm和和vt组组成成第第一一块块的的分分割割方方案案。其其中中vti为为顶顶点点i属属于于第第一一块块的的标标志志；fi,j为为前前i个个顶顶点点中中选选取取若若干干顶顶点点、其其权权和和正正好好为为j的的标标志志；被被选选取取的顶点数的顶点数为为n
100、mi,j；顶点顶点i被选中的标志为被选中的标志为pi,j。显然显然fi,j=fi-1,jor(jwi)andfi-1,j-wi1in，1jall）选取权和正好为选取权和正好为j的若干顶点，有两种选择：的若干顶点，有两种选择：vfi-1,j表表明明前前i-1个个顶顶点点中中，被被选选取取顶顶点点的的权权和和已已达达到到j，顶顶点点j未未被被选选中中，因此因此pi,j=false，nmi,j=nmi-1,j；v(jwi)andfi-1,j-wi表表明明加加入入顶顶点点i后后，权权和和正正好好为为j，顶顶点点i被被选选中，因此中，因此pi,j=true，nmi,j=nmi-1,j-wi+1经经过过上
101、上述述运运算算，使使得得问问题题变变成成了了判判定定性性问问题题。我我们们从从出出发发，按按照照递递减减方方向向枚枚举举x值值，使使得得fn，x成成立立的的x值值为为最最大大x，nmn,x即即为为第第一一块块的的顶顶点点数数。我我们们从从x出出发发，根根据据p的的指指示示，依依次次输输出出第第一一块块的的顶顶点点。显显然，第二块的顶点数为然，第二块的顶点数为n-nmn,x，未在第一块的顶点属于第二块。未在第一块的顶点属于第二块。 readln(n,m,k);读顶点数、边数和块数 for i:=1 to n do read(j,w0i);读每个顶点的权 s0:=0; w:=w0;计算权和序列 f
102、or i:=1 to n do si:=si-1+wi; all:=sn; 记下所有顶点的权和 fillchar(f,sizeof(f),0);f和nm初始化 f0,0:=true; nm0,0:=0; for i:=1 to n do枚举顶点数 begin fi,0:=true; for j:=1 to all do枚举可能的权和，计算fi,j、pi,j和nmi,j begin fi,j:=fi-1,jor(j=wi)and fi-1,j-wi; if fi,jthen if fi-1,j then begin pi,j:=false; nmi,j:=nmi-1,j endthen else
103、 begin pi,j:=true;nmi,j:=nmi-1,j-wi+1 end;else endforend;forfor i:=all div 2 downto 0 do if fn,i then break; 计算最大x writeln(i);输出最大x write(nmn,i);输出第一块的顶点数 b:=i;从最大x出发，根据p的指示计算和输出第一块的顶点 for a:=n downto 0 do beginif pa,b then beginwrite( ,a);若权和为b的顶点集中包含顶点a，则输出a,标志顶点a属于第一块，在权和中去掉顶点a的权 b:=b-wa; vta:=tr
104、ue; end;then end;for writeln; write(n-nmn,i);输出第二块的顶点数 for i:=1 to n do输出不属于第一块的顶点 if not vti then write( ,i);数据生成器（数据生成器（Jerrygen）【题题目目背背景景】小明在做NOI2003练习赛的幸幸福福的的老老鼠鼠时觉得题目太简单了，于是对原题做了一些扩展：l将原题的N从20扩展到200000。l将原题经过一条街道需要的时间改为Ti（1Ti1000000000）分钟（i为街道的编号）。l增加了一个条件：小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。即使这样，他仍然很
105、快地做了出来。于是，小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图，不过为了增大测试数据的难度，他希望你能帮他选取一组X、Y、Z，使老鼠拿到礼物的时间尽可能地大。【小小明明扩扩展展的的题题目目（注注意意，你你并并不不需需要要解解决决此此题题）】幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发，先到小狗家Y（因因为为小小狗狗家家Y离离老老鼠鼠家家X的的距离小于等于大狗家距离小于等于大狗家Z离老鼠家离老鼠家X的距离）的距离），再到大狗家Z，将两份礼物取回。卡通城由N（3N200000）个居住点和N-1条连接居住点的双向街道组成
106、，经经过过第第i条条街街道道需需花花费费Ti（1 Ti 1000000000）分钟的时间分钟的时间。可以保证，任两个居住点间都存在通路。不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？【任务描述任务描述】定义：令定义：令|AB|表示卡通城中从表示卡通城中从A点走到点走到B点需要的最少时间。点需要的最少时间。给出卡通城的地图，找到一组X、Y、Z，使得：|XY|XZ|；|XY|+|YZ|最大。并求出此时|XY|+|YZ|的值。【输输入入文文件件】输入文件jerrygen.in第一行是两个整数N（3N200000）和M（M=N-1
107、），分别表示居住点总数和街道总数。从第2行开始到第N行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1Ui,ViN，1Ti1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。【输出文件输出文件】输出文件jerrygen.out仅包含一个整数T，即|XY|+|YZ|的最大值。“以以M为起点为起点”的三条最长路径的三条最长路径任何XYZ的路径构成的集合一定是如右图所示的三叉形。|MX|,|MY|,|MZ|三条路径仅在M处有公共点（单个顶点被认作为长为零的路径）。这个图形的目标函数就是|MX|+2|MY|+|MZ|。为了满足最优性，必须满足以下两个必
108、要条件：v0|MX|MY|MZ|。v令M为根顶点，MX路径上与M相邻的顶点是A（假设M、X不重合）。若MX是以M为起点的一条最长路径，则路径AX必定是以A为根的子树中一端为A的一条最长路径。对MY、MZ也是类似的。我们简称满足这种性质的三条路径称为“以M为起点”三条最长路径。自下而上计算自下而上计算l和和t设var l:array1.4,1.mxof comp;在以x为起点的三条最长路径中，第K长的那条路径的长度为l(k，x),l4,x不影响结果,是一个暂存空间 t:array1.4,1.mxof longint;在以x为起点的三条最长路径中，第K长的路径上与x相邻的点的序号为tk,x。如果不
109、存在，令t（k，x）0 初始时l、t数组清零，之后不断地更新它们的值（t随l变化）。如果扩展出一条由x出发、长度为w的路径。按照长度递减顺序，该路径应该位于l序列的哪个位置呢，我们通过过程get_k(w，x，k)计算位置k。procedure get_k(w:comp;x:longint;var k:shortint);输入路径的出发点x和路长W，计算该路径在l序列的插入位置 beginif wl1,x then k:=1 else if wl2,x then k:=2 else if wl3,x then k:=3 else k:=4end;get_k 假设当前顶点为假设当前顶点为x，一个子
110、顶点是一个子顶点是y。显然，由显然，由x出发，途径（出发，途径（x，y）的最长路径为的最长路径为l(1，y)Wxy（Wxy为（为（x，y）的边权）。的边权）。按照路径长度递减的顺序，将该条路径的长度插入按照路径长度递减的顺序，将该条路径的长度插入l1，xl3，x的适当位置、的适当位置、y插入插入t1，xtt3，x的适当位置的适当位置。procedure encode1(x:longint);按照自下而上的顺序，计算x往下方向的前3条最长路径 var p:vtype; k,i:shortint;begin vtx:=true; p:=gx.nt; 设x已访问标志 while pnil do搜素由
111、X出发的所有未访问边 begin if not vtp.y then begin encode1(p.y); 递归搜索以p.y为根的子树 get_k(l1,p.y+p.w,x,k);计算由x出发、途径（x，p.y）的最长路径在l和t序列的插入位置 for i:=3 downto k+1 do将该路径插入l和t序列 begin li,x:=li-1,x; ti,x:=ti-1,x end;for lk,x:=l1,p.y+p.w; tk,x:=p.y end;then p:=p.nt搜索X出发的下一条未访问边 endwhileend; encode1在主程序中，通过执行下述语句fillchar(
112、vt,sizeof(vt),0); 所有顶点未访问encode1(1);自底向上计算l和t序列l数组和t数组记录了每个顶点往下方向的前三条最长路径。自上而下调整自上而下调整l和和tProcedure encode2(x,pt:longint;l0:comp);自 顶向下更新l的值。输入X、父顶点Pt和经由（x，pt）的最长路长度l0，计算x朝上方向的前3条最长路径，并更新l序列和t序列 var k,i:shortint; p:vtype; begin vtx:=true;设顶点x已访问标 get_k(l0,x,k);计算由x出发的、长度为l0的路径在l和t序列的插入位置，获得更新信息 for
113、i:=3 downto k+1 do“让位” begin li,x:=li-1,x;ti,x:=ti-1,x end;for lk,x:=l0; tk,x:=pt;“入座” p:=gx.nt;搜素由X出发的所有未访问边while pnil dobeginif not vtp.ythen if p.y=t1,x若x出发的最长路径途径（x，p.y）,则取途径（x，p.y）的次长路径，重新调整l序列和t序列 then encode2(p.y,x,l2,x+p.w) else encode2(p.y,x,l1,x+p.w);否则取途径（x，p.y）的最长路径，重新调整l序列和t序列 p:=p.nt搜索
114、X出发的下一条未访问边 endwhileend;encode2主程序主程序fillchar(vt,sizeof(vt),0); 所有顶点未访问encode2(1,0,0); 自顶向下计算x往上方向的前3条最长路径，更新l序列和t序列。可可以以看看出出：encode1过过程程是是自自底底向向上上地地达达到到目目标标的的，encode2过过程程中中则则是是自自顶顶向向下下达达到到目目标标，转转折折点点就就是是每每棵子树的根。完成两步后，最终的答案就是棵子树的根。完成两步后，最终的答案就是l(1,x)+2*l(2,x)+L(3,x)。两次遍历时每条边只处理一次，因此复杂度为两次遍历时每条边只处理一次
115、，因此复杂度为O（M）。简述另一种算法简述另一种算法1、树中的任意顶点a1为起点找一条由a1出发的最长路径，该路径的另一端点为a2的（a1至a2的路径并不是树的最长路径）。2、以该路径的另一个端点a2为起点，找一条最长路径，该路径即为树的最长路径（路径的终点为a3）。从顶点1出发计算最长路径，该路径的终点为a1；从顶点a1出发计算最长路径，该路径的终点为a2，长度为l，顶点数为j。将该路径上的顶点序列依次存入line1linej；max0；fori2toj-1do枚举该路径上的每一个中间顶点beginl1linei至a1的距离；l2l-l1；l2为linei至a2的距离l3minl1，l2；计
116、算由linei出发、不经过linei-1和linei+1的最长路径，该路径的长度为len；iflen+l3maxthenmaxlen+l3；end;for输出max+l；问题的核心为“计算以树中任意顶点为起点的最长路径”。这项工作可以通过宽度优先搜索实现，时间复杂度为O(n)。小结小结并查集并查集一般用于对集合合并和查找的运算线段树线段树一般用于线段和点的计算问题树状数组树状数组用静态方法解决动态统计问题的技巧静态二叉排序树和虚实现静态二叉排序树和虚实现解决点统计问题后根遍历后根遍历按照自下而上的方向计算思路思路在集合运算中多考虑树结构的、且经过路在集合运算中多考虑树结构的、且经过路径压缩的并查集；在平面离散点的有序统计径压缩的并查集；在平面离散点的有序统计问题中，多考虑二分法和动态程序设计。如问题中，多考虑二分法和动态程序设计。如果需要按照自下而上的方向计算，则采用后果需要按照自下而上的方向计算，则采用后根遍历。根遍历。
