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

登顶计划 湖南师大附中 彭天翼 出题灵感 怎么爬山 题目描述 山的二维平面模型：由一系列顶点给定，第一 个顶点和最后一个顶点都在x轴上，相邻的两个 顶点之间连边。 题目描述 定义“看见”：连线段没有穿过山的内部 题目描述 采取如下的爬山策略： 1、从一个顶点出发，向能看到的最高的顶点的 方向走去 2、在行走的同时，观察此时能看到的最高顶点 ，一旦比以前看到的所有顶点都高，则向此时 的最高顶点走去 3、走到全局最高点时，爬山结束 题目描述 最高点 新的最高点 题目描述 请输出： 从每个顶点出发，到达全局最高点的路程长度 。 数据范围：N 只在顶点处才观察 每当走到一个顶点时，再观察当前能看到的最 高点 一个点往左右能看到的最高点 性质1： 设该点为A，编号为i，往左看到的最高点为B， 则前i个点都在AB射线的下方（非严格） A A B B 一个点往左右能看到的最高点 等价于更优美的性质： 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)的。 T1 T2 P1 P2 B 回到原问题 至此，问题在排序时间复杂度内得到完美解决 。 回顾思路 1、简化问题条件 2、凸壳求出每个点所见最高点 3、构建树的模型 4、数据结构优化 5、回到原问题 总结与收获 命题思路：本题的灵感来源于对现实生活中 爬山问题的思考。用算法知识对现实问题进行 分析，不仅能提高我们的算法分析能力，还能 反映学习就是为了“学以致用”的本质目的，并 且能激发我们对信息学竞赛的兴趣，让我们乐 在其中。希望这种命题方法对大家有所启发。 总结与收获 解题思路： 1、化繁杂为简单，问题简单化 2、化整为零，把问题分步骤解决 感谢