【資料下載】結(jié)果提交類問(wèn)題

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

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

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

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

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

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

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