冬令營(yíng)測(cè)試解題報(bào)告xmas

1、Xmas 解題問(wèn)題分析本題是一道交互試題，解決此類問(wèn)題的通用解法是通過(guò)獲取的信息不斷篩選，直到剩下唯一的此題亦是如此。為止。先來(lái)看看最基礎(chǔ)的想法。設(shè)銀針圓盤對(duì)應(yīng)的序列為(a0,a1,an-1)，令 T(i)=(ai,ai+1,ai+2,an-1,a0,a1,ai-1)。由于題目中說(shuō)明“一定存在一個(gè)位置可以將兩個(gè)圓盤完美的拼合在一起”，所以小孔圓盤必然是某一個(gè) T(r*)， Ro(r*)、Drop 即可。的任務(wù)實(shí)際上就是要求出這個(gè) r*；然后設(shè)定集合 S ， 表示那些可能成為結(jié)果 r* 的數(shù)的集合。一開(kāi)始顯然S=0,1,2,n-1，即每個(gè)位置都有可能成為結(jié)果。然后不斷的篩。從S 中取出一個(gè)元素x

2、，執(zhí)行如下操作：Roe(x) v DropRoe(n-x)（將x 旋轉(zhuǎn)到開(kāi)始位置）（計(jì)算距離）（復(fù)原）可以得到的信息是：T(x)與T(r*)之間的距離是v。然后依次判斷每一個(gè) yS，如果T(x)與T(y)之間的距離不等于v，則將y 篩掉。如此而行。一旦發(fā)現(xiàn)|S|=1，則 S 中唯一的數(shù)即是r*。不難發(fā)現(xiàn)上述算法時(shí)間復(fù)雜度極高。求一次T(x)與T(y)的距離就需要 O(n)，如果將S 中的元素一一判斷，僅第一次篩選復(fù)雜度就可高達(dá) O(n2)。在n100000 的可怕范圍內(nèi)，這樣的時(shí)間復(fù)雜度是絕對(duì)們必須另辟蹊徑。受的。因此我算法改進(jìn)一般來(lái)說(shuō)做交互式題目考慮的都是如何充分的利用信息，以求獲得更優(yōu)的結(jié)

3、果。但任何問(wèn)題都要抓住主要復(fù)雜度。此題的主要并不是次數(shù)，而是時(shí)間因此可以考慮少利用一些信息，降低篩選的時(shí)間復(fù)雜度。先來(lái)看一個(gè)例子：n=10銀針圓盤為 10 9 8 7 6 1 2 3 4 5一開(kāi)始不進(jìn)行任何旋轉(zhuǎn)，直接執(zhí)行v Drop，得到 v=5。于是可知T(0)與T(r*)之間的距離為 5。將T(0)與T(i)的距離列出來(lá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。然后隨便問(wèn)一次就能得到結(jié)果。之前分析過(guò)這種做法的復(fù)雜度為 O(n2)，當(dāng) n 較大的時(shí)候效率太低。換一種角度來(lái)分析。T(0)和T(r*)的距離為 5，這個(gè) 5 是怎么來(lái)的？只有可能是 10-5, 9-4, 8-3, 7-2, 6-1。也就是把 10 和 5 對(duì)齊、把 9 和 4 對(duì)齊、把 8 和 3 對(duì)齊、把 7 和 2 對(duì)齊、或者把 6 和 1 對(duì)齊。把 10 和 5 對(duì)齊需要把銀針圓盤把 9 和 4 對(duì)齊需要把銀針圓盤把 8 和 3 對(duì)齊需要把銀

5、針圓盤把 7 和 2 對(duì)齊需要把銀針圓盤把 6 和 1 對(duì)齊需要把銀針圓盤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。歸納起來(lái)就是從S 中取一個(gè)x，執(zhí)行：Roe(x) vDrop Roe(n-x)把T(x)旋轉(zhuǎn)到開(kāi)始位置試探還原如下數(shù)對(duì)：然后依次(n, n-v), (n-1, n-v-1),(v+1,1)設(shè)將他們對(duì)齊需要把銀針圓盤往 T=1,3,5,7,9）將 T 中的元素都加上 x就被縮小了。如是反復(fù)，直到|S|=1。的集合為 T。（比如上例動(dòng)的位移后

6、集合 T。然后 SST。新的 S可進(jìn)行一個(gè)預(yù)處理，將每個(gè)數(shù)在數(shù)列中的位置記下，則每次篩的時(shí)候考察上述數(shù)對(duì)僅需 O(n)的復(fù)雜度。容易發(fā)現(xiàn)，對(duì)于上面的例子，經(jīng)過(guò)一次提問(wèn)后，實(shí)際上只有1,9是可行集合。然而采取的后法卻保留了1,3,5,7,9，其中絕大部分不可能是結(jié)果，沒(méi)有做到信息的充分利用。但是必須注意的事實(shí)是：時(shí)間才是本題的主要，大大提高了時(shí)間復(fù)雜度（從 O(n2)到 O(n)），這通過(guò)舍棄一部分無(wú)用的信息就達(dá)到了預(yù)期的目的。詢問(wèn)次數(shù)分析為了提高時(shí)間效率，一個(gè)估計(jì)。只利用了一部分信息，因此還有必要對(duì)詢問(wèn)次數(shù)做關(guān)鍵是“從S 中取一個(gè)x”這一步，到底取哪個(gè)x？一種想法是取S 中最小的x。但是形如下面的數(shù)據(jù) n, n-1, n-2, n-3, , n/2+1, 1, 2, 3, , n/2就需要log2n 次詢問(wèn)！到底如何取，技巧？我至今還沒(méi)有研究出