学科竞赛骗分导论
/ 11 min read
前言
本文是《学科竞赛骗分导论》系列文章之二——《骗分导论·信息学竞赛》，同时是NOI2009 河北省代表队论文、博杰学习网 2009 研究发展规划重要成果。笔者在《骗分导论·数学竞赛》第三版（81页）受到广泛好评之后，又受到“我是智障”大牛的《骗分导论》启发，决定再写一篇有关信息学竞赛尽可能多得分的方案。
内容
取同样的题目《骗分导论》，并无抄袭之意，只是为了更加具体的阐明“骗分”的方案，为同名文章增添理论色彩、方法色彩，更加具体的阐述“骗分”理论，使“骗分”真正成为信息学竞赛中的有效策略。
笔者在 NOIP2008 中取得较好的发挥，以 330 分进入河北省信息学代表队，又参加了WC2009 冬令营，取得了 101 分的较好成绩，但真正实力，尤其是高级算法的实力并不强，在欣喜之余，应该总结一些有关“骗分”的技巧，为 OI 事业的长足发展提供动力。在我学习信息学竞赛的过程中，曾经多方寻找相关资料，而每份资料在介绍时都不能面面俱到，甚至出现两种资料所述观点相反的情况，给我们的学习带来很大不便。据我所知，本文是首篇具体、全面总结信息学竞赛技巧的文章，可以称得上是“第一个吃螃蟹的人”。希望本文的发表能为更多具有总结性质的信息学竞赛资料的出现起到抛砖引玉的作用。正是因为笔者写作本文的动机是为广大信息学竞赛选手整理、提供一份较为全面的信息学竞赛得分技巧，笔者决定开放本文的版权，任何人都可以修改、添加本文的部分并发布，也可以在注明出处的要求下任意引用本文的语段、程序。
正是因为本文的总结性质，笔者不能保证内容的原创性。如果把《骗分导论》比作是一束美丽的鲜花，那么其中的朵朵鲜花都是各位大牛辛勤努力的成果，本文仅是做了一个筛选鲜花、制作花瓶并将花插入花瓶的工作。
本文的长度有目共睹，为了普及、易懂，拉近与读者的距离，况且不是正式出版物，上面也许有一些废话，或十分简单的试题，请各位大牛原谅，并可以选择性阅读。本文参考了众多大牛的论文、高级教练的书籍，并摘录了一些语段和程序，在此表示衷心感谢。事实上，笔者在写这篇文章时，感到比《骗分导论·数学竞赛》要轻松一些。因为数学竞赛是要推理过程的，严格的证明始终是困难的；而信息学竞赛只需要结果，而且有“部分分”，这些“黑箱测试”的特点都给“骗分”提供了极大的方便。
本文以竞赛心态的调整为开端，以常数时间优化为基础，以数学分析与猜想为指导思想，以非完美算法为主要策略，以搜索为最后的万能策略，讲述信息学竞赛中“骗分”的若干策略，再进行实战演习，说明“骗分”的强大功力。
值得注意的是，本文将不介绍“我是智障”《骗分导论》中“直接输出结果”的方法，因为在近几年的 OI 竞赛中，这种方法很难得分，也不能体现信息学竞赛的考察本质。“会做才是硬道理”，本文的多数手段事实上不是“骗分”，而是如何采用稍微差一些的算法得到较高的分数。通过阅读本文，相信读者不仅能学到“骗分”的有关技巧，更能得到“做题”的一些启示。
如果说“装备精良兵器，精通诸子兵法，部署优势兵力1”是战争取胜的三要素，那么在信息学竞赛中，熟练的编程就是精良的兵器，高效的算法就是诸子兵法，巧妙的策略就是优势兵力。
本文采用了“注释”的写作风格，将大量用于定义、解释、补充说明的语句放在每页下方的注释中，并且对后文要提到的内容在注释中先给出提要，方便理解。这样可以使文章逻辑更加严谨，中心更加突出。需要注意的是，“注释”不等于“不重要”，很多文章中“无地可容”的思想和一些细节方面的看法往往包含在注释中。希望读者习惯这种方式。
本文中出现了很多代码，原因主要有二：首先，本文不是正式出版物，篇幅长短并无大碍，希望读者不要为了节省宝贵的磁盘空间而在意 PDF 的大小；更重要的是，本文是以介绍竞赛策略为核心的信息学文章，需要对编写代码、调试代码的细节进行讲解，而不是像其他文章一样只给出解题的思路和算法。读者如果对这些代码感到厌烦，可以略过它们。为了充分利用网络资源，《骗分导论》依托数之理论坛开通了官方网站2，发布本文的最新版本，有关试题、源程序、测试数据，配套学习资料等，也方便广大读者朋友对本文提出意见建议，与作者对话，讨论本文中涉及的试题，交流“骗分”的思想方法。
由于“骗分”是一个本来不正规的方法，也是多种思想综合的结果，本文强行将各种方法分成章节，未必符合人类的思维特点，也势必造成大量重复，包括事例重复、论证重复，请读者多多包涵。
由于笔者水平有限，错误、疏漏在所难免，希望读者指正，并为《骗分导论》的再版提出意见建议。我们对您的支持表示感谢。
NOIP 取消保送的传言前一段时间沸沸扬扬。竞赛回归自然，确实是 OI 应有的取向。学习 OI，不仅是为了得奖、保送，更是为了学习知识，掌握技能，服务于其他学科的学习和今后的发展。事实证明，学习信息学竞赛的学生在其他学科，尤其是数学上往往有逻辑思维强、表达严谨、知识面广等优点。目前国产软件的普及仍然远不如国外市场的垄断，这也对我国的信息安全构成了巨大威胁。为了实现民族独立自主发展，就必须有自己的信息产业，有自己的独立知识产权。国内教育界对信息学的重视程度也远远不够，这些难题都需要我们这一代 OIER 做开路先锋。本文使用永中集成 Office 编辑、制作，并在红旗 Redflag Linux 环境下发表，也是为了支持民族软件，振兴民族产业。我们看到，国产软件无法获得普及的重要原因不是技术低、水平差，而是众多用户对民族软件不了解，还没有使用就认为低人一等。只要我们改变对民族软件的不公平认识，共同反对外国公司的垄断，我们民族软件产业的振兴，就为期不远了。学习 OI，为民族信息学产业的发展，甚至人类信息学事业的进步贡献力量。我们希望这不是一句空话，而能够让每个人身体力行。如果这个宏伟目标能够成为现实，或者本文能为一批 OIER 走上民族产业振兴之路做出一点积极的影响，笔者为撰写《骗分导论》花费的巨大精力，也就在所不惜、有所充实了。
衷心祝愿各位读者在《骗分导论》的引导下，在 OI 之路上越走越远，越走越成功。