Table of Contents

2106

这道题目有很多种做法,下面我说一下我的做法:

这道题目的本质就是求一个会聚点,使得两个分身到达本体的时间和最小。

由于本体不会移动,所以只需要枚举三次即可。

剩下的问题就是如何求分身到达本体的时间了,这个是一个单源最短路模型。

其实可以直接用BFS暴力过掉,暴力过掉当然还需要一些技巧,我用的就是SPFA。

至于什么是SPFA,请看:SPFA reference

当然,这道题的主人佘召臣有一个巧妙的构图方法,大家可以找他问一下。

2107

这是作业题中的翻版,首先说一下这道题的数据容易引起误解。

比如A和B是Group1和Group2的强者,每次询问后不是输出max(A/2,B/2),而是输出Group1和Group2并成一堆后,最强者。

然后就是怎么做这道题目了,熟读了题目之后发现这道题目涉及合并操作,以及找最大值操作。

对于合并操作,我们能想到并查集,就是每次合并,将一堆人的首领和另一堆人的首领合并。

下面就是找最大值的问题了,考场上有不少同学没思考清楚,直接在并查集的基础上做了一些不科学的改动,拿不到满分。

其实想一想,找最大值用堆维护不就行了嘛。

总结一下思路,这道题可以用并查集加上堆来解决,具体地说就是每一个集合里面建一个大根堆。

初始时有N个堆,每个堆只有一个元素。

每次合并,就将一堆删去,并入另外一堆。

这样的确很暴力,不过至少可以通过7个点,已经很不错了。

当然,由于作业里面出现了左堆,那么可以直接将堆换成左堆,大大减少了合并时间,数据就全过了。

2108

这道题目就是N路合并问题,如果不知道什么是N路合并,可以考虑N=2的情形。

两个有序队列做合并,数据结构课里面应该讲过怎么做吧。现在我们将N扩大,然后就是N个有序队列做合并。

“配对I” 这个题有2种做法 by 蒋舜宁:

  1. N路归并。先将A,B排序,考虑A[i]+B[j], j=1..N这个数列,对于每一个i都有一个N个数的有序数列,我们选取当前剩下的序列头中最小的那个,自然就是当前最小的一对。然后这就成了一个N路归并的问题。如果没法一下子想清楚,就画个图试试看吧,N行,每行N个数,每次比较这N行的头,然后把选了的那个头划掉,划N次。
  1. 二分答案套二分查找。我们发现,我们可以把第N大的数找出来。事实上,如果我们知道了一个数T,就可以算出比他小的有多少个,这个通过排序A,B,枚举每个i,然后二分得到B[j]⇐T-A[i]的个数,再加起来,就可以搞出来,这一步的复杂度是kNlogN,k是个常数(<32)。最后,我们可以用算出来的答案ret,还原最后一次二分:再枚举i=1到N,将所有A[i]+B[j]⇐ret的扔进数组,排序输出即可。

上述两种方法都可以通过此题。

exam3.txt · Last modified: 2012/04/14 20:56 by xcyan
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki