國家集訓隊作業(yè)04.藩problems

1、青少年信息學中國國家隊訓練 2010-2011藩競賽時間：待定提交源程序須加后綴注意：最終測試時，所有編譯命令均不打開任何優(yōu)化開關(guān)。對于Pascal 語言paspaspas對于C語言ccc對于C+語言cppcppcpp題目名稱飛飛俠跳跳棋悄悄話目錄flyhopmsg可執(zhí)行文件名flyhopmsg輸入文件名標準輸入標準輸入標準輸入輸出文件名標準輸出標準輸出標準輸出每個測試點時限511測試點數(shù)目202020每個測試點分值555是否有部分分無無無題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型飛飛俠【問題描述】飛飛國是一個中的國度，國家的居民叫做飛飛俠。飛飛國是一個 NM的矩形方陣，每個格子代表一個街區(qū)。然而飛飛國是沒有

2、交通工具的。飛飛俠完全靠地面的彈射裝置來移動。每個街區(qū)都裝有彈射裝置。使用彈射裝置是需要支付一定費用的。而且每個彈射裝置都有自己的彈射能力。設(shè)第i 行第 j 列的彈射裝置有 Aij 的費用和Bij 的彈射能力。并規(guī)定有相鄰邊的格子間距離是 1。那么，任何飛飛俠都只需要在(i,j)支付 Aij 的費用就可以任意選擇彈到距離不超過Bij 的位置了。如下圖（從紅色街區(qū)交費以后可以跳到周圍的任意藍色街區(qū)。）現(xiàn)在的問題很簡單。有三個飛飛俠，分別叫做 X，Y，Z?，F(xiàn)在它們決定聚在一起玩，于是想往其中一人的位置集合。告訴你 3 個飛飛俠的坐標，求往哪里集合大家需要花的費用總和最低?！据斎敫袷健枯斎氲牡谝恍邪?/p>

3、含兩個整數(shù)N 和 M，分別表示行數(shù)和列數(shù)。接下來是 2 個 NM 的自然數(shù)矩陣，為 Aij 和 Bij最后一行六個數(shù)，分別代表X，Y，Z 所在地的行號和列號?！据敵龈袷健康谝恍休敵鲆粋€字符X、Y 或者Z。表示最優(yōu)集合地點。第二行輸出一個整數(shù)，表示最小費用。如果無法集合，只輸出一行 NO【樣例輸入】40104022022001055552055551055553055554 2 2【樣例輸出】Z 15【范圍】20%40%100%N, MN, M 10; 100;Bij 20Bij 200 Bij 109;0 Aij 10001 N, M 150;【解題】飛飛俠這道題是一個明顯的最短路模型題。主要

4、選手對圖論的理解和對經(jīng)典算法的優(yōu)化能力?！舅惴?1】直接建圖。以矩陣的每個格子為點，如果從u 可以彈到 v 那么建一條從 u 到v，長度為u 點彈射費用的邊。然后從X，Y，Z 三個點分別開始做單源最短路。此時圖的尺寸是點數(shù) O(NM)，邊數(shù) O(N2M2)。具體實現(xiàn)：Bellman-Ford 算法，時間 O(N3M3) 空間 O(N2M2)，期望得分 20 Dijkstra 算法，時間 O(N2M2) 空間 O(N2M2)，期望得分 20 SPFA 算法，時間 O(KN2M2)空間 O(N2M2)，期望得分 20以上 3 個算法的瓶頸在于空間。事實上，對于 40%的數(shù)據(jù)，發(fā)現(xiàn)圖并不是很稠密，可

5、以用鄰接表等數(shù)據(jù)結(jié)構(gòu)來連通信息。這樣 Dijkstra 算法和SPFA算法可以得到 40 的分數(shù)。使用優(yōu)先隊列（堆）進行優(yōu)化以后可以多得到少許的分數(shù)。注意，在這個圖上點數(shù)和邊數(shù)同級，所以當模型是邊數(shù)很多的稠密圖時，堆優(yōu)化的效果就會顯得不明顯。（設(shè)V 是點數(shù)，E 是邊數(shù)。堆可以把 O(V2)的最短路算法優(yōu)化成 O(V+E)logV)，當E 越小時，堆的效果越突出。）【優(yōu)化 1】思考 Dijkstra 算法的特點。事實上在這題中只要求從一個點到另外 2 個點的最短路，也就是說，一旦另外兩個點的最短距離已經(jīng)算出，就可以終止Dijkstra 算法避免浪費時間。原因是，Dijkstra 算法運行時，每次

