算法合集之結(jié)果提交類問題

算法合集之結(jié)果提交類問題第一頁(yè)，共三十三頁(yè)，2022年，8月28日結(jié)果提交類問題概念：提供輸入數(shù)據(jù)，提交結(jié)果重要技巧：數(shù)據(jù)分析隨機(jī)化深刻變革綜合策略原則：最短時(shí)間內(nèi)得到正確結(jié)果第二頁(yè)，共三十三頁(yè)，2022年，8月28日數(shù)據(jù)分析[例]Crackthecode(BalticOI2001)文件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),n∈N另有密碼整數(shù)a1a2

……a10，對(duì)cra.out第i個(gè)字母ci作轉(zhuǎn)換：1.如ci為小寫，則變?yōu)榇髮?，轉(zhuǎn)22.如ci為大寫，則作變換ci=succ(ci,a(i-1)mod10+1)cra.out轉(zhuǎn)換后的結(jié)果即cra.in你的任務(wù)是根據(jù)提供的cra.in和cra.txt，得出cra.out第三頁(yè)，共三十三頁(yè)，2022年，8月28日數(shù)據(jù)分析法考慮我們先看一個(gè)數(shù)據(jù)：信息文本：cra1.txt：ALFREDTARSKIWASONEOFTHEGREATESTMATHEMATICIANS,LOGICIANSANDPHILOSOPHERSOFTHEPASSINGCENTURY,ANDONEOFTHEGREATESTLOGICIANSOFALLTIME.后略。密文：cra1.inJKXHLMGXCPPZEUOWLBM1939VPZEUCRGBSHVOLDIJUHGUXUKDYYXTMHPJIYPIOMGLTKBLYVDBMJG,GCVCPTTSLFLFHMXLMSOGNXHPECWTUKBBHMMERZUFZEUH,EQMDY1943,CZQXYYYBULTYFJSSQVZSKLLHHMLTSIGXHUFIJ.后略。結(jié)論：文章是英文第四頁(yè)，共三十三頁(yè)，2022年，8月28日數(shù)據(jù)分析法考慮聯(lián)想思考：許多高頻詞匯都很短(如a，I，the，of等)a1……a10意義：原文和密文單詞對(duì)應(yīng)字母差異

建立對(duì)應(yīng)：原單詞A1A2……Ak

加密后單詞B1B2……Bk

則有：

Bj=succ(Aj,a(m+j-2)mod10+1)

A1是文章第m個(gè)字母，j=1，2，…k

方法：猜想+試探單詞對(duì)應(yīng)關(guān)系關(guān)鍵：充分發(fā)揮手工和程序各自的優(yōu)勢(shì)第五頁(yè)，共三十三頁(yè)，2022年，8月28日舉例信息文本：cra1.txt：ALFREDTARSKIWASONEOFTHEGREATESTMATHEMATICIANS,LOGICIANSANDPHILOSOPHERSOFTHEPASSINGCENTURY,ANDONEOFTHEGREATESTLOGICIANSOFALLTIME.后略。密文：cra1.inJKXHLMGXCPPZEUOWLBM1939VPZEUCRGBSHVOLDIJUHGUXUKDYYXTMHPJIYPIOMGLTKBLYVDBMJG,GCVCPTTSLFLFHMXLMSOGNXHPECWTUKBBHMMERZUFZEUH,EQMDY1943,CZQXYYYBULTYFJSSQVZSKLLHHMLTSIGXHUFIJ.后略。信息：文字在描述某人生平

AFTER！EQMDY的’E’是文章第116個(gè)字母結(jié)果：a6=4，a7=11，a8=19，a9=25，a10=7第六頁(yè)，共三十三頁(yè)，2022年，8月28日舉例用a6…a10還原文本得：JKXHLIVEDIPZEUOSAIN1939OPZEUCNVITAVOLDIFJOHNXUKDYUMANAPJIYPEDTHETKBLYRSINCG,GCVCLIATEFLFHMTATTHGNXHPARDUNKBBHMITYANFZEUH,AFTER1943,CZQXYUNIVETYFJSOFCALKLLHHIAATBGXHUFEY.

后略。THEHARVARDUNIVERSITY

THEUNIVERSITYOFCALIFORNIA于是可得a1，a2，a3，a4，a5

全文可破第七頁(yè)，共三十三頁(yè)，2022年，8月28日再舉一例cra8.txtMynameisMary.cra8.inJCPEHRLDNBHKUP.NGTVXDCCG.IAMA1234a1a2a3a4151617181920a5a6a7a8a9a10IAMACLEVERGIRL.IAMNOTBAD.IAMNOT第八頁(yè)，共三十三頁(yè)，2022年，8月28日(分母為0的修正)經(jīng)典方法考慮算法思路：每種字母出現(xiàn)頻率不同→頻率比較用P=(PA…PZ)表示未加密文本中每個(gè)字母出現(xiàn)的相對(duì)頻率用Q=(QA…QZ)表示密文中第i+10*(N-1)位字母組成集合中每個(gè)字母出現(xiàn)的相對(duì)頻率(

用以確定ai)比較P和Q的相似程度----估價(jià)函數(shù)的選擇方法一：方法二：方法三：第九頁(yè)，共三十三頁(yè)，2022年，8月28日方法比較一二三四五六七八九總分方法一

101010108851163方法二101010108831161方法三1010101010752165官方程序

