User Tools

Site Tools


exam3

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki