《国家集训队论文：雷环中——结果提交类问题》由会员分享，可在线阅读，更多相关《国家集训队论文：雷环中——结果提交类问题（27页珍藏版）》请在金锄头文库上搜索。
1、浅谈结果提交类问题 重庆外语学校 雷环中第 1 页结果提交类问题重庆外国语学校 雷环中【关键词】结果提交 数据分析 随机化 策略【摘要】结果提交类问题的历史非常短，但其崭新的模式、效率观、时空观，以及独特的解题技巧、解题策略，和对各种方法的鼓励，对选手更加深入、更加全面的考察而很快受到人们的青睐，在短期内快速的传播并发展，以至成为当今信息学奥林匹克中的一种重要题型。本文就结果提交类问题的两种重要技巧数据分析和随机化展开讨论，提出此类问题所需要的不同策略。用一句话概括本文的核心，即：在最短的时间内得到正确结果，而不是过程。【目录】一、引言二、数 据分析三、随 机化四、结果提交 类问题的策略1不同
2、的效率观和策略观 2不同的时空复杂观3手工运算与程序运算的协调策略【正文】一、引言结果提交类问题可算是当今信息学奥林匹克竞赛中最年轻的一类问题，然而 IOI 连续两年出现此类问题的事实，使其成为主流竞赛中不争的必考题。其中最主要的原因，还是由于此类问题灵活新颖，以及命题人对殊途同归的倡导和对新奇方法的鼓励。纵观在近两年来主流竞赛中出现的 Crack the code，Double Crypt，Birthday party， Tetris，Xor 等五道题目，可以说道道精彩，其中不仅充满了巧妙的构思，解题的方法也是百花齐放。但如何才能正确、迅速地完成此类问题，还需要我们深入地思考。本文以上述五道
3、题目为例，分析结果提交类问题的一些特点，介绍一些针对结果提交类问题的特殊方法和技巧。伴随着结果提交问题的出现，很多方面都发生了深刻的变革：浅谈结果提交类问题 重庆外语学校 雷环中第 2 页1 考察内容的变革在信息学奥林匹克竞赛发展已较为成熟的今天，仅仅就选手算法和数据结构方面能力作为主要考核标准是远远不够的。结果提交类问题的出现，使得考察的核心还涉及了一些更深层次的东西，如选手的思维能力、创造能力，全局策略、时间策略等等。这些方面的考察在以往题目中同样存在，但似乎都没有结构提交类问题体现得这样充分，考察得如此精妙。2 区分度的变革一道题目对选手的区分度发生了深刻的变革。我们不能仅仅依靠对算法时
4、空复杂度的分析来衡量算法的优劣，还应该综合考虑，衡量我们完成输出文件所花的时间。原因很简单，在以往，1 秒钟出解的程序和 10 秒钟出解的程序，测试的结果一般是前者得分要高不少；而结果提交类问题如果如果结果均正确，一名选手花 20 分钟，另一名花时 2 小时，前者则明显胜出，不论二人使用何种方法。3 题目的变革我们后面可以看到，如 Birthday Party 这样的题目，是否结果提交，完全决定了我们的思考方式，决定了算法。既然命题者将一道题目以结果提交的形式出现，就说明并不希望选手将其视为一道普通题目，而是希望选手大胆使用各种方法，以在最快时间内得到正确结果。倘我们仍以老的思路来看待此类问题
5、，不仅违背了命题者的意愿，浪费了所提供的输入文件，更重要的，我们将浪费更多的时间，甚至得不到理想的方法。结果提交，不是让我们放弃对完美算法的追求，而是鼓励我们站在综合效益的角度去得到结果。4 评卷方式的变革大家都清楚，信息学奥林匹克的评卷是黑箱的，然而以前的黑箱似乎显得相对较狭义。自从结果提交类问题出现以来，黑箱的涵义得到了进一步拓展，更突出了对结果的唯一追求。过程，或者说是程序，更加显得无足轻重了。我们用一句话来概括解决结果提交类问题的原则就是：永远提醒自己，你所需要的只是在最短的时间内得到正确结果，而不是过程。下面的讨论，也都是围绕此原则展开的。二、数据分析数据分析的方法始于结果提交类问题
6、，由于这种方法对选手的观察、思考、猜想及动手实践能力的要求较其他的方法更高，而且灵活多变，所以备受重视。下面以 Crack the code 和 Birthday party 为例进行说明。例一Crack the code(Baltic OI 2001)题目大意：有五个文件 cra*.out，与其对应的，有 cra*.txt，已知每一对文件出自同一篇文章。对于每个.out 文件，有十个未知的 Byte 型数 ，我们对文件的1a0第 i 个字符 进行下述变换：ic1如果 不是英文字母，则不做变化；i浅谈结果提交类问题 重庆外语学校 雷环中第 3 页2如果 为小写字母，则变为大写，转 3；ic3如
7、果 为大写字母，则对其连续进行 次取后继操作。我们i 10 1)mod-(ia视A的后继为 B， B的后继为C Z的后继为 A。然后将 依次写入对应的 cra.in 文件。你的任务是根据提供的 cra*.in 和iccra*.txt(都在 11KB 以内) ，得出 cra*.out。分析：这道题是没有对于任何数据都非常有效的算法的，因为它毕竟是一种比较成形的加密算法。这也是命题者将此题作为结果提交问题的根本原因，只需你要破解给出的数据即可。本题的解决方法很多，后面我们将要提到。还是先让我们试着用数据分析的方法来考虑此题，来看看数据分析方法的威力。首先我们注意到本题数据只有 5 组，这和近年来
8、10 组甚至更多的测试数据不大一致，或许是在暗示这道题可以手算，换句话说，就为数据分析的方法提供了可能性。注意到题目中的五篇文章都是英文的。我们清楚，英语中的许多高频词汇，如 a，I ，the， he，are，of ，in，after 等都是很短的，同时，单词长度越短，可能的情况就越少，如果长度为 1，我们就基本可以肯定是 a 或 I 了。问题的关键是求出 ，之后，cra.out 自然也就很容易得到了。而 a0 1a反映在微观上，就是原文和加密后的文章中每个单词（当然更是某些单词）10a的对应字母之间的差异。也就是说，我们只要确定了少数原单词和加密后单词的一一对应关系， 也就浮出水面了。比如
9、是原单词，1a0 kA21是加密后的单词， 是文章的第 m 个字母，则我们可以得到kB21 1A，其中 j=1，2，k 。反之，自jj BA 次 取 后 继 操 作进 行 1 0mod 2)-j(a然有 。jj AB次 取 前 趋 操 作进 行 1 0mod 2)-j(a基于上述思路，我们完全可以仅用猜想+试探少数单词间对应关系的方法处理本题，当然还需要编两三个十余行的辅助小程序来提高效率。这种方法全靠观察能力和猜想能力，不涉及算法的复杂度。下面仅以数据一和数据五为例进行简单说明。数据一：cra1.txt：ALFRED TARSKI WAS ONE OF THE GREATEST MATHEM
10、ATICIANS, LOGICIANS浅谈结果提交类问题 重庆外语学校 雷环中第 4 页AND PHILOSOPHERS OF THE PASSING CENTURY, AND ONE OF THE GREATEST LOGICIANSOF ALL TIME. 后略。cra1.inJK XHLMGXC PP ZEU OWL BM 1939 VP ZEU CRGBSHVOLD IJ UHGU XUK DYYXTM HPJIYPIO MGLTK BLYV DBMJG, GCVCPTTSLF LFHMX LM SOG NXHPECW TUKBBHMMER ZUF ZEUH,EQMDY 1943, C
11、Z QXY YYBULTYFJS SQ VZSKLLHHML TS IGXHUFIJ. 后略。对于输入文件，稍加观察我们便可以发现，位于第三行的 EQMDY 1943 是突破口。英语常识告诉我们，EQMDY 只能是 AFTER！同时，EQMDY 的E是文章的第 116 个字母，同时有 ，这样，10 个数就EQMDYAFTER )7,2519,4(被破了 5 个，具体地说，就是 ， ， ， ， 。我6a78a259710a们用得到的这 5 个数还原文本之后，就可以得到：JK XHLIVED IP ZEU OSA IN 1939 OP ZEU CNVITAVOLD IF JOHN XUK DYUM
12、AN APJIYPED THETK BLYR SINCG, GCVCLIATEF LFHMT AT THG NXHPARD UNKBBHMITY ANF ZEUH,AFTER 1943, CZ QXY UNIVETYFJS OF CALKLLHHIA AT BGXHUFEY. 后略。很多单词都已露出了“马脚” ，选择一两个较长的单词，即可轻松迅速地破解全文。如第二行的 THG NXHPARD UNKBBHMITY，我们不用想就知道应该是 THE HARVARD UNIVERSITY；还有第三行的 UNIVETYFJS OF CALKLLHHIA，我们也很容易看出是 UNIVERSITY OF
13、CALIFORNIA，因为cra1.txt 告诉我们这段文字是在描述一个人的生平。之后再做一次转换，得到，于是就可破解全文了。54321aa，数据五：cra5.txt：THE PLURAL IS USED HERE BECAUSE THE TERM HAHN-BANACH THEOREMIS CUSTOMARILY APPLIED TO SEVERAL CLOSELY RELATED RESULTS.cra5.inYSOEGOCYTV: OVN ZNGU IUIXS XB T ZXFTTJURYTR EUHBJF BLTIN NNA OVN RXICEW AKOLA Q* CQEXM ZZNI
14、XTCI FZZ HQA VUWJNVPCDOEOWUFZ AIWYMOXDFTN CW T.GUCU YPVH JZWOCYTV VBM OVGUQW UPZCEIRRSFBDCW WKK MUKQISM EG D* KO (.)NB DG LHXGA JMIO HQALK XFJZVHRKGY ME NVYSNZ FGTU C* QIHX W OKLJTZ NDJYX.对于官方的参考程序而言，数据五是最难的，但对于我们数据分析的方法而言，却是最简单的，我们甚至可在一分钟内将它破解。根据 cra5.txt 文件，我们可以大致判断这是一篇理科方面的文章，从英语语法的角度我们知道，cra5.in
15、 开始的 OVN 可能 是 the。 “YSOEGOCYTV:”似乎浅谈结果提交类问题 重庆外语学校 雷环中第 5 页是引出什么东西的定义。YSOEGOCYTV 共有 10 个字母，我们可以立即想到 或许 是 DEFINITION 这个单词。当然这不一定是对的，但试验之后，我们发现，文章到此已被完全破解：DEFINITION: THE DUAL SPACE OF A TOPOLOGICAL VECTOR SPACE XIS THE VECTOR SPACE X* WHOSE ELEMENTS ARE THE CONTINUOUSLINEAR FUNCTIONALS ON X.NOTE THAT ADDITION AND SCALAR MULTIPLICATION ARE DEFINED IN X* BY (.)IT IS CLEAR THAT THESE OPERATIONS DO INDEED MAKE X* INT
