《【5A版】信息学奥赛教程指导》由会员分享，可在线阅读，更多相关《【5A版】信息学奥赛教程指导（228页珍藏版）》请在金锄头文库上搜索。
1、上海市控江中学 王建德,云南省 全国奥林匹克信息学联赛辅导,6、2002、2003年分区联赛复赛试题解析,1、高精度运算,2、图的运算,3、搜索算法,4、构造算法,5、动态程序设计,2002、2003年全国分区联赛复赛 试题解析,虽然2002、2003年全国奥林匹克信息学复赛中含许多可“一题多解” 的试题，但如果按照较优算法标准分类的话，大致可分为,特 点,1、凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力，激发学生的创造力，2002、2003年全国奥林匹克信息联赛(NOIP)中学科类的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与学科的依赖关系日益凸
2、现，学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势（按照2005年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。,2、“构造法” 或贪心策略类试题的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质知识是不断推陈出新的。,3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(字串变换回溯法中有字符串处理)，也找不到一个纯粹的数据结构问题（级数求和需要为表达式的计算
3、结果设计合适的数据类型），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；,4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得0分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。,1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺
4、陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）；,启 示,2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（ 爱笛生小学三年级退学、比尔.盖茨大学三年级退学）,学生必须学会从浩如烟海的信息
5、中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构 培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。,3、参与活动的学生应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法
6、、集中编程、互测数据等互相合作的方式完成学习任务）,学生的心理调适： 我掌握的知识仅不过是沧海一粟(进取心)； 固守错误的概念比一无所知更可怕（明智）； 三人之行必有我师（谦虚）； 知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作windows，人类基因工程）（现代意识）；,前提条件：水平相当的同质成员或各有所长（包括数学知识、编程能力和思维方式等解题所需的各种因素）的异质成员是开展合作学习的组织基础；,合作学习的效应： 集思广益容易出好的算法； 群体设计的测试数据相对全面； 在群体活动中能比较客观的反映自己能力情况； 每个学
7、生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性好、 乐于帮助他人，并且善于取他人之长的学生（符文杰、张一飞等）。,4、选手面对从未遇到过的挑战应调整好心态，不要急功近利，要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两次失误，也是砥砺之石，可从中汲取有益的经验和教训。“不是一番寒彻骨，哪得梅花扑鼻香”。,题5、均分纸牌,题6、字串变换,题7、自由落体,题8、 矩形覆盖,题 1、字符近似查找,题2、级数求和,题3、选数,题4、过河卒,9、乒乓球,10、数字游戏,11、栈,12、麦森数,13、神经网络,14、侦探推理,15、加分二叉树,16、传染病控制,第一题：字符近似查找
8、设有n个单词的字典表（1n100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）： i：该单词在字典表中的序号； Ei：在字典表中仅有一个字符不匹配的单词序号； Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号； N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。 输入文件 输入文件名为a.in，文件的格式如下： n（字典表的单词数） n行，每行一个单词 待匹配单词,输出文件 输出文件名a.out，格式如下： i Ei Fi 其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种
9、情况不存在，则输出N。 输入输出样例 输入1: 5 abcde abc asdfasfd abcd aacd abcd,输出1: 4 E5 F1 输入2: 1 a b 输出2: 0 E0 F0 N,我们将字典表中的单词分成3类： 第1类：单词与待匹配单词多或少一个字符，其余字符匹配； 第2类：单词仅有一个字符与待匹配单词不匹配； 第3类：单词与待匹配单词完全匹配； 设 const note :array13 of string=(F,E,)； 匹配情况的标志 var want :string； 待匹配单词 list :array1100 of string； 字典表。其中listi为字典i a
10、ns ：array1100 of integer；单词的类别序列。其中 ansi= ,1、匹配情况的计算 计算两个等长字串中不同字符的个数 function find(a,b:string):integer；输入两个等长字串a,b，计算和返回不同字符的个数 var i,tot:integer； begin tot0； for i1 to length(a) do if aibi then inc(tot)； findtot； end； find ,判别一个字串是否比另一个字串多一个字符（其余字符匹配） 我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另
11、一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。 function check(a,b:string):integer；输入字串a,b。若b能够在a的基础上添加一个字符得到的话，则返回1；否则返回0 var i:integer； begin check0； for i0 to length(a) do begin acopy(a,1,i)+bi+1+copy(a,i+1,255)；在ai后插入bi+1 if a=b 若插入后两串相同，则成功退出 then begin check1；exit；end；then delete(a,i+1,1)； 删去a中的插入字符 e
12、nd；for end；check,2、计算字典表中的每一类单词 首先，我们依次计算每一个单词的类别序号 在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为3；若两串仅有一个字符不同，则单词i的类别记为2； 若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0； 然后根据ans序列在字典表中依次搜索类别3类别1的单词，输出对应的单词序号。如果在字典表中不存在上述3种类别的单词，则输出N。 fillchar(ans,sizeof(ans),0)； 单词的类别序列初始化 for i1 to n do begin 对字典中的每个单词进行分类 i
13、f length(listi)=length(want) 若单词i与待匹配单词等长 then begin kfind(listi,want)；计算单词i与待匹配单词的不同字符个数 if k=0 then ansi 3； 记下类别序号 if k=1 then ansi 2； end；then,若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0 if length(listi)+1=length(want) then ansi check(listi,want)； if length(listi)=length(want)+1 then ansi ch
14、eck(want,listi)； end；for havefalse； 匹配情况存在的标志初始化 for i3 downto 1 do begin 依次输出每一类别的单词在字典表最先出现的序号 k0； for j1 to n do if ansj=i then begin kj；break；end；then havehave or (k0)； writeln(notei,k)； end；for,第二题：级数求和 已知：Sn=1+1/2+1/3+.+1/n。显然当n.非常大的时候，Sn可大于任何一个整数K。现给出一个整数K（1K15），要求计算出一个最小的n，使得SnK。 输入 键盘输入 k 输
15、出 屏幕输出 n 输入输出样例 输入: 1 输出: 2,算法分析,该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不下。但未必非高精度运算不可。只要启动浮点数运算（$n+），将项数设为extended类型，便可以得出正确解。 $n+ 启动浮点数运算 var s,b,k:extended； 数列的和、项数、最接近sn(大于sn)的整数值 begin s0； 数列的和初始化 b0； 项数初始化 readln(k)； 读最接近sn(大于sn)的整数值k while s=k do 若目前数列的和小于k，则项数b+1，计算sb begin bb+1； ss+1/b； end；while 输出项数round(b)； end.main,第三题：选数,已知n个整数 x1,x2,xn, 以及一个整数k (kn)。从 n 个整数中任选k个整数组合相加，可分别得到一系列的和。例如当 n=4, k=3，4个整
