1、第1頁結(jié)果提交類問題結(jié)果提交類問題【關(guān)鍵詞】【關(guān)鍵詞】結(jié)果提交結(jié)果提交數(shù)據(jù)分析數(shù)據(jù)分析隨機化隨機化策略策略【摘要】【摘要】結(jié)果提交類問題的歷史非常短，但其嶄新的模式、效率觀、時空觀，以及獨特的解題技巧、解題策略，和對各種方法的鼓勵，對選手更加深入、更加全面的考察而很快受到人們的青睞，在短期內(nèi)快速的傳播并發(fā)展，以至成為當(dāng)今信息學(xué)奧林匹克中的一種重要題型。本文就結(jié)果提交類問題的兩種重要技巧——數(shù)據(jù)分析和隨機化展開討論，提出此類問題所需要的不

2、同策略。用一句話概括本文的核心，即：在最短的時間內(nèi)得到正確結(jié)果，而不是過程?！灸夸洝俊灸夸洝恳弧⒁远?、數(shù)據(jù)分析三、隨機化四、結(jié)果提交類問題的策略1不同的效率觀和策略觀2不同的時空復(fù)雜觀3手工運算與程序運算的協(xié)調(diào)策略【正文】【正文】一、引一、引言結(jié)果提交類問題可算是當(dāng)今信息學(xué)奧林匹克競賽中最年輕的一類問題，然而IOI連續(xù)兩年出現(xiàn)此類問題的事實，使其成為主流競賽中不爭的必考題。其中最主要的原因，還是由于此類問題靈活新穎，以及命題人對殊途同

3、歸的倡導(dǎo)和對新奇方法的鼓勵?？v觀在近兩年來主流競賽中出現(xiàn)的Crackthecode，DoubleCrypt，Birthdayparty，Tetris，X等五道題目，可以說道道精彩，其中不僅充滿了巧妙的構(gòu)思，解題的方法也是百花齊放。但如何才能正確、迅速地完成此類問題，還需要我們深入地思考。本文以上述五道題目為例，分析結(jié)果提交類問題的一些特點，介紹一些針對結(jié)果提交類問題的特殊方法和技巧。伴隨著結(jié)果提交問題的出現(xiàn)，很多方面都發(fā)生了深刻的變革：

4、第3頁2如果為小寫字母，則變?yōu)榇髮懀D(zhuǎn)3；ic3如果為大寫字母，則對其連續(xù)進行次取后繼操作。我們ic1101)mod(i?a視‘A’的后繼為’B’，‘B’的后繼為’C’……‘Z’的后繼為’A’。然后將依次寫入對應(yīng)的cra.in文件。你的任務(wù)是根據(jù)提供的cra.in和iccra.txt(都在11KB以內(nèi))，得出cra.out。分析：這道題是沒有對于任何數(shù)據(jù)都非常有效的算法的，因為它畢竟是一種比較成形的加密算法。這也是命題者將此題作為結(jié)果提

5、交問題的根本原因，只需你要破解給出的數(shù)據(jù)即可。本題的解決方法很多，后面我們將要提到。還是先讓我們試著用數(shù)據(jù)分析的方法來考慮此題，來看看數(shù)據(jù)分析方法的威力。首先我們注意到本題數(shù)據(jù)只有5組，這和近年來10組甚至更多的測試數(shù)據(jù)不大一致，或許是在暗示這道題可以手算，換句話說，就為數(shù)據(jù)分析的方法提供了可能性可能性。注意到題目中的五篇文章都是英文的。我們清楚，英語中的許多高頻詞匯，如a，I，the，he，are，of，in，after等都是很短的，

6、同時，單詞長度越短，可能的情況就越少，如果長度為1，我們就基本可以肯定是a或I了。問題的關(guān)鍵是求出…，之后，cra.out自然也就很容易得到了。而…1a10a1a反映在微觀上，就是原文和加密后的文章中每個單詞（當(dāng)然更是某些單詞）10a的對應(yīng)字母之間的差異。也就是說，我們只要確定了少數(shù)原單詞和加密后單詞的一一對應(yīng)關(guān)系，…也就浮出水面了。比如是原單詞，1a10akAAA??21是加密后的單詞，是文章的第m個字母，則我們可以得到kBBB??2

7、11A，其中j=1，2，…k。反之，自jjBA????????????次取后繼操作進行110mod2)j(ma然有。jjAB????????????次取前趨操作進行110mod2)j(ma基于上述思路，我們完全可以僅用猜想試探少數(shù)單詞間對應(yīng)關(guān)系的方法處理本題，當(dāng)然還需要編兩三個十余行的輔助小程序來提高效率。這種方法全靠觀察能力和猜想能力，不涉及算法的復(fù)雜度。下面僅以數(shù)據(jù)一和數(shù)據(jù)五為例進行簡單說明。數(shù)據(jù)一：cra1.txt：ALFREDT