6、確定的點都一定是最短的。加上這個優(yōu)化以后會少許提高分數(shù)。注意SPFA 算法無法進行此項優(yōu)化。因為 SPFA 和Bellman-Ford 同屬迭代型的最短路算法，算法結(jié)束前無法保證任意一點的是否不會改變?！緝?yōu)化 2】不使用鄰接表和其他任何數(shù)據(jù)結(jié)構(gòu)來建圖，直接根據(jù)圖的特點來做最短路。這是一個很節(jié)約空間的方法，事實證明內(nèi)存空間時間也會有很大改善。進行此項優(yōu)化可以少許提高分數(shù)。次數(shù)減少以后，算法的【算法 2】發(fā)現(xiàn)從最短路算法上的優(yōu)化來考慮沒法得出效率更高的解。所以究圖的特點。在此，出題者發(fā)現(xiàn)一種圖的改建方法，可以減少邊數(shù)：研取圖中最遠可能的彈射距離S。（SN+M-2）引入“云端”這個新的概念。建立一個

7、包含 N*M*(S+1)個點的圖 G1.N1.M0.S其中 Gxy0代表地面，也就是飛飛國的街區(qū)。 Gxyh (h0) 代表一個云端節(jié)點。當飛飛俠在云端節(jié)點上時，他必須選擇往低一層的相鄰云端降落。也就是說，Gxyh有 5 條出邊：Gxyh到 Gxyh-1Gxyh到 Gx-1yh-1Gxyh到 Gx+1yh-1Gxyh到 Gxy-1h-1Gxyh到 Gxy+1h-1它們的邊權(quán)(長度)都是 0.也就是說，在高度為 1 的云端可以落到地面的 5 個相鄰點。在高度為h 的云端，最終一定會落到地面距離不超過h 的某個點。彈射裝置的作用，實際上就是把飛飛俠從地面彈到同經(jīng)緯的一定高度的云端上。如果 Axy

8、= v（彈射能力）那么建邊 Gxy0到 Gxyv，邊權(quán)(長度)為 Bxy（彈射費用）。這樣一來，每個云端點只有 5 條出邊每個地面點只有 1 條出邊也就是說，這是一個相當稀疏的圖，點數(shù)和邊數(shù)同級。建立了一個點數(shù)和邊數(shù)都是 O(N*M*S)的圖。同樣是求 3 個地面點互相的最短路。發(fā)現(xiàn)新圖比原來的圖顯得更自然注意S 與 N 和 M 同級，所以，雖然點數(shù)增加了，但這個圖的邊數(shù)是算法 1 中圖的約 1/N。于是，堆優(yōu)化就可以很有效的優(yōu)化算法了。堆+Dijkstra 算法加上前面說到的優(yōu)化 1 和優(yōu)化 2，就可以獲得本題的滿分了。時間復雜度：O(N3logN)?？臻g復雜度 O(N3)。 （M 用同級的

9、N 表示）期望得分 100注：時間限制為標程最慢測試點用時的 2 倍。【總結(jié)】本題為出題者，出現(xiàn)過的類似算法，純屬思維上的巧合。感謝感謝中學同學提供了一個優(yōu)秀的 AC 程序。中學各位同學在數(shù)據(jù)設(shè)計上的幫助。跳跳棋【問題描述】跳跳棋是在一條數(shù)軸上進行的。棋子只能擺在整點上。每個點不能擺超過一個棋子。用跳跳棋來做一個簡單的：棋盤上有 3 顆棋子，分別在a，b，c 這要通過最少的跳動把他們的位置移動成 x，y，z。（棋子是沒有三個位置。區(qū)別的）跳動的規(guī)則很簡單，任意選一顆棋子，對一顆中軸棋子跳動。跳動后兩顆棋子距離不變。一次只允許跳過 1 顆棋子。寫一個程序，首先判斷是否可以完成任務(wù)。如果可以，輸出

10、最少需要的跳動次數(shù)。【輸入格式】第一行包含三個整數(shù)，表示當前棋子的位置a b c。（互不相同）第二行包含三個整數(shù)，表示目標位置x y z。（互不相同）【輸出格式】如果無解，輸出一行 NO。如果可以到達，第一行輸出 YES，第二行輸出最少步數(shù)?！緲永斎搿? 2 30 3 5【樣例輸出】YES 2【范圍】20% 輸入整數(shù)的絕對值均不超過 1040% 輸入整數(shù)的絕對值均不超過 10000100% 絕對值不超過 109【解題】跳跳棋這題是一個偏向想象力和數(shù)學的題目。選手的數(shù)學建模能力以及對樹結(jié)構(gòu)的操作的熟練程度。首先，注意題目沒有標明輸入的有序性。把 3 個數(shù)排好序。設(shè)三個數(shù)從小到大是 a, b,

