NOIP2012 开车旅行

好难呀。。。

花了一早上来肝这道题,我认为真心不好做。

首先思路是倍增:

令F[I][J]表示以I出发2^J个点所到达的点

令A[I][J]表示以I出发2^J个点a所行驶的距离

令B[I][J]表示以I出发2^J个点b所行驶的距离

首先,你需要找到n个点距离他最近的点与次近的点。

显而易见,我们不能使用n^2的暴力来枚举,一个想法是二叉搜索树来搞搞。

但是明显太复杂,考虑,因为只需寻找次近与最近,所以可以先排序,用链表连起来。

然后链表的点也要对应回来,因为我们必须由这个点得到i所对应链表的位置。

然后因为是只有从后面往前面走,那么我们就顺次寻找,找完一个删除一个。

值得注意的是,对于一个点 x ,他的最近的点肯定只可能是相邻的任意一个点。

然后我们暂时删除最近的点,此时次近的点依旧是相邻的点。

另外,因为可能越界,即左右两边没有城市了,那么我们还需要进行两次判断,这里具体见代码(就是这里坑了我)。

找完了次近与最近,这时候就可以倍增处理了,倍增处理完了以后,就是一般的倍增问题了。

从高位往低位枚举,然后可以的话就跳。

最后还必须看看a能不能再单独跳一次。

输出答案。

c++代码如下:

 

回复

  1. 回复 sdfsdfs

    sdfsdfsd :sad: f javascript:grin(':razz:');:oops: :wink: :wink: :oops: :?: :?: :?: :?: :???: :twisted: :cool: :smile: :???: :???: :mad: 水电费水电费就是对方

  2. 回复 sdfsdfs

    。。。の䳗鬬sfsdfsdfsfd

4 + 9 =