【資料下載】結果提交類問題

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

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

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

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

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了。問題的關鍵是求出…，之后，cra.out自然也就很容易得到了。而…1a10a1a反映在微觀上，就是原文和加密后的文章中每個單詞（當然更是某些單詞）10a的對應字母之間的差異。也就是說，我們只要確定了少數(shù)原單詞和加密后單詞的一一對應關系，…也就浮出水面了。比如是原單詞，1a10akAAA??21是加密后的單詞，是文章的第m個字母，則我們可以得到kBBB??2

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