国家集训队论文：雷环中——结果提交类问题.docVIP

结果提交类问题 重庆外国语学校 雷环中 【关键词】 结果提交 数据分析 随机化 策略 【摘要】 结果提交类问题的历史非常短，但其崭新的模式、效率观、时空观，以及独特的解题技巧、解题策略，和对各种方法的鼓励，对选手更加深入、更加全面的考察而很快受到人们的青睐，在短期内快速的传播并发展，以至成为当今信息学奥林匹克中的一种重要题型。本文就结果提交类问题的两种重要技巧——数据分析和随机化展开讨论，提出此类问题所需要的不同策略。用一句话概括本文的核心，即：在最短的时间内得到正确结果，而不是过程。 【目录】 一、引言 二、数据分析 三、随机化 四、结果提交类问题的策略 不同的效率观和策略观 不同的时空复杂观 3．手工运算与程序运算的协调策略 【正文】 一、引言 结果提交类问题可算是当今信息学奥林匹克竞赛中最年轻的一类问题，然而IOI连续两年出现此类问题的事实，使其成为主流竞赛中不争的必考题。其中最主要的原因，还是由于此类问题灵活新颖，以及命题人对殊途同归的倡导和对新奇方法的鼓励。 纵观在近两年来主流竞赛中出现的Crack the code，Double Crypt，Birthday party，Tetris，Xor等五道题目，可以说道道精彩，其中不仅充满了巧妙的构思，解题的方法也是百花齐放。但如何才能正确、迅速地完成此类问题，还需要我们深入地思考。本文以上述五道题目为例，分析结果提交类问题的一些特点，介绍一些针对结果提交类问题的特殊方法和技巧。 伴随着结果提交问题的出现，很多方面都发生了深刻的变革： 考察内容的变革 在信息学奥林匹克竞赛发展已较为成熟的今天，仅仅就选手算法和数据结构方面能力作为主要考核标准是远远不够的。结果提交类问题的出现，使得考察的核心还涉及了一些更深层次的东西，如选手的思维能力、创造能力，全局策略、时间策略等等。这些方面的考察在以往题目中同样存在，但似乎都没有结构提交类问题体现得这样充分，考察得如此精妙。 2． 区分度的变革 一道题目对选手的区分度发生了深刻的变革。我们不能仅仅依靠对算法时空复杂度的分析来衡量算法的优劣，还应该综合考虑，衡量我们完成输出文件所花的时间。原因很简单，在以往，1秒钟出解的程序和10秒钟出解的程序，测试的结果一般是前者得分要高不少；而结果提交类问题如果如果结果均正确，一名选手花20分钟，另一名花时2小时，前者则明显胜出，不论二人使用何种方法。 3． 题目的变革 我们后面可以看到，如Birthday Party这样的题目，是否结果提交，完全决定了我们的思考方式，决定了算法。既然命题者将一道题目以结果提交的形式出现，就说明并不希望选手将其视为一道普通题目，而是希望选手大胆使用各种方法，以在最快时间内得到正确结果。倘我们仍以老的思路来看待此类问题，不仅违背了命题者的意愿，浪费了所提供的输入文件，更重要的，我们将浪费更多的时间，甚至得不到理想的方法。结果提交，不是让我们放弃对完美算法的追求，而是鼓励我们站在综合效益的角度去得到结果。 4． 评卷方式的变革 大家都清楚，信息学奥林匹克的评卷是黑箱的，然而以前的黑箱似乎显得相对较狭义。自从结果提交类问题出现以来，黑箱的涵义得到了进一步拓展，更突出了对结果的唯一追求。过程，或者说是程序，更加显得无足轻重了。 我们用一句话来概括解决结果提交类问题的原则就是：永远提醒自己，你所需要的只是在最短的时间内得到正确结果，而不是过程。下面的讨论，也都是围绕此原则展开的。 二、数据分析 数据分析的方法始于结果提交类问题，由于这种方法对选手的观察、思考、猜想及动手实践能力的要求较其他的方法更高，而且灵活多变，所以备受重视。下面以Crack the code和Birthday party为例进行说明。 [例一]Crack the code(Baltic OI 2001) 题目大意： 有五个文件cra*.out，与其对应的，有cra*.txt，已知每一对文件出自同一篇文章。对于每个.out文件，有十个未知的Byte型数…，我们对文件的第i个字符进行下述变换： 如果不是英文字母，则不做变化； 如果为小写字母，则变为大写，转3； 3．如果为大写字母，则对其连续进行次取后继操作。我们视‘A’的后继为’B’，‘B’的后继为’C’…… ‘Z’的后继为’A’。 然后将依次写入对应的cra.in文件。你的任务是根据提供的cra*.in和cra*.txt(都在11KB以内)，得出cra*.out。 分析： 这道题是没有对于任何数据都非常有效的算法的，因为它毕竟是一种比较成形的加密算法。这也是命题者将此题作为结果提交问题的根本原因，只需你要破解给出的数据即可。 本题的解决方法很多，后面我们将要提到。还是先让我们试着用数据分析的方法来考虑此题，来看看数据分析方法的威力。 首