1、結(jié)果提交類問題,重慶外語學(xué)校 雷環(huán)中,結(jié)果提交類問題,概念：提供輸入數(shù)據(jù)，提交結(jié)果 重要技巧：數(shù)據(jù)分析 隨機(jī)化 深刻變革 綜合策略 原則：最短時(shí)間內(nèi)得到正確結(jié)果,數(shù)據(jù)分析,例Crack the code(Baltic OI 2001) 文件cra.out與cra.txt出自同一篇文章。 定義函數(shù)succ(C,1)為大寫字母C的后繼 有succ(A,1)= B , succ(B,1)= C , , succ(Z,1)= A succ(C,0)=C , succ(C,n)=succ(succ(C,n-1),1) , nN 另有密碼整數(shù)a1 a2 a10，對cra.out第i個(gè)字母ci作轉(zhuǎn)換：,1.

2、 如ci為小寫，則變?yōu)榇髮?，轉(zhuǎn)2 2. 如ci為大寫，則作變換ci=succ(ci ,a(i-1) mod 10 + 1 ),cra.out轉(zhuǎn)換后的結(jié)果即cra.in 你的任務(wù)是根據(jù)提供的cra.in和cra.txt，得出cra.out,數(shù)據(jù)分析法考慮,我們先看一個(gè)數(shù)據(jù)：,信息文本： cra1.txt： ALFRED TARSKI WAS ONE OF THE GREATEST MATHEMATICIANS, LOGICIANS AND PHILOSOPHERS OF THE PASSING CENTURY, AND ONE OF THE GREATEST LOGICIANS OF ALL T

3、IME. 后略。 密文： cra1.in JK XHLMGXC PP ZEU OWL BM 1939 VP ZEU CRGBSHVOLD IJ UHGU XUK DYYXTM HPJ IYPIO MGLTK BLYV DBMJG, GCVCPTTSLF LFHMX LM SOG NXHPECW TUKBBHMMER ZUF ZEUH,EQMDY 1943, CZ QXY YYBULTYFJS SQ VZSKLLHHML TS IGXHUFIJ. 后略。,結(jié)論：文章是英文,數(shù)據(jù)分析法考慮,聯(lián)想思考：許多高頻詞匯都很短(如a，I，the，of等),a1a10意義：原文和密文單詞對應(yīng)字母差異,建立對

4、應(yīng)：,原單詞A1A2Ak,加密后單詞B1B2Bk,則有： Bj=succ(Aj ,a(m+j-2) mod 10 +1 ) A1是文章第m個(gè)字母 ，j=1，2，k,方法：猜想+試探單詞對應(yīng)關(guān)系,關(guān)鍵：充分發(fā)揮手工和程序各自的優(yōu)勢,舉例,信息文本： cra1.txt： ALFRED TARSKI WAS ONE OF THE GREATEST MATHEMATICIANS, LOGICIANS AND PHILOSOPHERS OF THE PASSING CENTURY, AND ONE OF THE GREATEST LOGICIANS OF ALL TIME. 后略。 密文： cra1.i

5、n JK XHLMGXC PP ZEU OWL BM 1939 VP ZEU CRGBSHVOLD IJ UHGU XUK DYYXTM HPJ IYPIO MGLTK BLYV DBMJG, GCVCPTTSLF LFHMX LM SOG NXHPECW TUKBBHMMER ZUF ZEUH, EQMDY 1943, CZ QXY YYBULTYFJS SQ VZSKLLHHML TS IGXHUFIJ. 后略。,信息：文字在描述某人生平,EQMDY的E是文章第116個(gè)字母,結(jié)果：a6=4，a7=11，a8=19，a9=25，a10=7,舉例,用a6a10還原文本得：,JK XHLIVED

6、 IP ZEU OSA IN 1939 OP ZEU CNVITAVOLD IF JOHN XUK DYUMAN APJ IYPED THETK BLYR SINCG, GCVCLIATEF LFHMT AT THG NXHPARD UNKBBHMITY ANF ZEUH, AFTER 1943, CZ QXY UNIVETYFJS OF CALKLLHHIA AT BGXHUFEY. 后略。,THE HARVARD UNIVERSITY,THE UNIVERSITY OF CALIFORNIA,于是可得a1，a2，a3，a4，a5,全文可破,再舉一例,cra8.txt My name is

7、Mary. cra8.in J CP E HRLDNB HKUP. N GT VXD CCG.,I AM A,1 2 3 4,a1 a2 a3 a4,151617 181920,a5 a6 a7 a8 a9 a10,I AM A CLEVER GIRL. I AM NOT BAD.,I AM NOT,(分母為0的修正),經(jīng)典方法考慮,算法思路：每種字母出現(xiàn)頻率不同頻率比較,方法比較,結(jié)論：1.以上算法均不理想-結(jié)果提交的原因 2.程序方法差異不大 隨著樣本容量的減小，正確率顯著降低 3.對于本題結(jié)果提交特點(diǎn)，數(shù)據(jù)分析法相對最好！,表中數(shù)字為該數(shù)據(jù)算對的密碼位數(shù)，前五組為官方數(shù)據(jù),數(shù)據(jù)分析法小結(jié)

