VIP会员

0 前言 4 1 骗分——与复杂度的较量 6 2 参赛准备 7 2.1 心态——成就考试的前提 7 2.2 知己知彼， 百战不殆 8 2.2.1 单题的命制 8 2.2.2 测试数据的命制 10 2.2.3 套题的命制 11 2.3 应该学习的内容 12 2.4 找准位置， 水滴石穿 14 2.5 临阵磨枪， 不快也光 16 2.6 玩自己的养成游戏 17 3 复杂度常数优化 17 3.1 时间复杂度常数优化的意义 17 3.2 基本运算的速度 18 3.3 位运算的速度 20 3.4 数组运算的速度 23 3.5 实数运算的速度 24 1 博杰学习网， 官方顶级域名为 http://boj.pp.ru， 是本文作者的个人网站， 主要发表各学科竞赛（ 主要是数 学、 信息学） 的信息动态、 竞赛试题解答、 学习资料、 个人研究成果， 趣味科学， 个人随笔文章， 班级事 务， 是石家庄二中首个学科竞赛资料库、 河北省信息学代表队资料库， 欢迎访问。 旗下网站有数之理论坛 http://boj.5d6d.com/， 属于数学、 信息学趣题、 文章、 资料交流的场所， 其中大量语 言精辟、 分析透彻的教程文章和趣味十足、 深入本质的趣题值得读者一看。 2 什么是信息学竞赛？ 笔者认为， 信息学竞赛就是考察在有电脑的情况下“ 如何使用计算机代替人脑的工 作， 使得人的工作效率更高”， 就是考察应用计算机这个高效工具解决实际问题的能力。 3 本文所说的“ 骗分” 不是作弊， 而是尽可能多得分的应试技巧， 请不要误解。 NOI2009 河北省代表队论文 石家庄二中 李博杰 骗分导论·信息学竞赛 2 3.6 程序书写习惯 25 3.7 小算法 大优化 30 3.8 空间复杂度优化 33 3.9 降低编程复杂度 34 4 数学分析与猜想 41 4.1 数学与信息学 41 4.2 计算数学基础 45 4.2.1 素数判断算法 45 4.2.2 欧几里德算法 47 4.2.3 函数类算法 48 4.3 组合计数 50 4.4 计算几何算法 54 4.5 博弈论中的数学 61 4.5.1 纳什均衡 61 4.5.2 数学分析的应用 63 4.5.3 SG 定理与组合游戏 67 4.6 概率 68 4.7 组合构造 70 5 非完美算法 73 5.1 贪心法 74 5.2 随机法 78 5.3 试验法 78 5.4 调整法 78 5.5 模拟法 79 6 搜索算法 79 6.1 可行性剪枝 79 6.2 最优性剪枝 87 6.3 局部贪心、 动态规划 91 6.4 启发式搜索 92 7 骗分攻略 92 7.1 数学题——观察 92 7.2 小数据——交表 96 7.3 部分分——卡时 96 7.4 提交答案题——枚举 96 7.5 全面地考虑问题 98 7.6 设计获胜策略 103 8 调试程序 108 8.1 从静态查错开始 108 8.1.1 编译错误 108 8.1.2 运行错误 109 8.1.3 变量冲突 110 8.1.4 张冠李戴 115 8.1.5 正反对调 115 8.1.6 就差一点 116 NOI2009 河北省代表队论文 石家庄二中 李博杰 骗分导论·信息学竞赛 3 8.1.7 逻辑混乱 117 8.1.8 边界溢出 117 8.1.9 格式错误 117 8.1.10 忽略特例 118 8.1.11 分类失误 118 8.1.12 算法错误 118 8.2 善用输出语句 118 8.3 设计测试数据 122 8.4 考试有风险， 答题需谨慎 122 9 实战演习 124 9.1 2008 试题回顾与分析 124 9.1.1 2008 主要赛事题目与分类 124 9.1.2 题目方法与分类比例 126 9.1.3 竞赛规则 126 9.2 NOIP 模拟赛（ 一） 127 9.3 NOIP 模拟赛（ 二） 141 9.4 NOIP 模拟赛（ 三） 154 9.5 NOIP 模拟赛（ 四） 169 9.6 NOIP2008 183 9.6.1 笨小猴 184 9.6.2 火柴棒等式 186 9.6.3 传纸条 194 9.6.4 双栈排序 201 9.6.5 NOIP 小结 209 9.7 NOI2008 209 9.7.1 假面舞会 209 9.7.2 设计路线 211 9.7.3 志愿者招募 212 9.7.4 奥运物流 213 9.7.5 糖果雨 214 9.7.6 赛程安排 217 9.8 WC2009 219 9.8.1 最短路问题 219 9.8.2 语音识别 220 9.8.3 优化设计 223 9.9 CTSC2008 225 9.9.1 三角形的教学楼 225 9.9.2 祭祀 227 9.9.3 奥运抽奖 229 9.9.4 图腾 231 9.9.5 网络管理 232 9.9.6 唯美村落 234 9.10 IOI2008 236 10 骗分的实质 236 NOI2009 河北省代表队论文 石家庄二中 李博杰 骗分导论·信息学竞赛 4 10.1 Keep it simple and stupid 236 10.2 告别骗分 237 参考文献 238 感谢 238 后记——程序人生 238