NOIP2000-2007 全部题解

完成了NOIP2000-2008的全部题解,发上来供大家参考吧,如有谬误还请多多指教。

BYVoid原创程序及题解打包下载(37 KB)

==2009.3.26== 格式重新整理,另外附上 NOIP2008 双栈排序 twostack 题解

==2009.6.30== 添加 NOIP2008 传纸条 费用流建模

目录

  • 2 NOIP2001

  • 3 NOIP2002

  • 4 NOIP2003

  • 5 NOIP2004

  • 6 NOIP2005

  • 7 NOIP2006

  • 8 NOIP2007

  • NOIP2000

    进制转换

    和正基底进制数转化方法类似,使用短除法进制转换。

    例如题中写的-15的-2进制

    -2|-15
    +—–…1
    -2|8
    +—–…0
    -2|-4
    +—–…0
    -2|2
    +—–…0
    -2|-1
    +—–…1
    -2|1
    +—–…1
    0
    倒序把每次余数写下,就是110001。所以结果是-15=110001(base-2)。

    但要注意的是在编程中,使用整除的问题。无论是C++还是Pascal,-15 整除 -2结果为7,-15 与 -2 求模结果为-1。但我们显然不能用负数作为余数,所以要满足,商 * 除数 <= 被除数。

    即结论如下:

    • 当 a / b * b <=a 时,a 整除 b 结果为 a / b。
    • 当 a / b * b >a 时,a 整除 b 结果为 a / b + 1。

    乘积最大

    题中所述的是长度为N的数字串中添加K个乘号,即把前N个数字分为W份乘积的最大值,W=K+1。

    动态规划

    状态

    • sum[i,j] 表示从第i位到第j位组成的数字
    • F[i,j] 表示把前i个数字分为j份乘积的最大值

    状态转移方程

    • F[i,j]=max{F[k,j-1]*sum[k+1,i]} (1<=k<=i-1)

    边界条件

    • F[x,1]=sum[1,x]

    目标结果

    • F[N,W]

    时间复杂度

    • O(K*N^2)

    单词接龙

    这是一道搜索题,可以转化为图论,求有向图无环最长路径。由于每个单词最多可以用两次,为方便起见,先把每个单词复制一遍,看做两个相同的单词。

    把能接龙的单词a与b之间建立一条边(a,b),边权为单词b的长度-a,b重合部分的长度。把起始字母看做一个节点,建立起始字母能接到的单词a的边,边权为a的长度。最后从起始点开始搜索最长路径即可。

    由于有向图无环最长路径是NP的,最坏情况下时间复杂度为O(N^N)。这具体取决与图的疏密程度,如果使用邻接表存储,在图不是十分密集的时候效果很好。该题测试数据中没有很强大的,所以这样就可以过了。

    有两点要注意,题上说的很不明确,容易造成误解。这两点是我在看过数据后发现的。

    1. 所谓“两部分不能存在包含关系”,是指两部分接龙后不能长度不增加。例如ababab和ababab,可以接成ababababab,但不能为ababab。
    2. 接龙时,如果两个单词接龙后的单词有多种情况,要尽可能保证接龙后的单词最长。例如cabab和ababc,一定要接成cabababc,为而不是cababc。

    方格取数

    数据不大,搜索两条路径即可。

    把每个有数字的方格看做一个顶点,该顶点与其右下的所有顶点连接一条有向边。然后从左上角的点搜索到右下角顶点的点权最长路径。搜索到一条路径以后要再搜索一遍其余节点,找出另一条最长路径。每次保留两个阶段的和的最大值。

    最后的结果就是两次路径和最长的路径的长度。

    最坏情况下时间复杂度为O(2^(N^2)),不过数据中没有能构造到这样时间复杂度的。

    NOIP2001

    一元三次方程求解

    穷举就行了,精度只有0.01,范围-100至100。

    要注意精度问题,不要直接判断式子等于0,而要判断式子的绝对值在(-0.01,0.01)之间,避免漏解。

    数的划分

    动态规划

    状态

    • F[i,j] 表示数i分为j部分的方案个数

    状态转移方程

    • F[i,j]=F[i-1,j-1]+F[i-j,j]

    边界条件

    • F[x,1]=1
    • F[i,j]=0 (j>i)

    目标结果

    • F[N,K]

    状态转移方程可以理解为:

    每种拆分方案中,最小的数为w,按照w的不同,我们可以把拆分方案分成2类:

    • w=1,我们把1除去,则剩余部分正好是i-1拆分成j-1部分,一共有F[i-1,j-1])个;
    • w>1,所有的数都>1,我们把所有的数-1,则正好是i-j拆分成j部分,一共有F[i-j,j]个。

    根据加法原理,得出以上方程。

    统计单词个数

    动态规划

    以0为第一个字符存储字符串。

    状态

    • F[i,j]为前i个字符,分为j份的最大单词个数
    • cnt[i,j]为从第i到第j的字母中单词最大个数

    状态转移方程

    • F[i,j]=max{ F[k,j-1] + cnt[k+1,i] } (0<=k<=i-1)

    边界条件

    • F[x,1]=cnt[0,x]

    目标结果

    • F[L,K] L为主串长度-1,即最后一位

    时间复杂度

    • O(K*P^2)

    Car的旅行路线

    明显的最短路径问题,顶点数最多只有400个。Floyed,Dijkstra,SPFA,用什么最短路算法都行。但这道题麻烦的地方不在最短路,而在构图上。

    首先是已知矩形三个顶点求第四个,利用对称性可以求出。首先要找出已知三个顶点组成的三角形的直角顶点,可以用向量的数量积为0,可以以用 勾股定理的逆定理。如果(x3,y3)为已知三个顶点组成的三角形的直角顶点,根据中心对称性,要求的点(x4,y4)可以表示为(x1+x2- x3,y1+y2-y3),依此类推。

    找出每个矩形的所有定点后,下面就是连接边,只要细心就不会漏。最后再算一下最短路就行了。

    由于这是一个完全图,所以时间复杂度为

    • Floyed O(N^3)
    • Dijkstra O(N^2)
    • SPFA O(N^2)

    其中算法常数最小的是SPFA,我用SPFA做了这道题,尽管Floyed就可以了。

    NOIP2002

    均分纸牌

    贪心法,一次扫描即可。

    首先算出纸牌的平均数,我们希望通过尽可能少的移动,来使所有纸牌达到平均值。

    从第一张纸牌开始扫描,把它[多出平均值的数量]向右移,[多出平均值的数量]有可能是负数。然后扫描第二张,一直到N 1张为止。扫描的过程中如果发现这张纸牌数值正好是平均值,那么直接跳过即可。

    例如样例,平均值为10。

    9 8 17 6
    第1次移动,第1张牌移 1

    10 7 17 6
    第2次移动,第2张牌移 3

    10 10 14 6
    第3次移动,第3张牌移4

    10 10 10 10
    结果为移动了3次。

    字串变换

    广度优先搜索即可,没有必要双向搜索。

    关键是状态的判重,我用的是ELFash,配合Treap平衡树,每次判断时间都是O(logK^N),根据数据规模最大也就是25次。

    平衡树中存储字符串的Hash码,由ELFHash算法生成。如果没有重复的就加入搜索队列,否则直接淘汰。

    无解有两种情况,一个是根本无法变换出目标串,另一个是在10步变换以内没有求出目标串。

    自由落体

    这是一道十分基础的题,不需要什么算法,只是需要细心。

    显然小车接到的球一定是相邻几个,只需考虑两端即可。注意小车接球时还在移动,可以接了一个球以后移动一下再接到一个。

    误差小于等于0.00001就行了。

    矩形覆盖

    离散化加搜索,在NOIP的确是一道难题。

    首先把所有点分别以横坐标和纵坐标排序,生成两组序列。

    首先从[0,500]整个区域中,分别按横向和纵向扫描若干个点,以一个矩形覆盖。然后在剩余的区域内再次分别按横向和纵向扫描若干个点,以一个矩形覆盖……直到把K个矩形覆盖完为止。

    找到面积最小的方案。

    NOIP2003

    神经网络

    这道题描述上很冗长,容易使人混淆,多次读题才能发现其意义。

    根据题意,我们要在这个网络上递推。题目上给了一个递归公式,但我们可以把它改为正向的递推。

    即 C[j]=Sum{W[i,j]*C[i]}-U[j] 以i的变化为阶段递推即可。

    为了尽可能高效,我使用了邻接表+链队列。

    题上有些地方描述的不清晰,需要来澄清。

    1. “神经元 i 最初状态”即为C[i]的初始值。
    2. 公式只对非输入层点有效。换句话说就是输入层的阈值根本没用,不用让C[i]减去U[i]。
    3. “仅输出最后状态非零的输出层神经元状态”,实际上是要求输出C[i]>0的i和C[i]。

    侦探推理

    看似简单的一道题,但很一次难拿到满分。

    显然需要枚举所有解,输出唯一解,无解则输出Impossible,多解则输出Cannot Determine。

    枚举谁说的是真话,是个愚蠢的策略。这样最多会有C(M,N)种可能,运行要超时不说,程序写起来还十分麻烦。由于只存在两个事实,即谁是凶手和今天是星期几。我们枚举这两个事实即可,仅有M*7种可能。

    输入格式是个陷阱,很容易出错。为避免错误发生,原则就是字符串完全匹配,区分大小写。在读入的过程中,我们可以直接去掉“废话”,即与事实无关的话。

    在判断谁说的是真话,谁说的是假话的时候,会出现一个人说的话前后矛盾,可能有悖论的产生,这时要直接跳过这种情况。

    有人可能会不说一句话!对于这种情况,这些人是算成说真话的人呢?还是算成说假话的人?很显然,有多种可能。所以对于输入中给出的“始终说谎的人数N”,只要满足(说假话的人<=N<=说假话的人+不说话的人),即可认定为一个解。

    加分二叉树

    动态规划

    状态

    • F[i,j] 为中序遍历中第i到第j个节点所组成的子树的最大加分
    • root[i,j] 为中序遍历中第i到第j个节点所组成的子树的根

    状态转移方程

    • F[a,b]=max{ F[a,k-1]*F[k+1,b]+F[k,k] }
    • root[a,b]=使F[a,b]最大的k的值 (a<=k<=b)

    边界条件

    • F[i,i]=P[i] 第i个节点的分数
    • F[i,j]=1 (i>j)

    目标结果

    • 最大加分为 F[1,N]

    前序遍历要在root状态中递归得出。从a=1,b=N开始递归,a,b子树中根为root[a,b]。输出root[a,b]并递归进入(a,root[a,b]-1)和(root[a,b]+1,b)

    传染病控制

    搜索一棵树,从根节点开始,枚举剪掉每一条边,把剩余的节点合并为一个节点,继续回溯搜索它。返回时要把合并了的节点再拆开来。继续枚举另一条边。

    这样的话,可能会超时的。所以要加上两个显而易见的优化。

    优化一:当搜索过程中发现当前的感染人数已经大于已知最小感染人数,继续搜索是无意义的,要回溯。

    优化二:如果遍历到一颗树的节点全部都是叶节点,不用枚举剪哪个,这时新感染人数一定为叶节点数-1。否则在枚举剪断的时候,无需剪叶节点。

    优化三:启发式搜索。很明显,一棵子树的节点数越多,这棵树就越“危险”,所以优先枚举剪掉这棵子树,会减少很多搜索量。

    NOIP2004

    津津的储蓄计划

    再简单不过的题了。边读边算就行了,相信学过编程的都能做这道题。

    有个要注意的地方,就是年末取得存款的时候,最好不要乘以1.2,而是先除以5再乘以6。这样可以避免由于两次隐式转换产生的误差。这个误差对于C++尤为显著。

    合并果子

    由题意可知,显然是每次合并两堆数目最小的果子,合并N-1次以后消耗体力最少。

    因为越早合并的果子堆,合并的次数就越多。我们把数目大的果子堆留到尽量靠后合并,才能保证尽量合并少,这样消耗体力才能最少。

    我们每次合并时,都要从所有的果子中找到数目最少的两堆。由于N<=10000,显然每次O(N^2)的排序是不行的。要用到最小堆或者平衡树了。

    我用的是Treap树,时间复杂度为O(N*logN)。

    注意这道题不是石子归并!

    合唱队形

    动态规划。这道题实际上是求最长谷状序列,可以转化为最长上升、下降序列问题。方法为枚举中间长的最高的人,在其左边求最长上升序列,在其右边求最长下降序列。注意这两个序列要以中间这个人为公共点。

    所以设置的两个状态分别为以第i个数为结尾的最长上升序列和以第i个数为开头的最长下降序列,这样可以保证两个序列可以连接。

    状态

    • F[i] 以第i个数为结尾的最长上升序列
    • G[i] 以第i个数为开头的最长下降序列
    • H[i] 第i个数的值

    状态转移方程

    • F[i]=max{ F[j] + 1 } (1<=j<=i-1 and H[j]<H[i])
    • G[i]=max{ G[j] + 1 } (i+1<=j<=N and H[j]<H[i])

    边界条件

    • F[i]=1 (H[j]均大于等于H[i] 1<=j<=i-1 )
    • G[i]=1 (H[j]均大于等于H[i] i+1<=j<=N )

    目标结果

    • N-最长谷状序列长度。
    • max { N-(F[k]+G[k]+1) } (1<=k<=N)

    虫食算

    这是NOIP2004的唯一一道难题,而且是很难的题。单纯暴力搜索,超时是无疑的,加上许多强剪枝也很难通过。于是我用了解方程组的方法。

    从算式中可以发现,有N位,每位都是两个未知数相加得到第三个未知数。正好是N元一次线性方程组。由于存在进位问题,枚举除最后一位以外的每位的是否进位,可以列出2^(N-1)个不同的方程组,解每个方程组即可得出解。 解方程组使用高斯消元算法,时间复杂度为O(N^3)。但枚举多达2^(N-1)个,这样还是会超时。

    深入分析发现,枚举每位是否进位,仅仅影响方程的常数项。于是可以在枚举进位之前,设每个方程的常数项为d1,d2,d3,…,dn。解方程组,把未知数x1,x2,x3,…,xn用d1,d2,d3,…,dn表示,高斯消元的时候要把常数项以多项式的方式计算。

    这是我们在还是枚举每位是否进位,算出每个方程的常数项,即d1,d2,d3,…,dn,代入x1,x2,x3,…,xn再判断即可。

    这种方式只用计算一次方程组,虽然时间复杂度不变,但算法常数小了许多,对付N=26没有问题了。

    NOIP2005

    谁拿了最多奖学金

    读入每行数据,进行多条件判断,算出每个人的奖学金,保留总和与最大值。

    很简单的题,只要细心就不会错。

    用C或C++语言读入数据十分方便,一条语句即可。但是Pascal就麻烦了。

    过河

    动态规划,需要状态压缩。

    状态

    • F[i] 跳到距离i处碰到的最少的石子数。

    状态转移方程

    • F[i]=min{ F[i-k] } + F[i] (S<=k<=T i-k>=0)

    边界条件

    • F[i]=1 i处有石子

    目标结果

    • min{ F[k] } (L+1<=k<=L+T-1)

    状态压缩

    由于L最大为10^9,直接线性递推会超时。发现石子数很少,这意味着路径上有许多很长的空白段。我们可以把长度大于ST的空白段都缩小到ST,这样最长只有10090了。

    篝火晚会

    首先把这个圈看做一个图,每个同学看做一个顶点。因为要形成环,所以每个顶点的度必须为2。如果存在度数不为2的顶点,那么整个图无法构成一个环,即“无论怎么调整都不能符合每个同学的愿望”输出-1。 如果是一个环,那么就遍历图,生成以第1个顶点为开头的序列。现在就要求出最小移动的代价。

    在理解题意所述的调整方式中,要注意实际上就是把M个在错误位置上的人移动到正确的位置上,代价为M。一次下令移动即可。

    假如生成的目标序列为1,5,3,2,4。我们现在就需要比较它和初始状态1,2,3,4,5,看有几个人离开了原来的位置。但这个序列实 际代表的是一个环,而且方向正反有两种,就需要把初始序列正反分别转N次,和得到的序列比较,看其中最少有几个位置上的人编号不相同,就得到了我们要求的 最小代价。

    上述方法有大量冗余。但可以发现转来转去不管怎么转,任意两个人之间的相对位置关系在这过程中都不会变。于是想到做差,如果差小于0则加上N。

    1 5 3 2 4

    • 1 2 3 4 5 ———— 0 3 0 3 4
    这表示序列1,5,3,2,4不转动时1,3两个人在原来的位置上,转动3个位置后5和2两个人在原来的位置上,转动4个位置后只有4一个人会在原 来的位置上。这就是说,1,5,3,2,4与1,2,3,4,5在旋转后最多有2个位置上的人编号相同,即最少有3个位置上的人编号不相同。同理要反转再 求一次。

    记录每个不同的差值的个数,取其最大值P,即不调换次数最大的。结果N-P就是调换次数最小的。

    等价表达式

    这道题很显然不是让写多项式展开的程序的。只需要代入几次,判断与题干中表达式等价的表达式即可。

    注意,只有加法、减法、乘法、乘幂四种运算,没有除法!这意味着计算表达式的时候不用考虑出现小数的问题,数据类型要用8字节整型(即Pascal中的int64,C++中的long long)。因为数据中有2004^9之类的大数,幸好还不用高精度。

    对于表达式计算,我们可以现将题目中的表达式转化为后缀表达式,代入数值,并且对后缀表达式求值。当然也可以双堆栈计算表达式。多带入几次不同的数值,以避免表达式恰好相等而并不等价的情况。

    NOIP2006

    能量项链

    动态规划,属于石子归并、合并沙堆等一类的题目。

    首先把每颗珠子用一个结构存储,.L为头标记的值,.R为尾标记的值。由于项链是一个环,把环拆成两条首尾相接的链。

    例如每颗珠子表示为

    B[1] (2,3)
    B[2] (3,5)
    B[3] (5,10)
    B[4] (10,2)
    B[5] (2,3)
    B[6] (3,5)
    B[7] (5,10)
    状态设定

    • F[i,j]表示从第i颗珠子到第j颗珠子,合并一共所得的能量的最小值。
    • B[i]结构为每颗珠子的头尾标记值。

    状态转移方程

    • F[i,j]=Max{ F[i,k] + F[k+1,j] + B[i].L B[k].R B[j].R } (i<=k<=j-1)

    边界条件

    • F[i,i]=0 (1<=i<=2*N-1)

    目标结果

    • Max{ F[k,k+N-1] } (1<=k<=N)

    金明的预算方案

    背包问题的衍生问题,动态规划。

    首先把附件物品分离出来,归为主件所有。于是每次决策成了5种

    1. 不购买
    2. 购买主件
    3. 购买主件 + 附件 1
    4. 购买主件 + 附件 2
    5. 购买主件 + 附件 1 + 附件 2
    由于题中所述每件物品都是整10元,可以加一个小小的优化,就是每个物品的价格除以10。最后结果在乘以10输出。

    状态设定

    • F[i,j] 前i个主件,花费为j元的时候,重要程度与价格乘积的总和的最大值
    • V[i] 第i个主件的价格
    • W[i] 第i个主件的重要程度

    状态转移方程

    • F[i,j] =
    • Max
    • {
    • F[ i - 1 , j ], (不购买)
    • F[ i - 1 , j - V[i] ] + V[i] * W[i], (只购买主件)
    • F[ i - 1 , j - V[i] - V[i的附件1] ] + V[i] W[i] + V[i的附件1] W[i的附件1], (购买主件+附件1)
    • F[ i - 1 , j - V[i] - V[i的附件2] ] + V[i] W[i] + V[i的附件2] W[i的附件2], (购买主件+附件2)
    • F[ i - 1 , j - V[i] - V[i的附件1] - V[i的附件2] ] + V[i] W[i] + V[i的附件1] W[i的附件1] + V[i的附件2] * W[i的附件2], (购买主件+附件1+附件2)
    • }

    边界条件

    • F[0,k]=0 (0<=k<=N)

    目标结果

    • F[M,N]

    作业调度方案

    做这道题关键在于理解题意。这道题让我想起了流水作业调度的Johnson算法,虽然与这道题无关。

    提示几点

    1. 每个工件的每个工序对应着不同的机器。
    2. 一个工件必须按照加工顺序加工。
    3. 把每个机器看成一个时间轴,每个时间对应着加工一个工件,或者为空闲状态。
    4. 题中的算法是给定的贪心策略,不需要构造,只要模拟。
    由于数据很小,把每个机器的时间轴用布尔数组表示,true为该时间有工件在加工,false为空闲。

    按照给定的顺序,一件一件得往时间轴上插入,每个工件插入的位置必须在前面的工序都完成以后的时间断插入。每次插入扫描一遍时间轴数组,找到最前面一个。

    其实题中所给的图已经一目了然了。理解题意以后,会发现这是NOIP2006最简单的题。

    2^k进制数

    较难的递推问题,需要不错的数学知识基础才能顺利的解决问题。

    2^k进制实质上就是2进制数,分为长度为k的段。

    • 每位的最大值 M = 2^k-1
    • 最大的位数 N = w/k +1
    • 最高位的最大值 H = (2^(W Mod K))-1

    题中的“另一角度解释”其实已经给了我们解题的思路。设F[i,j]为位数为i,最高位为j的满足条件的2^k进制数的个数。

    如题中解释

    • 2 位数:高位为 1 F[2,1]=6 (即 12,13,14,15,16,17)。 高位为2,F[2,2]=5 , … ,F[2,6]=1(即 67)。
    • 3 位数:高位是 1,F[3,1],第 2 位为2,有F[2,2]的5 个(即123,124,125,126,127),第 2 位为 3 ,F[2,3]4 个, … ,第 2 位为 6,F[2,6] 个(即 167)。F[3,1]=5+4+ … +1=15个。

    我们可以发现,F[i,j]总是由F[i-1,k]推出,确切来说递推方程是Sum{ F[i-1,k] } (j+1<=k<=M)。

    最终结果要分为两种情况的总和。

    1. 最高位大于等于1
    对于这种情况,总数为位数为N,最高位为i(1<=i<=H)的满足条件的2^k进制数的个数的和。即Sum{ F[N,i] }(1<=i<=H)

    1. 最高位为0
    这种情况并不是简单的F[N,0],因为r至少是个2位的2^k进制数,所以要求每位开头不为0的个数和。即Sum{ F[i,k] } (2<=i<=N-1,1<=k<=W)。根据递推方程又可知Sum{ F[i,k] } (1<=k<=W)等于Sum{ F[i+1,N] },所以这种情况的总个数为Sum{ F[k,0] } (3<=j<=N)。

    由于状态很多,使用滚动数组可以大幅度节约空间。计算时要用要用高精度。

    状态设定

    • 每位的最大值 M = 2^k-1
    • 最大的位数 N = w/k +1
    • 最高位的最大值 H = (2^(W Mod K))-1
    • F[i,j]为 位数为i,最高位为j的满足条件的2^k进制数的个数

    递推方程

    • F[i,j]=Sum{ F[i-1,k] } (j+1<=k<=M)

    边界条件

    • F[1,k]=1 (0<=k<=M)

    目标结果

    • Ans = Sum{ F[N,i] } + Sum{ F[j,0] } (1<=i<=H 3<=j<=N)

    NOIP2007

    统计数字

    基本上可以说是送分题了吧。解决这道题的方法太多了,基本思想就是排序。快排,堆排,只要O(nlogn)都可以,没有可以卡快排的数据。也可以挂链哈希。当然平衡树也行。我写了Treap。

    字符串的展开

    这是个简单的题,但不是完全的送分题,要胆大心细。多读几遍题,掌握每一个细节。

    题中陷阱很多,例如字符串长度可能很长,最好一边读一遍输出,对于Pascal尤其不要用string存起来。注意减号的问题,注意有可能有些减号不是起上述作用的,例如字符串开头就是一个减号,或者好几个减号在一起。

    矩阵取数游戏

    动态规划。由于每行是互不影响的,可以把每行孤立开看,对每行分别进行一次动态规划计算。结果可能很大,需要高精度计算。为避免计算高精度乘法,可以在初始化时把每个数的2^k递推算出。

    状态设定

    • F[i,j] 为当前行取前i个数和后j个数的最大得分。
    • V[i,j] 为当前行第i个数乘以2^j的值。

    状态转移方程

    • F[i,j]=max{ F[i-1,j] + V[i,p] , F[i,j-1] + V[M-j+1,p] } p=i+j(表示当前是第几次取数)
    • V[i,j]=V[i,j-1]+V[i,j-1]

    边界条件

    • V[i,1]=当前行第i个数的值
    • F[0,0]=0

    每行结果

    • Max{ F[i,M-i] } (0<=i<=M)

    最终结果

    • 每行结果的总和

    高精度计算时要缩位优化,否则是很容易超时的。任何可以常数优化的地方都不要放过,因为数据是比较强的。

    树网的核

    图论题,其实并不难,但可能理解起来有障碍。

    首先,一个图可能有多个直径,但只用研究其中任意一个即可。所以要先找一条直径。

    根据直径的定义,可以这样找直径。

    1. 在图中任意找一个顶点A。
    2. 以A为源点,搜索距离A最远的点B。O(N)
    3. 以B为源点,搜索距离B最远的点C。O(N)
    则BC就是一条直径。找直径的时间复杂度为O(N)。

    下面就是在直径上枚举核。不难发现,核的长度越大,期望的最小偏心距就越小。方法如下

    1. 在直径上枚举顶点A。O(N)
    2. 找到直径上距离A不超过S的最远顶点B。O(1)
    3. 求AB的偏心距。O(N)
    最后保留最小偏心距即可。时间复杂度为O(N^2)。

    按照定义找核的偏心距,即枚举核上每个顶点A距离最远点B,且B不在核上的距离|AB|。搜索即可。要把核上的顶点从图中暂时删掉,避免找到的B在核上。时间复杂度为O(N)。

    最终时间复杂度为O(N^2)。

    相关日志