集训队论文答辩(彭天翼).ppt

登顶计划,湖南师大附中 彭天翼,出题灵感,怎么爬山,题目描述,山的二维平面模型：由一系列顶点给定，第一个顶点和最后一个顶点都在x轴上，相邻的两个顶点之间连边。,题目描述,定义“看见”：连线段没有穿过山的内部,题目描述,采取如下的爬山策略： 1、从一个顶点出发，向能看到的最高的顶点的方向走去 2、在行走的同时，观察此时能看到的最高顶点，一旦比以前看到的所有顶点都高，则向此时的最高顶点走去 3、走到全局最高点时，爬山结束,题目描述,最高点,新的最高点,题目描述,请输出： 从每个顶点出发，到达全局最高点的路程长度。 数据范围：N = 105,问题简单化,任意时刻观察 - 只在顶点处才观察 每当走到一个顶点时，再观察当前能看到的最高点,一个点往左右能看到的最高点,性质1： 设该点为A，编号为i，往左看到的最高点为B，则前i个点都在AB射线的下方（非严格）,一个点往左右能看到的最高点,等价于更优美的性质： A和B是前i个点的上凸壳上两个相邻的点。且A点一定是上凸壳的最右侧点。 单调栈维护凸壳的性质即可。 时间复杂度：O(n),接下来的问题,朴素做法： 枚举每个出发的顶点，模拟行走的路线,接下来的问题,如何优化： 设TA为A号点往左右能看到的最高点的高度。 当我们从A点出发，走到第一个满足TB=TA的B点时，就等价于从B出发了。 DA = DB + dis(A, B),接下来的问题,让B向A连一条边，边权为A与B之间的距离。 形成了一棵树！ 根就是最高点，根向任意一个点的路径边权和，就是该点到最高点的距离。 只要求出这棵树，就能通过一遍dfs求出答案。,第一个满足TB=TA的B,数据结构 二分答案+区间RMQ？ -更简单的双向链表,第一个满足TB=TA的B,对所有的顶点按从左往右的顺序建立双向链表。接下来按T值从小到大访问所有的点。 每访问到一个点A，则往左第一个满足TB=TA的B点就在此时双向链表中A的左侧。将A点和B点建边，然后将A点在双向链表中删除。 排序复杂度,回到原问题,任意时刻观察最高点。 假设我们现在从A点出发(A点的编号为i)，往右行走，走到某个点B上，发现了左侧的更高点，转而向左行走。转折点B应该满足怎样的性质呢？ 我们希望探究出B点的性质，并且求出所有这样的B点。,回到原问题,性质1： 设B所在的线段为P1-P2，B点为A点左侧某两个点的连线（设为T1，T2）与P1P2的交点,P2,P1,T2,T1,B,回到原问题,性质2：前i个点将位于T1T2连线的下方（非严格） -T1，T2为前i个点的上凸壳上两个相邻的点 这意味着，有意义的观测点B将是上凸壳上某条边延伸以后与山的折线段的第一个交点。,回到原问题,由于前i个点的上凸壳的总边数是O(n)的，所以有意义的观测点也是O(n)的。这让我们看到了胜利的曙光,T1与T2的连线和P1P2有交点，这意味着当P2加入凸壳后，T2将要被弹出，而P1加入凸壳时，T2没有被弹出。于是我们在维护凸壳的同时，通过求被弹出点和插入点的相关直线的交，就能得到所有观测点。复杂度仍然是O(n)的。,回到原问题,至此，问题在排序时间复杂度内得到完美解决。,回顾思路,1、简化问题条件 2、凸壳求出每个点所见最高点 3、构建树的模型 4、数据结构优化 5、回到原问题,总结与收获,命题思路：本题的灵感来源于对现实生活中爬山问题的思考。用算法知识对现实问题进行分析，不仅能提高我们的算法分析能力，还能反映学习就是为了“学以致用”的本质目的，并且能激发我们对信息学竞赛的兴趣，让我们乐在其中。希望这种命题方法对大家有所启发。,总结与收获,解题思路： 1、化繁杂为简单，问题简单化 2、化整为零，把问题分步骤解决,感谢,感