11、c【算法 1】BFS（寬度優(yōu)先搜索）或 DFSID（迭代加深搜索）期望得分 10。注意到重復狀態(tài)很多加入hash 判重，期望得分 20。如果大范圍輸出無解，可以少許提高分數(shù)。顯然搜索無論怎么優(yōu)化都無法通過全部數(shù)據(jù)?！窘！吭O(shè)：s1=b-as2=c-b那么b 可以跳動到 a 左邊，或者c 右邊。如果s1s2，那么 c 可以跳到ab 中間也就是說，如果 s1s2，那么一個局面有 3 種跳法。如果s1=s2，那么只有 2 種跳法。如果用圖來表示狀態(tài)之間的關(guān)系，就很容易發(fā)現(xiàn)，狀態(tài)之間組成的聯(lián)系實際上是二叉樹組成的森林。每一個s1=s2 的狀態(tài)都是一棵二叉樹的根。其余的每個狀態(tài)，a 或 c 往中間跳表示

12、往父親節(jié)點走一步對于所有狀態(tài)，中間節(jié)點往左右跳分別對應(yīng)往左右孩子走一步。設(shè)起始狀態(tài)對應(yīng)節(jié)點 p，目標狀態(tài)對原問題轉(zhuǎn)換成了樹上最短路問題。應(yīng)節(jié)點q。那么問題是：1.p 和q 是否同根。 2.如果同根，求p 到q 的距離。這兩個問題都可以用LCA 的知識來解決。（LCA 最近公共祖先）如果p 和 q 不存在 LCA 那么輸出NO。如果存在，那么計算LCA(p,q)到 p 和q 分別的距離，相加即為。【算法 2】可以用不斷往里跳的方法找兩個狀態(tài)的LCA。設(shè)輸入坐標范圍是 S，那么很容易得出一個 O(S2)的算法：枚舉LCA(p,q)到 p 的距離從q 不斷往父親方向走，判斷是否經(jīng)過枚舉的 LCA。如

13、果經(jīng)過，直接輸出答案并結(jié)束算法。如果一直找不到，判斷無解。這個算法可以得到 40 分。如果大范圍輸出無解，可以少許提高分數(shù)。仍然不能獲得 AC?！舅惴?3】算法 2 慢在對位置很離散的情況處理。發(fā)現(xiàn)在有些裝態(tài)，比如說 1 2 999999999 時，往父親走每次只能走一步。這樣等走到根就需要走 999999996 步。這也是為什么算法 2 超時的原因。也就是說，可能非常大。于是思考，可不可以一次走很多步?？梢?，簡單的數(shù)算就能解決問題。事實上可以在 O(logS)的時間內(nèi)做到把某狀態(tài)往父親走任意多步。（相當于 s1 和s2 輾轉(zhuǎn)相除，已證明此操作復雜度為對數(shù)階）這樣一來，可以直接計算p 和 q

14、在二叉樹中的深度。為了方便求LCA，不妨設(shè)h(p)h(q)。首先把p 和 q 深度調(diào)整到相同。h(x)表示 x 的深度。把q 往上走h(q)-h(p)步。求 2 個深度相同的點的 LCA，可以采用二分的方法。對于二分：LCA 到p 的距離mid，如果p 往上走mid 和 q 往上走mid 到達的點相同，midmid那么否則如此一來，得到了一個 O(logS)2)的算法。期望得分：100問題被完美解決。【總結(jié)】此題的原型是TopCoder SRM 463 Div 1 Problem 1000本題是原題的一個變形。悄悄話【問題描述】在這個有話不直說的年代，學越來越被廣泛接受。經(jīng)典的“”。在英文中，

15、加密只對 26 個字母生效（分大小寫）按照a 到z 來排字母。加密的原理就是把原文的每一個字母都按順序往后移 K 位。這個 K 將被作為密鑰。（a往后移變成b，z往后移會變成a）（0K25）現(xiàn)在給出一系列用加密的英文句子，請你編寫程序逐句翻譯。也就是說，請你確定一個密鑰，使得以后的文字最符合英文的規(guī)則與規(guī)范。數(shù)據(jù)保證存在唯一的方案，使得明碼是完全可以分辨的英文句子?！据斎敫袷健枯斎胍欢ò?10 行每一行都是用同一密鑰加密的英文。【輸出格式】輸出 10 行，為結(jié)果。不允許格式上有任何不同?！緲永斎搿縠 Vdkbnlde Nvctfdvmywo Nvctfdv Jrypbzr Ucjamk C