1010101010640161數(shù)據(jù)分析法1010101010101010080結(jié)論：1.以上算法均不理想----結(jié)果提交的原因

2.程序方法差異不大隨著樣本容量的減小，正確率顯著降低

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

分析測(cè)試數(shù)據(jù)Tetris1.in9011100000

Tetris2.in6524302

第十四頁(yè)，共三十三頁(yè)，2022年，8月28日分析測(cè)試數(shù)據(jù)Tetris3.in200024668101212141618182022242426283030323436后略。數(shù)據(jù)以四列為單位規(guī)律出現(xiàn)。最基本的(0,2,4,6)容易處理：

本數(shù)據(jù)只需一個(gè)小程序即可解決第十五頁(yè)，共三十三頁(yè)，2022年，8月28日分析測(cè)試數(shù)據(jù)下面是后面幾組數(shù)據(jù)的規(guī)模：（數(shù)據(jù)略）Tetris4.inN=16Tetris5.inN=47Tetris6.inN=97Tetris7.inN=100Tetris8.inN=246Tetris9.inN=574Tetris10.inN=1202第十六頁(yè)，共三十三頁(yè)，2022年，8月28日綜合分析數(shù)據(jù)一、二：規(guī)模很小，手工能迅速出解

N≤9數(shù)據(jù)三：規(guī)模較大，規(guī)律明顯，只需

N＝200一個(gè)短程序數(shù)據(jù)四、五：規(guī)模不小，可手算，但需一

N＜50定時(shí)間數(shù)據(jù)六…十：規(guī)模較大，規(guī)律很不明顯或

N≥97無(wú)規(guī)律，手工無(wú)法勝任這其實(shí)也是一種數(shù)據(jù)分析第十七頁(yè)，共三十三頁(yè)，2022年，8月28日隨機(jī)化兩種形狀：形狀一形狀二對(duì)于任一初狀態(tài)，可僅用這兩種形狀使棋盤高度不超過3然后從左到右找“空”，隨機(jī)用一個(gè)合法的形狀填上此空，直到將棋盤完全弄平應(yīng)在隨機(jī)的基礎(chǔ)上加入一些人的思想此算法很粗劣，顯得過于隨機(jī)第十八頁(yè)，共三十三頁(yè)，2022年，8月28日優(yōu)化一對(duì)于下面一個(gè)殘局：

結(jié)論：應(yīng)盡量使用下面兩種形狀，以使棋盤盡量顯得平整

我們的算法卻在這樣隨機(jī)生成形狀：

這樣雖合法，但對(duì)大數(shù)據(jù)而言步數(shù)太多。其實(shí)只需：

第十九頁(yè)，共三十三頁(yè)，2022年，8月28日優(yōu)化二應(yīng)盡量避免下面四種形狀，以減少突兀

類似的優(yōu)化還有很多……第二十頁(yè)，共三十三頁(yè)，2022年，8月28日隨機(jī)化死機(jī)概率程序花時(shí)得到算法最有利因素避開算法不利因素第二十一頁(yè)，共三十三頁(yè)，2022年，8月28日經(jīng)典方法算法一：貪心每一步都使棋盤變得更平直到最后完全平整算法二：構(gòu)造以4列為單位對(duì)棋盤分組如最后不足4列，則獨(dú)為一組先填平4列組再用形狀2（橫四）結(jié)合貪心填平整個(gè)棋盤注意組間協(xié)調(diào)，保證可行性第二十二頁(yè)，共三十三頁(yè)，2022年，8月28日如下圖，第一、二、三組均無(wú)法通過組內(nèi)調(diào)節(jié)填平因?yàn)樗鼈冊(cè)袎K數(shù)分為2、5、5，皆非4的倍數(shù)算法二……第一組第二組第三組第二十三頁(yè)，共三十三頁(yè)，2022年，8月28日通過下圖的組間調(diào)節(jié)使它們都變成4的倍數(shù)調(diào)節(jié)后三組的塊數(shù)分為4、8、8算法二第三組第二組第一組……第二十四頁(yè)，共三十三頁(yè)，2022年，8月28日之后每組便很易填平如下圖所示：算法二第三組第二組第一組……第二十五頁(yè)，共三十三頁(yè)，2022年，8月28日算法比較時(shí)間復(fù)雜度空間復(fù)雜度運(yùn)行速度算法實(shí)現(xiàn)復(fù)雜度解的質(zhì)量隨機(jī)化算法O(M)O(N)﹤1s低較差算法一O(M×N)O(N)﹤10s低較好算法二O(N)O(N)﹤0.5s較高較好不同要求下我們的算法可能不同因?yàn)檫€要綜合考慮算法實(shí)現(xiàn)的復(fù)雜度M——出解步數(shù)，N——棋盤規(guī)模結(jié)論：對(duì)結(jié)果提交，隨機(jī)化算法和算法一最合適對(duì)非結(jié)果提交，算法二最好第二十六頁(yè)，共三十三頁(yè)，2022年，8月28日深刻變革大大擴(kuò)展了程序的可用空間

以至沒有嚴(yán)格限制……時(shí)限更自由，甚至可達(dá)幾個(gè)小時(shí)多線程方法嶄露頭角測(cè)試數(shù)據(jù)作為題目的組成部分出現(xiàn)第二十七頁(yè)，共三十三頁(yè)，2022年，8月28日綜合策略結(jié)果提交類問題飛流直下----