exam3
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
exam3 [2012/04/14 09:24] – xcyan | exam3 [2012/04/14 12:56] (current) – [2108] xcyan | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ## 2106 | + | ==== 2106 ==== |
这道题目有很多种做法,下面我说一下我的做法: | 这道题目有很多种做法,下面我说一下我的做法: | ||
+ | |||
这道题目的本质就是求一个会聚点,使得两个分身到达本体的时间和最小。 | 这道题目的本质就是求一个会聚点,使得两个分身到达本体的时间和最小。 | ||
+ | |||
由于本体不会移动,所以只需要枚举三次即可。 | 由于本体不会移动,所以只需要枚举三次即可。 | ||
+ | |||
剩下的问题就是如何求分身到达本体的时间了,这个是一个单源最短路模型。 | 剩下的问题就是如何求分身到达本体的时间了,这个是一个单源最短路模型。 | ||
+ | |||
其实可以直接用BFS暴力过掉,暴力过掉当然还需要一些技巧,我用的就是SPFA。 | 其实可以直接用BFS暴力过掉,暴力过掉当然还需要一些技巧,我用的就是SPFA。 | ||
- | 至于什么是SPFA,请看: | ||
- | [[http:// | + | 至于什么是SPFA,请看:[[http:// |
当然,这道题的主人佘召臣有一个巧妙的构图方法,大家可以找他问一下。 | 当然,这道题的主人佘召臣有一个巧妙的构图方法,大家可以找他问一下。 | ||
- | ## 2107 | + | ==== 2107 ==== |
这是作业题中的翻版,首先说一下这道题的数据容易引起误解。 | 这是作业题中的翻版,首先说一下这道题的数据容易引起误解。 | ||
- | 比如A和B是Group1和Group2的强者,每次询问后不是输出max(A/ | + | |
- | 而是输出Group1和Group2并成一堆后,最强者。 | + | 比如A和B是Group1和Group2的强者,每次询问后不是输出max(A/ |
然后就是怎么做这道题目了,熟读了题目之后发现这道题目涉及合并操作,以及找最大值操作。 | 然后就是怎么做这道题目了,熟读了题目之后发现这道题目涉及合并操作,以及找最大值操作。 | ||
+ | |||
对于合并操作,我们能想到并查集,就是每次合并,将一堆人的首领和另一堆人的首领合并。 | 对于合并操作,我们能想到并查集,就是每次合并,将一堆人的首领和另一堆人的首领合并。 | ||
+ | |||
下面就是找最大值的问题了,考场上有不少同学没思考清楚,直接在并查集的基础上做了一些不科学的改动,拿不到满分。 | 下面就是找最大值的问题了,考场上有不少同学没思考清楚,直接在并查集的基础上做了一些不科学的改动,拿不到满分。 | ||
+ | |||
其实想一想,找最大值用堆维护不就行了嘛。 | 其实想一想,找最大值用堆维护不就行了嘛。 | ||
+ | |||
总结一下思路,这道题可以用并查集加上堆来解决,具体地说就是每一个集合里面建一个大根堆。 | 总结一下思路,这道题可以用并查集加上堆来解决,具体地说就是每一个集合里面建一个大根堆。 | ||
+ | |||
初始时有N个堆,每个堆只有一个元素。 | 初始时有N个堆,每个堆只有一个元素。 | ||
+ | |||
每次合并,就将一堆删去,并入另外一堆。 | 每次合并,就将一堆删去,并入另外一堆。 | ||
+ | |||
这样的确很暴力,不过至少可以通过7个点,已经很不错了。 | 这样的确很暴力,不过至少可以通过7个点,已经很不错了。 | ||
+ | |||
当然,由于作业里面出现了左堆,那么可以直接将堆换成左堆,大大减少了合并时间,数据就全过了。 | 当然,由于作业里面出现了左堆,那么可以直接将堆换成左堆,大大减少了合并时间,数据就全过了。 | ||
- | ## 2108 | + | ==== 2108 ==== |
这道题目就是N路合并问题,如果不知道什么是N路合并,可以考虑N=2的情形。 | 这道题目就是N路合并问题,如果不知道什么是N路合并,可以考虑N=2的情形。 | ||
+ | |||
两个有序队列做合并,数据结构课里面应该讲过怎么做吧。现在我们将N扩大,然后就是N个有序队列做合并。 | 两个有序队列做合并,数据结构课里面应该讲过怎么做吧。现在我们将N扩大,然后就是N个有序队列做合并。 | ||
+ | " | ||
+ | |||
+ | - N路归并。先将A, | ||
+ | | ||
+ | - 二分答案套二分查找。我们发现,我们可以把第N大的数找出来。事实上,如果我们知道了一个数T,就可以算出比他小的有多少个,这个通过排序A, | ||
+ | 上述两种方法都可以通过此题。 |
exam3.1334395490.txt.gz · Last modified: 2012/04/14 09:24 by xcyan