結(jié)果提交類問題

1、結(jié)果提交類問題第1頁，共33頁，2022年，5月20日，19點23分，星期二結(jié)果提交類問題概念：提供輸入數(shù)據(jù)，提交結(jié)果重要技巧：數(shù)據(jù)分析 隨機化深刻變革綜合策略原則：最短時間內(nèi)得到正確結(jié)果第2頁，共33頁，2022年，5月20日，19點23分，星期二數(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)= Asucc(C,0)=C , succ(C,n)=succ(succ(C,n-1),1) , nN

2、另有密碼整數(shù)a1 a2 a10，對cra.out第i個字母ci作轉(zhuǎn)換：1. 如ci為小寫，則變?yōu)榇髮懀D(zhuǎn)22. 如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第3頁，共33頁，2022年，5月20日，19點23分，星期二數(shù)據(jù)分析法考慮我們先看一個數(shù)據(jù)：信息文本：cra1.txt：ALFRED TARSKI WAS ONE OF THE GREATEST MATHEMATICIANS, LOGICIANS AND PHILOSOPHERS OF THE

3、 PASSING CENTURY, AND ONE OF THE GREATEST LOGICIANS OF ALL TIME. 后略。密文：cra1.inJK 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é)論：文章是英文第4頁，共33

4、頁，2022年，5月20日，19點23分，星期二數(shù)據(jù)分析法考慮聯(lián)想思考：許多高頻詞匯都很短(如a，I，the，of等) a1a10意義：原文和密文單詞對應(yīng)字母差異 建立對應(yīng)：原單詞A1A2Ak 加密后單詞B1B2Bk 則有： Bj=succ(Aj ,a(m+j-2) mod 10 +1 ) A1是文章第m個字母 ，j=1，2，k 方法：猜想+試探單詞對應(yīng)關(guān)系 關(guān)鍵：充分發(fā)揮手工和程序各自的優(yōu)勢 第5頁，共33頁，2022年，5月20日，19點23分，星期二舉例信息文本：cra1.txt：ALFRED TARSKI WAS ONE OF THE GREATEST MATHEMATICIANS,

5、LOGICIANS AND PHILOSOPHERS OF THE PASSING CENTURY, AND ONE OF THE GREATEST LOGICIANS OF ALL TIME. 后略。密文：cra1.inJK 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 VZSKLLHH

6、ML TS IGXHUFIJ. 后略。信息：文字在描述某人生平 AFTER！EQMDY的E是文章第116個字母 結(jié)果：a6=4，a7=11，a8=19，a9=25，a10=7 第6頁，共33頁，2022年，5月20日，19點23分，星期二舉例用a6a10還原文本得：JK XHLIVED 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

7、UNIVETYFJS OF CALKLLHHIAAT BGXHUFEY. 后略。THE HARVARD UNIVERSITY THE UNIVERSITY OF CALIFORNIA于是可得a1，a2，a3，a4，a5 全文可破第7頁，共33頁，2022年，5月20日，19點23分，星期二再舉一例cra8.txtMy name is Mary.cra8.inJ CP E HRLDNB HKUP. N GT VXD CCG.I AM A1 2 3 4a1 a2 a3 a4151617 181920a5 a6 a7 a8 a9 a10I AM A CLEVER GIRL. I AM NOT BAD

8、. I AM NOT第8頁，共33頁，2022年，5月20日，19點23分，星期二(分母為0的修正)經(jīng)典方法考慮算法思路：每種字母出現(xiàn)頻率不同頻率比較用P= (PA PZ)表示未加密文本中每個字母出現(xiàn)的相對頻率用Q=(QAQZ)表示密文中第i+10*(N-1)位字母組成集合中 每個字母出現(xiàn)的相對頻率( 用以確定ai )比較P和Q的相似程度-估價函數(shù)的選擇 方法一：方法二：方法三：第9頁，共33頁，2022年，5月20日，19點23分，星期二方法比較一二三四五六七八九總分方法一 101010108851163方法二101010108831161方法三1010101010752165官方程序 10

