Differences

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

--- exam3 [2012/04/09 10:23] – created xcyan
+++ exam3 [2012/04/14 12:56] (current) – [2108] xcyan
@@ Line 1: / Line 1: @@
+==== 2106 ====
+这道题目有很多种做法，下面我说一下我的做法：
-# 二哥的逃离
+这道题目的本质就是求一个会聚点，使得两个分身到达本体的时间和最小。
+由于本体不会移动，所以只需要枚举三次即可。
-## Description
+剩下的问题就是如何求分身到达本体的时间了，这个是一个单源最短路模型。
-二哥突然学会了Blink（闪烁）魔法，但他也因此被伊利丹追杀。在慌乱之间，二哥冲入了迷宫的入口，被传送进入了远古之迷宫。
+其实可以直接用BFS暴力过掉，暴力过掉当然还需要一些技巧，我用的就是SPFA。
-“你将一分为三，两个分身，一个本体。分身不能走动只能使用魔法，而本体则会被束缚而完全无法动弹，他们会被传送至不同的地方。但是作为补偿，你可以在开始行动之前，决定自己的本体是三者中的哪一个。当三者重新汇聚，束缚将被打破，你也自然脱离了迷宫。”二哥在恍惚之间听到了这样一番话。
+至于什么是SPFA，请看：[[http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm|SPFA reference]]
-迷宫是一个矩形，被划分成了\\( N \\)行\\( M \\)列共\\(N \times M\\)个小格。迷宫左上角小格的坐标定义为\\((1,1)\\)，右上角小格的坐标定义为\\((1,M)\\)，右下角小格的坐标定义为\\((N,M)\\)。两小格\\((a,b)\\)，\\((c,d)\\)之间的距离定义为\\(|a-c|+|b-d|\\)（即曼哈顿距离）。
+当然，这道题的主人佘召臣有一个巧妙的构图方法，大家可以找他问一下。
-二哥唯一能做的事就是使用闪烁魔法，来使得自己的两个分身尽快与本体会合。不过正如同之前听到的那句话，只有分身能够使用闪烁魔法进行移动。
+==== 2107 ====
+这是作业题中的翻版，首先说一下这道题的数据容易引起误解。
-由于二哥的魔法水平有限，他每次使用魔法只能让分身移动到一定距离以内的任意一个小格并且在进行移动之前需要一段时间进行准备（吟唱魔法）。而在这个神秘的迷宫里，二哥发现他的分身在每个小格所能移动的距离和吟唱时间是不同的。
+比如A和B是Group1和Group2的强者，每次询问后不是输出max(A/2,B/2)，而是输出Group1和Group2并成一堆后，最强者。
-在 \\( \(i,j\) \\)小格上能移动的最大距离为: \\( A_{i,j} \\)
+然后就是怎么做这道题目了，熟读了题目之后发现这道题目涉及合并操作，以及找最大值操作。
-需要的准备时间为: \\( B_{i,j} \\)
+对于合并操作，我们能想到并查集，就是每次合并，将一堆人的首领和另一堆人的首领合并。
-更加悲剧的是，二哥每次只能让一个分身进行吟唱魔法并移动，移动完毕之后才能进行下一次吟唱。
+下面就是找最大值的问题了，考场上有不少同学没思考清楚，直接在并查集的基础上做了一些不科学的改动，拿不到满分。
-现在，二哥想知道，自己至少要花多少时间才能逃脱出迷宫。
+其实想一想，找最大值用堆维护不就行了嘛。
-注意：迷宫的外部是虚无，二哥不会通过闪烁移动到迷宫之外。
+总结一下思路，这道题可以用并查集加上堆来解决，具体地说就是每一个集合里面建一个大根堆。
-## Input Format
+初始时有N个堆，每个堆只有一个元素。
-第一行两个整数\\( N,M \\)
+每次合并，就将一堆删去，并入另外一堆。
-接下来两个\\( N \times M \\) 的自然数矩阵:
+这样的确很暴力，不过至少可以通过7个点，已经很不错了。
-\\( A_{i,j} \\) ,
-\\( B_{i,j} \\)
-接下来六个数\\(Xx,Xy,Yx,Yy,Zx,Zy\\)，表示本体和两个分身的坐标。
+当然，由于作业里面出现了左堆，那么可以直接将堆换成左堆，大大减少了合并时间，数据就全过了。
+==== 2108 ====
+这道题目就是N路合并问题，如果不知道什么是N路合并，可以考虑N=2的情形。
-## Output Format
+两个有序队列做合并，数据结构课里面应该讲过怎么做吧。现在我们将N扩大，然后就是N个有序队列做合并。
-输出两行第一行一个字符\\( X,Y\\)或\\( Z \\)，表示以哪一个为本体。
+"配对I" 这个题有2种做法 by 蒋舜宁：
-第二行一个整数，表示最短时间。
-若无法逃出迷宫，则只输出一行"NO"（不带引号）。
-## Sample Input
-4
-0 0 0
- 2 2 0
-2 2 1
-0 0 0
-5 5 5
-5 5 5
-5 5 5
-5 5 5
-1 3 4 2 2
-## Sample Output
-	Z
-## About Test Data
-对于20%的数据：\\( 1 \leq n,m \leq 10 \\)。
-对于50%的数据：\\( 1 \leq n,m \leq 100 \\) \\( 1 \leq B_{i,j} \leq 30 \\)。
-对于100%的数据：\\( 1 \leq n,m \leq 100 \\)
-\\( 1 \leq B_{i,j} \leq 100 \\)
-\\( 1 \leq A_{i,j} \leq 10^9 \\)
+  - 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的扔进数组，排序输出即可。
+上述两种方法都可以通过此题。