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 次詢問！到底如何取，技巧？我至今還沒有研究出