冬令营测试解题报告xmas

1、Xmas 解题问题分析本题是一道交互试题，解决此类问题的通用解法是通过获取的信息不断筛选，直到剩下唯一的此题亦是如此。为止。先来看看最基础的想法。设银针圆盘对应的序列为(a0,a1,an-1)，令 T(i)=(ai,ai+1,ai+2,an-1,a0,a1,ai-1)。由于题目中说明“一定存在一个位置可以将两个圆盘完美的拼合在一起”，所以小孔圆盘必然是某一个 T(r*)， Ro(r*)、Drop 即可。的任务实际上就是要求出这个 r*；然后设定集合 S ， 表示那些可能成为结果 r* 的数的集合。一开始显然S=0,1,2,n-1，即每个位置都有可能成为结果。然后不断的筛。从S 中取出一个元素x

2、，执行如下操作：Roe(x) v DropRoe(n-x)（将x 旋转到开始位置）（计算距离）（复原）可以得到的信息是：T(x)与T(r*)之间的距离是v。然后依次判断每一个 yS，如果T(x)与T(y)之间的距离不等于v，则将y 筛掉。如此而行。一旦发现|S|=1，则 S 中唯一的数即是r*。不难发现上述算法时间复杂度极高。求一次T(x)与T(y)的距离就需要 O(n)，如果将S 中的元素一一判断，仅第一次筛选复杂度就可高达 O(n2)。在n100000 的可怕范围内，这样的时间复杂度是绝对们必须另辟蹊径。受的。因此我算法改进一般来说做交互式题目考虑的都是如何充分的利用信息，以求获得更优的结

3、果。但任何问题都要抓住主要复杂度。此题的主要并不是次数，而是时间因此可以考虑少利用一些信息，降低筛选的时间复杂度。先来看一个例子：n=10银针圆盘为 10 9 8 7 6 1 2 3 4 5一开始不进行任何旋转，直接执行v Drop，得到 v=5。于是可知T(0)与T(r*)之间的距离为 5。将T(0)与T(i)的距离列出来：T(0)与T(0)的距离为 0T(0)与T(1)的距离为 5T(0)与T(2)的距离为 6T(0)与T(3)的距离为 7T(0)与T(4)的距离为 8T(0)与T(5)的距离为 9T(0)与T(6)的距离为 8T(0)与T(7)的距离为 7T(0)与T(8)的距离为 6T

4、(0)与T(9)的距离为 5故而小孔圆盘只有可能是T(1)或者T(9)。可行的集合 S=0,1,2,3,4,5,6,7,8,9，变成了S=1,9。然后随便问一次就能得到结果。之前分析过这种做法的复杂度为 O(n2)，当 n 较大的时候效率太低。换一种角度来分析。T(0)和T(r*)的距离为 5，这个 5 是怎么来的？只有可能是 10-5, 9-4, 8-3, 7-2, 6-1。也就是把 10 和 5 对齐、把 9 和 4 对齐、把 8 和 3 对齐、把 7 和 2 对齐、或者把 6 和 1 对齐。把 10 和 5 对齐需要把银针圆盘把 9 和 4 对齐需要把银针圆盘把 8 和 3 对齐需要把银

5、针圆盘把 7 和 2 对齐需要把银针圆盘把 6 和 1 对齐需要把银针圆盘9。7。5。3。1。所以 T(0) 、T(2) 、T(4) 、T(6) 、T(8) 不可能是 T(r*) ，可以筛掉。S 从0,1,2,3,4,5,6,7,8,9变成1,3,5,7,9。归纳起来就是从S 中取一个x，执行：Roe(x) vDrop Roe(n-x)把T(x)旋转到开始位置试探还原如下数对：然后依次(n, n-v), (n-1, n-v-1),(v+1,1)设将他们对齐需要把银针圆盘往 T=1,3,5,7,9）将 T 中的元素都加上 x就被缩小了。如是反复，直到|S|=1。的集合为 T。（比如上例动的位移后

6、集合 T。然后 SST。新的 S可进行一个预处理，将每个数在数列中的位置记下，则每次筛的时候考察上述数对仅需 O(n)的复杂度。容易发现，对于上面的例子，经过一次提问后，实际上只有1,9是可行集合。然而采取的后法却保留了1,3,5,7,9，其中绝大部分不可能是结果，没有做到信息的充分利用。但是必须注意的事实是：时间才是本题的主要，大大提高了时间复杂度（从 O(n2)到 O(n)），这通过舍弃一部分无用的信息就达到了预期的目的。询问次数分析为了提高时间效率，一个估计。只利用了一部分信息，因此还有必要对询问次数做关键是“从S 中取一个x”这一步，到底取哪个x？一种想法是取S 中最小的x。但是形如下面的数据 n, n-1, n-2, n-3, , n/2+1, 1, 2, 3, , n/2就需要log2n 次询问！到底如何取，技巧？我至今还没有研究出