9、10101010640161數(shù)據(jù)分析法1010101010101010080結(jié)論：1.以上算法均不理想-結(jié)果提交的原因 2.程序方法差異不大 隨著樣本容量的減小，正確率顯著降低 3.對于本題結(jié)果提交特點，數(shù)據(jù)分析法相對最好！表中數(shù)字為該數(shù)據(jù)算對的密碼位數(shù)，前五組為官方數(shù)據(jù)第10頁，共33頁，2022年，5月20日，19點23分，星期二數(shù)據(jù)分析法小結(jié)長處：具體問題具體分析，易于實現(xiàn) 短處：不利于處理規(guī)模數(shù)據(jù)關(guān)鍵：觀察數(shù)據(jù)特點精髓：手工與程序運算相協(xié)調(diào)目的：在最短的時間內(nèi)得到正確結(jié)果 第11頁，共33頁，2022年，5月20日，19點23分，星期二隨機化不同的隨機化：經(jīng)典隨機化 需在規(guī)定時間內(nèi)出解

10、 評測時只運行一次結(jié)果提交類問題的隨機化 沒有任何限制 目標(biāo)只有一個：得到正確結(jié)果！ 得到算法最有利因素，避開不利因素第12頁，共33頁，2022年，5月20日，19點23分，星期二隨機化例：Tetris(NOI 2002)題目大意： 給出一個初始俄羅斯方塊的棋盤狀態(tài)， 每次可從標(biāo)準(zhǔn)的19種形狀中任選一種， 放到任意位置上，要求在100000步以內(nèi) 將棋盤消空。輸入數(shù)據(jù)保證有解。 限制：棋盤永遠不能懸空 放置不能超出邊界第13頁，共33頁，2022年，5月20日，19點23分，星期二分析測試數(shù)據(jù)Tetris1.in90 1 1 1 0 0 0 0 0Tetris2.in65 2 4 3 0 2

11、第14頁，共33頁，2022年，5月20日，19點23分，星期二分析測試數(shù)據(jù)Tetris3.in2000 2 4 6 6 8 10 12 12 14 16 18 18 2022 24 24 26 28 30 30 32 34 36 后略。數(shù)據(jù)以四列為單位規(guī)律出現(xiàn)。最基本的(0,2,4,6)容易處理：本數(shù)據(jù)只需一個小程序即可解決第15頁，共33頁，2022年，5月20日，19點23分，星期二分析測試數(shù)據(jù)下面是后面幾組數(shù)據(jù)的規(guī)模：（數(shù)據(jù)略）Tetris4.in N=16Tetris5.in N=47Tetris6.in N=97Tetris7.in N=100Tetris8.in N=246Tet

12、ris9.in N=574Tetris10.in N=1202第16頁，共33頁，2022年，5月20日，19點23分，星期二綜合分析數(shù)據(jù)一、二：規(guī)模很小，手工能迅速出解 N9數(shù)據(jù)三： 規(guī)模較大，規(guī)律明顯，只需 N200 一個短程序數(shù)據(jù)四、五：規(guī)模不小，可手算，但需一 N50 定時間數(shù)據(jù)六十：規(guī)模較大，規(guī)律很不明顯或 N97 無規(guī)律，手工無法勝任這其實也是一種數(shù)據(jù)分析第17頁，共33頁，2022年，5月20日，19點23分，星期二隨機化兩種形狀：形狀一形狀二對于任一初狀態(tài)，可僅用這兩種形狀使棋盤高度不超過3然后從左到右找“空”，隨機用一個合法的形狀填上此空，直到將棋盤完全弄平應(yīng)在隨機的基礎(chǔ)上加

