2013ACM集训队论文集.pdf
2013ACM集训队论文集.pdf目录登顶计划湖南师范大学附属中学彭天翼方格取数吉林东北师大附中王康宁Two strings试题讨论17浙江省杭州学军中学罗十Catch The Penguins23浙江省杭州学军中学张闻涛浅谈分块思想在一类数据处理问题中的应用27北京市第八|中学罗剑桥搜索问题中的 meet in the middle技巧43江苏南京外国语学校乔明达浅析信息学竞赛中概率论的基础与应用57江苏省扬州中学胡渊鸣浅谈数据结构题的几个非经典解法71江苏南京外国语学校许昊然重量平衡树和后缀平衡树在信息学奥赛中的应用85浙江杭州外国语学校陈立杰浅谈环状计数问题99江苏省常州高级中学高胜寒分块方法的应用109山东胜利第一中学王子昱浅谈容斥原理121四川成都七中王迪登顶计湖南师范人学对属中学彭天翼登顶计划湖南师范大学附属中学彭天翼1题目背景爬山是一项非常有益于身心健康的运动。可是在爬山时,我们应该采取怎样的策略,才能尽快登上山的顶端呢?基于这个有趣的问题,作者思考出了下面这样一道题目2题目描述【资源限制】时间限制:2s内存限制:512MB【问题描述】二维平面上的山脉由一系列顶点确定:(x1,y).(x2,y2),,(xn,y)。相邻的两个顶点之间由线段相连(保证x严格递增),这样就构成∫一座连绵的山脉,每个点的y值代表了该点的高度。如下图所示:2013年信息学奥林匹克中国国家队侯选队员论文登顶计划湖南师范人学对属中学彭天翼我们定义山脉的内部为顶点之间的折线与x轴的所夹部分(不包括顶点之的折线)。如果顶点A与顶点B之间的连线段没有穿过山脉的内部,则我们称顶点A能看见顶点B(或B能看见A)。现在pt从某个顶点出发,想要登到山脉的顶峰(最高点),他只能在顶点之间的折线上行走。经过思考,他将采取如下的一种登山方式1.站在出发点,向左右看去,如果此时能够看到的最高山峰在左侧,则向左侧走去,否则往右侧走去。2.在行走的同时,pty仍然观察着此时左右的最高山峰,一旦发现一座比之前看到的都要高的山峰,他将向此时的最高峰走去。3.如果存在某个时刻,pty所站立的位置比左右能看到的最高峰都要高,则他到达了山脉的顶峰,此时他的爬山过程结束py想知道,采取如上的策略,从每个顶点出发,到达最高点的路程分别是多少?(平面中两点的距离等于它们之间连线段的长度)【输入格式】也 s1reaheie Av第一行一个整数n,表示山脉顶点个数。接下来n行,第i行两个整数x1y,表示第个顶点的坐标。保证x;严格递增,%互不相同(,v除外),x;都为非负整数。保证m1n的值为0。【输出格式】输出共n行:每行一个实数第i行的实数表示从第i个顶点出发,到达最高点的路程。如果输岀与标准输出的误差不超过1e-2,则该测试点得满分,否则得0分。【样例输入】62013年信息学奥林匹克中国国家队侯选队员论文登顶计划湖南师范人学对属中学彭天翼16460【样例输出】6.080.006.529.8714.97【样例解释】BC路线说明A点出发:A->BB点出发:BC点出发:C->BD点出发:D->G->DBE点出发:E->D->C->B2013年信息学奥林匹克中国国家队侯选队员论文登顶计划湖南师范人学对属中学彭天翼F点出发:F->E->D从D点出发时,看到的最高点是F,当步行至G点时,发现更高点B,转向后一直步行向B点。从其它点出发后都不需要转向数据规模与约定】所有的数据满足xi,yi≤10000测试点限制m<205-87≤709-107≤10000每个顶点都能直接看到最高点111472×3000015-20m<100003题目分析3.1简化问题题目中要求我们在爬山的任意时刻都要观察两侧当前的最高峰,让我们暂时将问题简单化:变为只有到达顶点时,才观察此时的最高峰。也就是说,现在的观测点,从无限个暂时变为有限的O)个顶点。32求一个顶点能看到的最高点设i号点往左能看到的最高点为L,往右能看到的最高点为R]。想象我们站在某个点上,初始时视线水平向左,接下来我们慢慢抬起头,直到我们的视线不再被某座山阻挡,此时我们便找到了L。设当前的顶点为A,L为B。则接下来的两个性质不言而喻:前个点都处于AB的下方(非严格)A,B为前i个点的上凸壳上两个相邻的点由于A点一定是前i个点的上凸壳的最后一个点,所以B点就是这个上凸克2013年信息学奥林匹克中国国家队侯选队员论文登顶计划湖南师范人学对属中学彭天翼的倒数第二个点。于是我们只需要用一个栈维护好前i个点的上凸壳即可,每次加入第+1个点,同时维护好凸壳的性质。由于总共只有O(m)个顶点,所以我们能在O(n)的时间内求出Li和R(i。3.3构建图论模型331暴力做法得出L[与R后,我们有了一个颇为暴力的算法:枚举从每个顶点出发,模拟路线的变化,复杂度为Omη2)或更高。这意味着我们需要继续挖掘其中被重复计算的冗余信息332建树令H代表第个顶点的高度,令=max(H[],HR印]),则意味着i点能够看到的最高峰的高度。当我们从A点出发,到达第一个满足TB>=T[A]的B点时,接下来我们要走的路程和从B点出发走的路程将完全一样。所以A到最高峰的距离就等于B到最高峰的距离再加上A到B的距离。此时让B向A连一条有向边,边权为AB之问的距离。对所有的顶点做完这样的操作以后,我们将得到一棵树(因为最高峰没有入度,其余每个点的入度为1)。从树的根节点走向任意个点的路径的边权和就等于该点到达最高峰的距离。dfs一遍即可得到每个点的答案。33.3需要解决的问题对于一个A点,如何快速求出它往左(或者往右)第一个TB]>=T[4]的点,这是一个十分经典的数据结构问题。我们可以用二分答案加区间RMQ算法解决。接下来介绍一种常数较小的做法。对所冇的顶点按从左往右的顺序建立双向链表。接下来按T值从小到大访问所有的点。每访问到一个点A,则往左第一个满足T[B>=T[4的B点就在此时双向链表中A的左侧。将A点和B点建边,然后将A点在双向链表中删除。该算法的复杂度为排序复杂度。1这样一个优美的结论着实令我惊讶。2013年信息学奥林匹克中国国家队侯选队员论文登顶计划湖南师范人学对属中学彭天翼34回归原问题至此,我们已经在O( nlogn)的排序时问内解决了一个被简化的问题,接下来让我们回归到原问题。我们具备了在任意时刻观测最高峰的能力。这会给我们带来什么变化呢?假设我们现在从A点出发,往右行走,走到某个点B上,发现了左侧的更高峰,转而向左行走。转折点B应该满足怎样的性质呢?设B所在的线段为P1-P2B将满足:B点为A点左侧某两个点的连线(设为/1,T2)与P1-P的交点前A个点将位于112连线的下方(非严格)T1,T2为前A个点的上凸壳上两个相邻的点这意味着,有意义的观测点B将是上凸壳上某条边延伸以后与山的折线段的第一个交点。由于前个点的上凸壳的总边数是O(n)的,所以有意义的观测点也是O(n)的2!那么,如何快速求出这些观测点呢?1与2的连线和P1-P有交点,这意味着当P加入凸壳后,T将要被弹出而P加入凸壳时,T没有被弹出。于是我们在维护凸壳的同时,通过求被弹出点和插入点的相关直线的交,就能得到所有观测点。复杂度仍然是O(n)的。而有限的观测点的问题我们刚刚己绎解决了。于是整个问题在O( nlogn)的时间内圆满解决。4总结11灵感来源本题的灵感来源于对现实生活中爬山问题的思考。用算法知识对现实问题进行分析,不仪能提高我们的算法分析能力,还能反映学习就是为了“学以致用”的本质目的,并且能激发我们对信息学竞赛的兴趣,让我们乐在其中。希望这种思考方式能对大家有所启发。2这又是一个令人兴奋的性质2013年信息学奥林匹克中国国家队侯选队员论文
