《信息学奥赛试题是如何炼成的？》由会员分享，可在线阅读，更多相关《信息学奥赛试题是如何炼成的？（28页珍藏版）》请在金锄头文库上搜索。
1、OLYMPIAD IN INFORMATICS 信息学奥赛试题是如何炼成的？信息学奥赛试题是如何炼成的？ 合肥信息学辅导站 张金苗合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 引言 引言 ? 想当年国际赛IOI1994 “数塔问题”可是难倒了一 批当年的大牛，现在可是很多人学习动态规划第一 个例子；全国联赛NOIP2006“能量项链”可是全国 赛NOI1995“石子合并”与大学计算机教材上经典 动态规划例子“矩阵相乘”的有机结合。 ? 难道是当年的那些题目太“菜”了吗？当然不是，因 为我们不能用现在的眼光看那些时过境迁的事物， 青少年信息学奥赛也是在不断变化与
2、发展中的，把 握信息学奥赛题目变化与发展规律，就能够站在一 个比较高的高度，解决好较难的问题。合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 ? 同时，把握信息学奥赛题目的变化与发展，也是剖 析、揣摩了出题者的想法和一般思路的过程，这对 于学习者和教学者都是有益的，这又就是另一种角 度的“换位思考”，也是更高层次的学习与教学。 ? 以下通过一系列由浅入深、在各级各类信息学竞赛 中出现的真题，阐述信息学奥林匹克竞赛“变化与 发展”这个永恒主题，通过如下讨论，也不难看 出，信息学奥赛试题是如何演变与炼就的。合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站
3、思维体操 智力风暴 Contents 算法拓展 算法拓展 算法拓展 算法拓展 增加增加决决策多策多样样性 性 增加增加决决策多策多样样性 性 增加控制点 增加控制点 增加控制点 增加控制点 题题目原型 目原型 题题目原型 目原型 ? 增加增加线线程 程 增加增加线线程 程 增加增加数学调数学调料 料 增加增加数学调数学调料料合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 一一、题目原型 、题目原型 ? 题1棋盘路径 ? 有一个n*m的棋盘，左上角为(1,1)，右上角为(n,m)。有一颗棋 子，初始状态为(1,1) ，该棋子只能向右走或者向下走，问改棋子 从(1,
4、1)到(n,m)一共有几条路径？（中国象棋，走边） ? 输入：两个整数n和m ? 输出：一个数，路径总数。 (1,1) (n,m)合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 解题思路解题思路 ? 除左边界和上边界上的点的路径，为其上面点的路径同左 边点路径之和。 ? 递推公式：f(i,j)=f(i1,j)+f(i,j1) ? 边界条件：f(1,1)=1 ? 程序框架 ? f1,1:=1 ? For i:=1 to n do ? for j:=1 to n do ? if i*j1)and(j1)and(aI,j 0) then begin ? if (ai,
5、j1=0)and(ai1,j=0)then ai,j:=0 ? if (ai,j1=0)and(ai1,j0)then inc(ai,j,ai1,j) ? if ai,j10)and(ai1,j=0)then inc(ai,j,ai,j1) ? if (ai,j10)and(ai1,j0)then ? if ai,j1i2 或 j1j2）)合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 ? for i1:=1 to n do ? for j1:=1 to n do ? for i2:=1 to n do ? for j2:=1 to n do ? begin ?
6、 m:=max(si11,j1,i21,j2,si11,j1,i2,j21,si1,j11,i21,j2,si1,j11,i2,j21) ? if (i1=i2) and (j1=j2) then si1,j1,i2,j2:=m+ai1,j1 ? else si1,j1,i2,j2:=m+ai1,j1+ai2,j2 ? end合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 Contents 算法拓展 算法拓展 算法拓展 算法拓展 增加增加决决策多策多样样性 性 增加增加决决策多策多样样性 性 增加控制点 增加控制点 增加控制点 增加控制点 题题目原型 目原型 题
7、题目原型 目原型 ? 增加增加线线程 程 增加增加线线程 程 增加增加数学调数学调料 料 增加增加数学调数学调料料合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 六六、增加、增加“数学佐料数学佐料” ? 题6 方格游戏 ? 现在有一个nn的正方形棋盘，每个格子上面都有一个非负整数。 你拥有一枚棋子，在游戏开始的时候，你的棋子位于左上角的方格 内。游戏的规则很简单：每一次，你可以将棋子向右或向下移动一 格，当棋子到达右下角的方格时，游戏结束。同时，你必须保证你 的棋子通过的路径是花费最小的。一条路径的花费就是这条路径上 所有格子上的数字的乘积最后的连续的0的个数。
8、有一点需要说明 的是，被标记为0的格子是不可以走到的。 ? 输入：第一行为一个整数n（1n1000），表示棋盘的大小。下 面n行每行有n个整数，表示每个格子上的数字（均不超过 1000000）。 ? 我们保证所有的输入数据都至少存在一条左上角到右下角的路径。 ? 输出：一个正整数，表示找到的最优路径的费用。合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 解题思路解题思路 ? 本题有两个亮点： ? （1）“花费”的解读独辟蹊径：一条路径的花费就是这条路径上所 有格子上的数字的乘积最后的连续的0的个数。实际上我们只要统 计路径上所有格子上的数字的乘积有多少个因子10
9、，由于 10=52，因而只需统计计路径上所有格子上的数字有多少个因子 5和2。2和5只有配对成功，才可以产生0，所以最终0的个数是由 最少的2或者5决定了。添加如此“数学佐料”，是不是让“烹饪”后的 “大餐”更有滋味呢？ ? （2）本题需要统计路径上所有格子上的数字有多少个因子5和2， 那么这里“走两遍”同题5的“走两遍”是一回事吗？其实这里是满足 “贪心”原则的，证明如下：假如找到某条路径上因子为5的个数最 少，为S(5)，某条路径上因子为2的个数最少，为S(2)，我们选择 S(2)，因为在产生S(2)这条路径上的S(5)一定大于S(2)；反之亦 然。合肥信息学辅导站 合肥信息学辅导站 合肥信息学辅导站 思维体操 智力风暴 ? 通过以上分析，不难看出一道信息学奥赛试题，是在原型 的基础上通过各种知识综合、能力拓展、包装修饰炼成 的，问题总是在不断变化与发展中延伸的。通过以上启 发，我们也可以将题5变形，题5中0的位置是可以走到的， 如果修改为0的位置不可以走到，问题就变得很有意思了， 控制点不仅第一遍中就存在，而且走过第一遍后，又会产 生新的控制点，这将如何解决呢？留给诸位思考。OLYMPIAD IN INFORMATICS ? http:/ 与我交谈