13、入一些人的思想此算法很粗劣，顯得過于隨機第18頁，共33頁，2022年，5月20日，19點23分，星期二優(yōu)化一對于下面一個殘局：結(jié)論： 應(yīng)盡量使用下面兩種形狀，以使棋盤盡量顯得平整我們的算法卻在這樣隨機生成形狀： 這樣雖合法，但對大數(shù)據(jù)而言步數(shù)太多。其實只需：第19頁，共33頁，2022年，5月20日，19點23分，星期二優(yōu)化二應(yīng)盡量避免下面四種形狀，以減少突兀 類似的優(yōu)化還有很多第20頁，共33頁，2022年，5月20日，19點23分，星期二隨機化死機概率程序花時得到算法最有利因素避開算法不利因素第21頁，共33頁，2022年，5月20日，19點23分，星期二經(jīng)典方法算法一：貪心 每一步都使

14、棋盤變得更平 直到最后完全平整算法二：構(gòu)造 以4列為單位對棋盤分組 如最后不足4列，則獨為一組 先填平4列組 再用形狀2（橫四）結(jié)合貪心填平整個棋盤注意組間協(xié)調(diào)，保證可行性第22頁，共33頁，2022年，5月20日，19點23分，星期二如下圖，第一、二、三組均無法通過組內(nèi)調(diào)節(jié)填平因為它們原有塊數(shù)分為2、5、5，皆非4的倍數(shù)算法二第一組第二組第三組第23頁，共33頁，2022年，5月20日，19點23分，星期二通過下圖的組間調(diào)節(jié)使它們都變成4的倍數(shù)調(diào)節(jié)后三組的塊數(shù)分為4、8、8 算法二第三組第二組第一組第24頁，共33頁，2022年，5月20日，19點23分，星期二之后每組便很易填平如下圖所示：

15、算法二第三組第二組第一組第25頁，共33頁，2022年，5月20日，19點23分，星期二算法比較時間復(fù)雜度空間復(fù)雜度運行速度算法實現(xiàn)復(fù)雜度解的質(zhì)量隨機化算法O(M)O(N)1s低較差算法一O(MN)O(N)10s低較好算法二O(N)O(N)0.5s較高較好不同要求下我們的算法可能不同因為還要綜合考慮算法實現(xiàn)的復(fù)雜度 M出解步數(shù)，N棋盤規(guī)模結(jié)論：對結(jié)果提交，隨機化算法和算法一最合適 對非結(jié)果提交，算法二最好第26頁，共33頁，2022年，5月20日，19點23分，星期二深刻變革大大擴展了程序的可用空間 以至沒有嚴格限制 時限更自由，甚至可達幾個小時 多線程方法嶄露頭角 測試數(shù)據(jù)作為題目的組成部分

16、出現(xiàn)第27頁，共33頁，2022年，5月20日，19點23分，星期二綜合策略結(jié)果提交類問題 飛流直下-曲線開始斜率較大，后逐漸減小經(jīng)典問題 厚積薄發(fā)-曲線始末斜率較小，中間階段斜率較大 結(jié)果提交(I)與經(jīng)典(II)問題完成題目時間與得分關(guān)系圖 程序效率得 分第28頁，共33頁，2022年，5月20日，19點23分，星期二綜合策略 結(jié)果提交(I)與經(jīng)典(II)問題完成題目時間與得分關(guān)系圖 區(qū)別一：經(jīng)典問題中常不知何時“適可而止”算法上得到提高，策略上并不明智結(jié)果提交問題中對能得分數(shù)有較準(zhǔn)估計，不會多花無謂時間第29頁，共33頁，2022年，5月20日，19點23分，星期二綜合策略 結(jié)果提交(I)與經(jīng)典(II)問題完成題目時間與得分關(guān)系圖 區(qū)別二：兩種方法程序效率(得分)都在某段較短時間內(nèi)迅速上升而這段時間在結(jié)果提交問題中顯然要相對提前很多第30頁，共33頁，2022年，5月20日，19點23分