16、kriusk Xfmdpnfto sn to kf dy kf gbthe sgd the kyv dro kyv gur rfc znk uiftest. sdrs. test. kvjk. docd. kvjk. grfg. rcqr. zkyz. uftu.This Sghr This Kyzj Drsc Kyzj Guvf Rfgq Znoy Uijtis hr is zj sc zj vf gq oy jtthe sgd the kyv dro kyv gur rfc znk uif1st 2mc 3rd 4ky 5dr 6ky 7gu 8rf 9znsample rzlokd sa

17、mple jrdgcv ckwzvo jrdgcv fnzcyr qyknjc ygsvrktest sdrs test kvjk docd kvjk grfg rcqr zkyz uftucase. bzrd. case. trjv. mkco. trjv. pnfr. ayqc. igyk. dbtf.zu upmbtu tbnqmf【樣例輸出】etothetest.Thisisthe 1st sampletestcase.e e e e e e e e eto to to to to to to to tothe the the the the the the the thetest.

18、test. test. test. test. test. test. test. test.This This This This This This This This Thisis is is is is is is is isthe the the the the the the the the2nd 3rd 4th 5th 6th 7th 8th 9thsample sample sample sample sample sample sample sampletest test test test test test test test testcase. case. case.

19、case. case. case. case. case. case.last sample【數(shù)據(jù)說明】數(shù)據(jù)將從不同的方面。請盡量保證程序的準確性。每一行長度不會太短(不少于 3 個單詞的完整句)。沒有全角字符和其他語言符號，可能包含半角空格和標點。單個測試點不超過 5kB?！窘忸}】悄悄話這道題是一個開放性的試題。屬于比較容易拿分，但很難拿高分的題目。不存在標準的解答方法，只提供若干種參考的解決方案。首先，數(shù)據(jù)范圍不大?？紤]直接枚舉密鑰，把 26 種方案全部進行評分估價。最后輸出估價最大的方案進行輸出。以下是一些可以被納入估價的因素：【思路 1：字母頻率】分析字母頻率是學中常用的方法。由于英文

20、本身存在字符分布不均勻的情況，因此一般的加密算法都會留下字母頻率作為線索。對于幾乎所有足夠長的密文，只需要把 E 作為出現(xiàn)最多的字母，就可以正確了。經(jīng)過嘗試可以發(fā)現(xiàn)只要判斷E 就可以通過樣例了。但是最終得分會很低。因為對于短句子來說，頻率判斷是不可靠的。比如：Imsible is nothing. (*) （沒有不可能）這句話中i 出現(xiàn) 4 次，s 出現(xiàn) 3 次，o 出現(xiàn) 2 次，e 僅 1 次。的，些低頻字母?？梢耘袛喑霈F(xiàn)A E S T I R 這些高頻字母，和V Z W Q Y X 這如果有英語字母頻率對照表的話，（可以用大量英文來統(tǒng)計），可以用平均差或者方差來進行估分，這樣結(jié)果更準確。當

21、然也有一些麻煩的情況：The quick brown fox jumps over the lazy dog. (那只敏捷的棕毛狐貍躍過了那只懶狗。經(jīng)典英文句。)這個短句子中每個字母都出現(xiàn)了。還有一些英文繞口令，它們的字母頻率完全一邊倒：t pamper damp scamp tramps透的踩到坡道路燈下的帳篷了。)t camp under ramp lamps. (不要讓那些濕【思路 2：元輔音字母】雖然元音字母只有 6 個（A E I O U Y），但是出現(xiàn)的總頻率絕不比剩下的 20個低很多。這是一條重要線索。更甚，很少多個連續(xù)出現(xiàn)，元音也是?？梢耘袛嘣o音交替的平均速度。輔音字母在應(yīng)用時，注意避開全大寫的單詞。以及無關(guān)字符，包括數(shù)字、標點、空格。不然會出現(xiàn)以下悲?。篢hrough the IEEE/IEE electronic library (IEL), you can have over 750,000articles. (*) （通過IEEE/IEE 電子館IEL，你可以擁有 750000 篇文章。）恰當?shù)脑o音字母的判斷可以極大地提高破譯準確率。很少有句子可以逃過這種破譯?！舅悸?3：小單詞判斷】一個句子總會有一些小單詞。 is are the a an and I you they itt 等。如果預(yù)選方案出現(xiàn)這些單詞，可