8、,長處：具體問題具體分析，易于實(shí)現(xiàn) 短處：不利于處理規(guī)模數(shù)據(jù) 關(guān)鍵：觀察數(shù)據(jù)特點(diǎn) 精髓：手工與程序運(yùn)算相協(xié)調(diào) 目的：在最短的時(shí)間內(nèi)得到正確結(jié)果,隨機(jī)化,不同的隨機(jī)化：,經(jīng)典隨機(jī)化 需在規(guī)定時(shí)間內(nèi)出解 評測時(shí)只運(yùn)行一次,結(jié)果提交類問題的隨機(jī)化 沒有任何限制 目標(biāo)只有一個(gè)：得到正確結(jié)果！,得到算法最有利因素，避開不利因素,隨機(jī)化,例：Tetris(NOI 2002) 題目大意： 給出一個(gè)初始俄羅斯方塊的棋盤狀態(tài)， 每次可從標(biāo)準(zhǔn)的19種形狀中任選一種， 放到任意位置上，要求在100000步以內(nèi) 將棋盤消空。輸入數(shù)據(jù)保證有解。 限制：棋盤永遠(yuǎn)不能懸空 放置不能超出邊界,分析測試數(shù)據(jù),Tetris1.i

9、n 9 0 1 1 1 0 0 0 0 0,Tetris2.in 6 5 2 4 3 0 2,分析測試數(shù)據(jù),Tetris3.in 200 0 2 4 6 6 8 10 12 12 14 16 18 18 20 22 24 24 26 28 30 30 32 34 36 后略。,數(shù)據(jù)以四列為單位規(guī)律出現(xiàn)。 最基本的(0,2,4,6)容易處理：,本數(shù)據(jù)只需一個(gè)小程序即可解決,分析測試數(shù)據(jù),下面是后面幾組數(shù)據(jù)的規(guī)模：（數(shù)據(jù)略） Tetris4.in N=16 Tetris5.in N=47 Tetris6.in N=97 Tetris7.in N=100 Tetris8.in N=246 Tetri

10、s9.in N=574 Tetris10.in N=1202,綜合分析,數(shù)據(jù)一、二：規(guī)模很小，手工能迅速出解 N9 數(shù)據(jù)三： 規(guī)模較大，規(guī)律明顯，只需 N200 一個(gè)短程序 數(shù)據(jù)四、五：規(guī)模不小，可手算，但需一 N50 定時(shí)間 數(shù)據(jù)六十：規(guī)模較大，規(guī)律很不明顯或 N97 無規(guī)律，手工無法勝任,這其實(shí)也是一種數(shù)據(jù)分析,隨機(jī)化,兩種形狀：,對于任一初狀態(tài)，可僅用這兩種形狀使棋盤高度不超過3,然后從左到右找“空”，隨機(jī)用一個(gè)合法的形狀填上此空， 直到將棋盤完全弄平,應(yīng)在隨機(jī)的基礎(chǔ)上加入一些人的思想,此算法很粗劣，顯得過于隨機(jī),優(yōu)化一,對于下面一個(gè)殘局：,結(jié)論： 應(yīng)盡量使用下面兩種形狀，以使棋盤盡量顯

11、得平整,我們的算法卻在這樣隨機(jī)生成形狀：,這樣雖合法，但對大數(shù)據(jù)而言步數(shù)太多。其實(shí)只需：,優(yōu)化二,應(yīng)盡量避免下面四種形狀，以減少突兀,類似的優(yōu)化還有很多,隨機(jī)化,死機(jī)概率,程序花時(shí),得到算法最有利因素 避開算法不利因素,經(jīng)典方法,算法一：貪心 每一步都使棋盤變得更平 直到最后完全平整,算法二：構(gòu)造 以4列為單位對棋盤分組 如最后不足4列，則獨(dú)為一組 先填平4列組 再用形狀2（橫四）結(jié)合貪心填平整個(gè)棋盤,注意組間協(xié)調(diào)，保證可行性,如下圖，第一、二、三組均無法通過組內(nèi)調(diào)節(jié)填平 因?yàn)樗鼈冊袎K數(shù)分為2、5、5，皆非4的倍數(shù),算法二,通過下圖的組間調(diào)節(jié)使它們都變成4的倍數(shù) 調(diào)節(jié)后三組的塊數(shù)分為4、8、

12、8,算法二,之后每組便很易填平 如下圖所示：,算法二,算法比較,不同要求下我們的算法可能不同 因?yàn)檫€要綜合考慮算法實(shí)現(xiàn)的復(fù)雜度,M出解步數(shù)，N棋盤規(guī)模,結(jié)論：對結(jié)果提交，隨機(jī)化算法和算法一最合適 對非結(jié)果提交，算法二最好,深刻變革,大大擴(kuò)展了程序的可用空間 以至沒有嚴(yán)格限制,時(shí)限更自由，甚至可達(dá)幾個(gè)小時(shí),多線程方法嶄露頭角,測試數(shù)據(jù)作為題目的組成部分出現(xiàn),綜合策略,結(jié)果提交類問題 飛流直下-曲線開始斜率較大，后逐漸減小 經(jīng)典問題 厚積薄發(fā)-曲線始末斜率較小，中間階段斜率較大,得 分,綜合策略,結(jié)果提交(I)與經(jīng)典(II)問題完成題目時(shí)間與得分關(guān)系圖,區(qū)別一： 經(jīng)典問題中常不知何時(shí)“適可而止” 算法上得到提高，策略上并不明智 結(jié)果提交問題中對能得分?jǐn)?shù)有較準(zhǔn)估計(jì)，不會多花無謂時(shí)間,綜合策略,結(jié)果提交(I)與經(jīng)典(II)問題完成題目時(shí)間與得分關(guān)系圖,區(qū)別二： 兩種方法程序效率(得分)都在某段較短時(shí)間內(nèi)迅