《信息学奥赛教程指导PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛教程指导PPT讲稿.ppt（227页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息学奥赛教程指导第1页，共227页，编辑于2022年，星期五6 6、20022002、20032003年年分分区区联联赛赛复复赛赛试试题题解析解析1 1、高精度运算、高精度运算2 2、图的运算、图的运算3 3、搜索算法、搜索算法4 4、构造算法、构造算法5 5、动态程序设计、动态程序设计第2页，共227页，编辑于2022年，星期五2002、2003年全国分区联赛复赛试题解析 第3页，共227页，编辑于2022年，星期五题题型型题题目目与课内知识相关与课内知识相关自自由由落落体体、级级数数求求和和、乒乒乓乓球球、麦森数麦森数 字符串处理字符串处理字符近似查找字符近似查找贪心法贪心法均分纸牌、传
2、染病控制均分纸牌、传染病控制 回溯法回溯法选选数数、字字串串变变换换、栈栈、神神经经网网络络、侦探推理侦探推理 动态程序设计方法动态程序设计方法过河卒、数字游戏、加分二叉树过河卒、数字游戏、加分二叉树 几何计算几何计算矩形覆盖矩形覆盖 虽然虽然2002、2003年全国奥林匹克信息学复赛中含许多可年全国奥林匹克信息学复赛中含许多可“一题多解一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为的试题，但如果按照较优算法标准分类的话，大致可分为 第4页，共227页，编辑于2022年，星期五特特特特 点点点点 1、凸现信息学知识和学科知识整合的趋势凸现信息学知识和学科知识整合的趋势。为为了考核
3、学生运用学科知识的能力，激发学生的创造力，了考核学生运用学科知识的能力，激发学生的创造力，2002、2003年全国奥林匹克信息联赛年全国奥林匹克信息联赛(NOIP)中学中学科类的试题增加，并且首次出现了计算几何类的试科类的试题增加，并且首次出现了计算几何类的试题题(矩形覆盖矩形覆盖矩形覆盖矩形覆盖)。这说明信息学与学科的依赖关系日益凸现，。这说明信息学与学科的依赖关系日益凸现，学科基础好、尤其是数学素质好的人虽然不一定会编学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈
4、来愈多的人的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势信息学联赛活动发展的一个大趋势（按照（按照2005年国家教改方案，数年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。学教材增加算法内容，信息科技教材掺入语言知识）。2、“构造法构造法”或贪心策略类试题的引入，或贪心策略类试题的引入，使得使得算法知识的不确定性和不稳定性增加。算法知识的不确定性和不稳定性增加。这正体现了科学的本质这正体现了科学的本质知识是不断推陈知识是不断推陈出新的。出新的。第5页，共2
5、27页，编辑于2022年，星期五3、试题的综合性增加试题的综合性增加，并不一定随知识，并不一定随知识的分类而发生变化，有时几乎找不到一个的分类而发生变化，有时几乎找不到一个单一的经典算法单一的经典算法(字串变换字串变换字串变换字串变换回溯法中有字符串处理回溯法中有字符串处理回溯法中有字符串处理回溯法中有字符串处理)，也找不到一个纯粹的数据结构问题也找不到一个纯粹的数据结构问题（级数求和（级数求和（级数求和（级数求和需要为表达式的计算结果设计合适的数据类型）需要为表达式的计算结果设计合适的数据类型）需要为表达式的计算结果设计合适的数据类型）需要为表达式的计算结果设计合适的数据类型），关键是，关键
6、是你从哪个角度去分析，也就是说能不能综你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；手的综合素质愈高，得胜的机率愈大；4、经常面对着不知道算法的试题，面经常面对着不知道算法的试题，面对着谁都不知如何处置的情境对着谁都不知如何处置的情境（经常出现许多（经常出现许多选手在一题中得选手在一题中得0 0分、优秀选手表现失常的情况分、优秀选手表现失常的情况），因此必因此必须使学生正确地理解问题、深入问题须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯的空间并形成解决问题的意识、习惯和能力。能不
7、能和能力。能不能创造性地应答没有遇创造性地应答没有遇到过的挑战到过的挑战，成为培训的基本要求和成为培训的基本要求和目标。目标。第6页，共227页，编辑于2022年，星期五1 1、培培养养问问题题意意识识和和问问题题能能力力。创创造造始始于于问问题题。“有有了了问问题题才才会会思思考考，有有了了思思考考才才有有解解决决问问题题的的方方法法，才才有有找找到到独独立立思思路路的的可可能能（陶陶行行知知）”。有有问问题题虽虽然然不不一一定定有有创创造造，但但没没有有问问题题一一定定没没有有创创造造（想想一一想想当当前前的的解解法法有有没没有有缺缺陷陷，有有没没有有更更好好的的算算法法，它它与与哪哪些些
8、问问题题有有联联系系，与与哪哪些些知知识识相相关关联联，还还可可以以拓拓延延出出哪哪些些问问题题，要要解解决决这这些些问问题题还还需需要要哪些知识）哪些知识）；启启启启示示示示2、处处理理好好前前沿沿性性与与基基础础性性、直直线线培培训训和和散散点点培培训训、循循序序渐渐进进与与跳跳跃跃式式的的矛矛盾盾。如如果果恪恪守守按按部部就就班班的的培培训训程程序序，不不谋谋求求跳跳跃跃式式学学习习，将将离离全全国国和和国国际际奥奥林林匹匹克克信信息息学学活活动动的的前前沿沿、离离世世界界程程序序设设计计知知识识的的前前沿沿愈愈来来愈愈远远。因因此此在在进进行行基基础础课课程程学学习习的的同同时时，必必
9、须须有有追追逐逐前前沿沿的的选选择择性性学学习习。这这里里，有有时时候候心心理理的的障障碍碍比比科科学学上上的的障障碍碍更更难难跨跨越越，敢敢不不敢敢的的问问题题比比能能不不能能的的问问题题更更突突出出。其其实实在在学学习习中中或或多多或或少少地地都都有有必必要要的的跳跳跃跃，不不少少人人还还能能够够实实现现比比较较大的跳跃大的跳跃（爱笛生小学三年级退学、比尔爱笛生小学三年级退学、比尔.盖茨大学三年级退学）盖茨大学三年级退学）第7页，共227页，编辑于2022年，星期五v学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构v培训内容要有
10、选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对对基基础础的的理理解解是是主主观观的的选选择择。例例如如中中国国、美美国国和和俄俄罗罗斯斯的的理理科科教教材材大大不不相相同同，有有的的同同年年级级同同学学科科的的教教材材相相差差三三分分之之二二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。3、参参与与活活动动的的学学生生应应由由竞竞争争关关系系和和独独立立关关系系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功
11、）转转向向合合作作学学习习的的关关系系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）第8页，共227页，编辑于2022年，星期五学生的心理调适：学生的心理调适：n我掌握的知识仅不过是沧海一粟我掌握的知识仅不过是沧海一粟(进取心进取心)；n固守错误的概念比一无所知更可怕固守错误的概念比一无所知更可怕（明智）（明智）；n三人之行必有我师三人之行必有我师（谦虚）（谦虚）；n知识生产社会化条件下人的基本素质之一是知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作科学家进行长期甚至
12、跨国的合作，例如制作windows，人类基因工程），人类基因工程）（现代意识）（现代意识）；前提条件：前提条件：水平相当的同质成员水平相当的同质成员或各有所长（包括数学知识、编程或各有所长（包括数学知识、编程能力和思维方式等解题所需的各种能力和思维方式等解题所需的各种因素）的异质成员是开展合作学习因素）的异质成员是开展合作学习的组织基础；的组织基础；合作学习的效应：合作学习的效应：n集思广益容易出好的算法；集思广益容易出好的算法；n群体设计的测试数据相对全面；群体设计的测试数据相对全面；n在群体活动中能比较客观的反映自己能力在群体活动中能比较客观的反映自己能力情况；情况；n每个学生在付出与给予
13、中可提高合作精每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性神和编程能力，成功者往往是那些相容性好、好、乐于帮助他人，并且善于取他人之长乐于帮助他人，并且善于取他人之长的学生的学生（符文杰、张一飞等）。（符文杰、张一飞等）。第9页，共227页，编辑于2022年，星期五4、选选手手面面对对从从未未遇遇到到过过的的挑挑战战应应调调整整好好心心态态，不不要要急急功功近近利利，要要只只管管耕耕耘耘、不不问问收收获获、潜潜心心钻钻研研、其其乐乐无无穷穷。那那怕怕是是一一两两次次失失误误，也也是是砥砥砺砺之之石石，可可从从中中汲汲取取有有益益的的经经验验和和教教训训。“不不是是一一
14、番番寒寒彻彻骨骨，哪哪得得梅梅花花扑鼻香扑鼻香”。第10页，共227页，编辑于2022年，星期五题题5、均分纸牌、均分纸牌题题6、字串变换、字串变换题题7、自由落体、自由落体题题8、矩形覆盖矩形覆盖题题1、字符近似查找、字符近似查找题题2、级数求和、级数求和题题3、选数、选数题题4、过河卒、过河卒9、乒乓球、乒乓球10、数字游戏、数字游戏11、栈、栈12、麦森数、麦森数13、神经网络、神经网络14、侦探推理、侦探推理15、加分二叉树、加分二叉树16、传染病控制、传染病控制第11页，共227页，编辑于2022年，星期五第一题：字符近似查找第一题：字符近似查找设有n个单词的字典表（1n100）。计
15、算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）：i：该单词在字典表中的序号；Ei：在字典表中仅有一个字符不匹配的单词序号；Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号；N：其他情况当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件输入文件输入文件名为a.in，文件的格式如下：n（字典表的单词数）n行，每行一个单词待匹配单词第12页，共227页，编辑于2022年，星期五输出文件输出文件 输出文件名a.out，格式如下：i Ei Fi其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情
16、况不存在，则输出N。输入输出样例输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出输出1:4E5F1输入输入2:1ab输出输出2:0E0F0N第13页，共227页，编辑于2022年，星期五我们将字典表中的单词分成3类：第1类：单词与待匹配单词多或少一个字符，其余字符匹配；第2类：单词仅有一个字符与待匹配单词不匹配；第3类：单词与待匹配单词完全匹配；设constnote:array1.3ofstring=(F,E,)；匹配情况的标志varwant:string；待匹配单词list:array1.100ofstring；字典表。其中listi为字典ians：arra
17、y1.100ofinteger；单词的类别序列。其中ansi=第14页，共227页，编辑于2022年，星期五1、匹配情况的计算、匹配情况的计算计算两个等长字串中不同字符的个数计算两个等长字串中不同字符的个数function find(a,b:string):integer；输入两个等长字串a,b，计算和返回不同字符的个数vari,tot:integer；begintot0；for i1 to length(a)do if aibi then inc(tot)；findtot；end；find 第15页，共227页，编辑于2022年，星期五n判别一个字串是否比另一个字串多一个字符（其余字符匹配）
18、判别一个字串是否比另一个字串多一个字符（其余字符匹配）n我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。nfunction function check(a,b:string):integercheck(a,b:string):integer；输输入入字字串串a,ba,b。若若b b能能够够在在a a的的基基础础上上添添加加一一个个字字符得到的话，则返回符得到的话，则返回1 1；否则返回；否则返回00nvarvari:integeri:integer；nbeginbegin
19、ncheck0check0；nfor i0 to length(a)do begin for i0 to length(a)do begin nacopy(a,1,i)+bi+1+copy(a,i+1,255)acopy(a,1,i)+bi+1+copy(a,i+1,255)；在在aiai后插入后插入bi+1bi+1nif a=b if a=b 若插入后两串相同，则成功退出若插入后两串相同，则成功退出 nthen begin check1then begin check1；exitexit；endend；thenthenndelete(a,i+1,1)delete(a,i+1,1)；删去删去a
20、 a中的插入字符中的插入字符 nendend；forfornendend；checkcheckn第16页，共227页，编辑于2022年，星期五2 2、计算字典表中的每一类单词、计算字典表中的每一类单词首先，我们依次计算每一个单词的类别序号在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为3；若两串仅有一个字符不同，则单词i的类别记为2；若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0；然后根据ans序列在字典表中依次搜索类别3类别1的单词，输出对应的单词序号。如果在字典表中不存在上述3种类别的单词，则输出N。fillchar(ans
21、,sizeof(ans),0)；单词的类别序列初始化for i1 to n do begin 对字典中的每个单词进行分类 if 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第17页，共227页，编辑于2022年，星期五若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0iflength(listi)+1=length(
22、want)thenansicheck(listi,want)；iflength(listi)=length(want)+1thenansicheck(want,listi)；end；forhavefalse；匹配情况存在的标志初始化fori3downto1dobegin依次输出每一类别的单词在字典表最先出现的序号k0；forj1tondoifansj=ithenbeginkj；break；end；thenhavehaveor(k0)；writeln(notei,k)；end；for第18页，共227页，编辑于2022年，星期五 第二题：级数求和第二题：级数求和 已知：Sn=1+1/2+1/3+
23、.+1/n。显然当n.非常大的时候，Sn可大于任何一个整数K。现给出一个整数K（1K15），要求计算出一个最小的n，使得SnK。输入输入 键盘输入k输出输出 屏幕输出n输入输出样例输入输出样例输入:1输出:2第19页，共227页，编辑于2022年，星期五算法分析算法分析 该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不下。但未必非高精度运算不可。只要启动浮点数运算（$n+），将项数设为extended类型，便可以得出正确解。$n+启动浮点数运算vars,b,k:extended；数列的和、项数、最接近sn(大
24、于sn)的整数值begins0；数列的和初始化b0；项数初始化readln(k)；读最接近sn(大于sn)的整数值kwhile s=k do 若目前数列的和小于k，则项数b+1，计算sb beginbb+1；ss+1/b；end；while 输出项数round(b)；end.main第20页，共227页，编辑于2022年，星期五第三题：选数第三题：选数 已知n个整数 x1,x2,.xn,以及一个整数k(kn)。从 n 个整数中任选k个整数组合相加，可分别得到一系列的和。例如当 n=4,k=3，4个整数分别为3，7，12，19 时，可得全部的组合为：3+7+12=22 3+7+19=29 7+1
25、2+19=38 3+12+19=34。现在，要求你计算出和为素数的组合数有多少种。例如上例，只有一种组合的和为素数：（3+7+19=29）。第21页，共227页，编辑于2022年，星期五输入输入 输入文件名为c.in。文件格式n,k（1n20，ka，则说明a不可能分解出比primei大的素数了，a本身为素数。由于primei表的最大素数接近10000，其平方远大于xi的上限5000000，因此是一个比较可行的方法：function check(a:longint):boolean；判断a是否是素数beginchecktrue；素数标志初始化for i1 to tot do begin 搜索素数
26、表 if primei*primeia then exit；若超出搜索范围的上限，则说明a是素数，返回true if a mod primei=0 then begin checkfalse；exit；end；thenend；forend；check 第24页，共227页，编辑于2022年，星期五2 2、递归搜索方案数、递归搜索方案数 由于数列是随机和无序的，因此只能通过搜索的办法求解。设 状态(left,now,all)：目前组合为all，还需要从xnowxn中选出left个数；约束条件(leftn-now+1)：xnowxn中数的个数大于等于left；边 界 条 件（(left=0)and
27、(now=n+1)）和 目 标 状 态（check(all)=true）：从x1xn中选出k个数为边界。在这种情况下，若k个数的和为素数，则满足条件的种数+1。到达边界后，应回溯；搜索范围为两种选择：当前组合不选xnow,递归计算子状态(left,now+1,all)；在还有数需要选的情况下（left0），xnow选入组合，递归计算子状态(left-1,now+1,all+listnow)；由此得出子程序第25页，共227页，编辑于2022年，星期五Procedure solve(left,now,all:longint)；递归计算选数情况beginif(leftn-now+1)then ex
28、it；若xnowxn中不足left个数，则回溯 if(left=0)and(now=n+1)若从x1xn中选出了k个数 then begin if check(all)then inc(ans)；若k个数的和为素数，则满足条件的种数+1 exit；回溯 end；then solve(left,now+1,all)；当前组合不选xnow,递归计算子状态if left0 在还有数需要选的情况下，xnow选入组合，递归计算子状态 then solve(left-1,now+1,all+listnow)；end；solve显然，递归调用solve(k,1,0)后得出的ans即为问题的解。第26页，共2
29、27页，编辑于2022年，星期五过河卒过河卒如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。第27页，共227页，编辑于2022年，星期五 同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2.P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A 点能够到达B点的路径的条数。输输 入：入：键盘输入B点的坐标(n,m)以
30、及对方马的坐标（X，Y）输输 出：出：屏幕输出一个整数（路径的条数）。输入输出样例：输入输出样例：输入：3 3 2 2 输出：0第28页，共227页，编辑于2022年，星期五1 1、计算对方马的控制点、计算对方马的控制点 按按照照题题意意，对对方方的的马马所所在在的的点点和和所所有有跳跳跃跃一一步步可可达达的的点点称称为为对对方方马马的的控控制制点点，卒卒不不能能通通过过对对方方马马的的控控制制点点。在在卒卒出出发发之之前前，必必须须计计算算对对方方马马的的所所有有控控制制点点。显显然然，若若（0，0）或（）或（n,m）为控制点，则输出路径数为）为控制点，则输出路径数为0。设。设constco
31、nst move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)；movemovekk，1.21.2为马沿为马沿k k方向跳跃一步的水平增量和垂直增量方向跳跃一步的水平增量和垂直增量 varvar list:array-1.20,-1.20 list:array-1.20,-1.20 of of compcomp；路路径径数数
32、序序列列，其其中中listi,jlisti,j为为卒卒从从(0,0)(0,0)到到(i,j)(i,j)的的路路径径数数 can:array0.20,0.20 of boolean can:array0.20,0.20 of boolean；点点(i,j)(i,j)允许卒通行的标志允许卒通行的标志 马的初始位置为（马的初始位置为（x,yx,y）。我们按照下述方式计算）。我们按照下述方式计算cancan序列：序列：canx,y falsecanx,y false；对方马所在的点为控制点对方马所在的点为控制点 for i1 to 8 do beginfor i1 to 8 do begin从（从（x
33、 x，y y）出发，沿）出发，沿8 8个跳马方向计算控制点个跳马方向计算控制点 jx+movei,1 jx+movei,1；计算计算i i方向的跳马位置方向的跳马位置(j(j，k)k)ky+movei,2 ky+movei,2；if(j=0)and(k=0)and(j=n)and(k=0)and(k=0)and(j=n)and(k=m)若（若（j,kj,k）在界内，则为控制点）在界内，则为控制点 then canj,k false then canj,k false；endend；forforif(not can0,0)or(not cann,m)if(not can0,0)or(not ca
34、nn,m)若卒的起点和终点为控制点，则输出路径数若卒的起点和终点为控制点，则输出路径数00 then writeln(0)then writeln(0)else begin else begin 计算和输出卒从（计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径数）点的路径数listn,mlistn,m；endend；elseelse第29页，共227页，编辑于2022年，星期五2 2、计算和输出卒从（计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数 我我们们按按照照由由上上而而下下、由由左左而而右右的的顺顺序序，将将卒卒可可能能到到达达
35、的的每每一一个个位位置置（i,ji,j）(0in(0in，0jm)0jm)设为阶段设为阶段,显然这样做，可以取消对状态的枚举。显然这样做，可以取消对状态的枚举。首首先先，将将卒卒的的出出发发点点（0 0，0 0）的的路路径径数数设设为为1 1（list0,01list0,01），并并将将该该位位置置设设为为控控制制点点（can0,0 can0,0 falsfals）。然然后后从从（0 0，0 0）出出发发，按按照照由由上上而而下下、由由左左而而右右的的顺顺序序计计算算卒卒经经过过每每一一个个可可行行点点的的路路径径数数。若若（i i，j j）为为可可行行点点，则则卒卒可可由由上上侧侧的的（i-
36、1,ji-1,j）和和左左侧侧的的（i,j-1i,j-1）进进入入该该点点。将将这这两两点点的的路路径径数数加加起起来来，即即为为从从（0 0，0 0）走到（走到（i i，j j）的路径数，即）的路径数，即 listi,j=listi-1,j+listi,j-1listi,j=listi-1,j+listi,j-1（i i，j j）非控制点）非控制点依次类推，最后得出的依次类推，最后得出的listn,mlistn,m即为问题的解。由此得出算法：即为问题的解。由此得出算法：fillchar(list,sizeof(list),0)fillchar(list,sizeof(list),0)；路径数
37、序列初始化路径数序列初始化 list0,01 list0,01；卒从（卒从（0 0，0 0）出发的路径数为）出发的路径数为1 1，该位置不再允许卒通行，该位置不再允许卒通行 can0,0 false can0,0 false；for for i0 i0 to to n n dodo对对于于每每个个可可行行点点,小小兵兵要要么么从从左左侧侧、要要么么从从上上方方走走到到,由由此此计计算算从从(0,0)(0,0)到到(i,j)(i,j)的路径数的路径数 for j0 to m do if cani,j for j0 to m do if cani,j then listi,jlisti-1,j+l
38、isti,j-1 then listi,jlisti-1,j+listi,j-1；输出卒从（输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数listn,mlistn,m；第30页，共227页，编辑于2022年，星期五题一题一均分纸牌均分纸牌问问题题描描述述有N堆纸牌，编号分别为1，2，.N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在在编编号号为为1 1堆堆上上取取的的纸纸牌牌，只只能能移移到到编编号号为为2 2的的堆堆上上；在在编编号号为为N N的的堆堆上上取取的的纸纸牌牌，只只能能移移到到编编号号为为N-1N-
39、1的的堆堆上上；其其他他堆堆上上取取的的纸纸牌牌，可可以以移移到到相相邻邻左左边边或或右右边边的的堆堆上上。现在要求找出一种移动方法，用用最最少少的的移移动动次次数数使使每每堆堆上上纸纸牌牌数数都都一一样样多多。例如N=4，4堆纸牌数分别为：98176移动3次可达到目的：从取4张牌放到（981310）从取3张牌放到（9111010）从取1张牌放到（10101010）。输输入入：N（N堆纸牌，1N100）A1，A2，.An(N堆纸牌，每堆纸牌初始数，1Ai10000)输输出出：所有堆均达到相等时的最少移动次数。输入输出样例输入输出样例第31页，共227页，编辑于2022年，星期五输入：输入：49
40、8176输出：输出：3设list为纸牌序列，其中listi为第i堆纸牌的张数（1in），ave为均分后每堆纸牌的张数，即；ans为最少移动次数。我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数listi超出平均值，则移动一次(ans+1)，将超出部分留给下一堆，既第i+1堆纸牌的张数增加listi-ave；若第i堆纸牌的张数listi少于平均值，则移动一次(ans+1)，由下一堆补充不足部分，既第i+1堆纸牌的张数减少ave-listi；右邻堆取的牌第32页，共227页，编辑于2022年，星期五问题是，在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(listi
41、+1-(ave-listi)xuud-yy-yzA.out文件：文件：3第35页，共227页，编辑于2022年，星期五1 1、分析变换规则、分析变换规则、分析变换规则、分析变换规则设规则序列为rule，其中第i条规则为rulei，1rulei，2；当前串为now，其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的，因此设j为now的指针，即从now的第j个字符开始匹配rulei,1。now适用第i条规则的条件是vnow中的子串被第i条规则替换后的长度小于255，即length(now)+length(rulei,2)-length(rulei,1)255vrulei,1是now的
42、一个子串（k=pos(rulei,1,tmp)0）在使用了第i条规则后，now变换为now=copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多个子串被第i条规则替换，因此每替换一次后，为了方便地找出下一个替换位置，我们将当前被替换串前（包括被替换串）的子串删除。第36页，共227页，编辑于2022年，星期五2 2、使用回溯法计算最少替换次数、使用回溯法计算最少替换次数、使用回溯法计算最少替换次数、使用回溯法计算最少替换次数由于原串a、目标串b和规则rule是随机输入的，因此不可能找出直接计算最少替换次数be
43、st的数学规律，只能采用回溯搜索的办法。设v状态（need,now）:替换次数为need，替换结果为now；v边界条件（needbest）和目标状态（now=b）：替换次数达到或超过目前得出的最小值为边界；已经替换出目标串为目标状态；v搜索范围i：尝试每一条规则,即1i规则数n；v约束条件（length(now)+length(rulei,2)-length(rulei,1)255）：now中的子串被第i条规则替换后的长度小于255；由此得出计算过程：第37页，共227页，编辑于2022年，星期五proceduresolve(need；now)；从当前串now出发，递归第need次替换vari
44、,k,j:integer；tmp:string；beginifneed=bestthenexit；若到达边界，则回溯ifnow=bthenbegin若达到目标状态，则记下替换次数，并回溯bestneed；exit；end；thenfori1tondo搜索每一条规则第38页，共227页，编辑于2022年，星期五iflength(now)+length(rulei,2)-length(rulei,1)0do反复在tmp中寻找子串rulei,1beginsolve(need+1，copy(now,1,j+k-1)+rulei,2+copy(now，j+k+length(rulei，1)，255)；递
45、归下一次替换delete(tmp,1,k)；将当前被替换串前（包括被替换串）的子串删除jj+k；右移匹配指针kpos(rulei,1,tmp)；继续尝试第i条规则end；whileend；thenend；solve第39页，共227页，编辑于2022年，星期五由此得出主程序：读入初始串a和目标串；读入替换规则rule；best31；设定替换次数的上限solve(0,a)；回溯搜索最少的替换次数ifbest=30输出最少替换次数thenwriteln(best)elsewriteln(ERROR!)；、第40页，共227页，编辑于2022年，星期五题三题三自由落体自由落体问问题题描描述述:在高为
46、H的天花板上有n个小球，体积不计，位置分别为0，1，2，n-1。在地面上有一个小车(长为L，高为K，距原点距离为S1)。已知小球下落距离计算公式为S=1/2*g*t2，其中g=10，t为下落时间。地面上的小车以速度V前进。如下图：小车与所有小球同时开始运动，当小球距小车的距离小车与所有小球同时开始运动，当小球距小车的距离0.000010.00001时，即认为小球被小时，即认为小球被小车接受车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个小球。输入输入：H，S1，v，L，k，n（1H，S1，v，L，k，n100000）输出输出：小车能接受到的小球个数。这是分区联赛最容易失这是分区
47、联赛最容易失误的一道试题，关键是误的一道试题，关键是弄清小车行程的物理意弄清小车行程的物理意义和计算的精度误差！义和计算的精度误差！第41页，共227页，编辑于2022年，星期五算法分析算法分析由题意可知，车顶与天花板的距离为h-k，小球由天花板落至车顶所花费的时间为t1=，由天花板落至地面的时间为t2=。小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。显然，若n1n2，则小车接受的小球数为n1-n2+1；否则小车未接受任何一个小球。小车在行驶了t1*v-0.00001路程后接受了第一个小球，其编号为n1=minn-1,小车在行
48、驶了t2*v+0.00001路程后小球落地，小车接受最后一个小球的编号为n2=max0，。为什么在为什么在n1 n1的公式中加上的公式中加上L L？为什么？为什么在在n2n2的公式中加上的公式中加上0.50.5？为什么？为什么n1 n1取下取下整、整、n2n2取上整？取上整？第42页，共227页，编辑于2022年，星期五矩形覆盖矩形覆盖问问题题描描述述：在平面上有n个点(n100)，每个点用一对整数坐标表示。例如：当n=4时，4个点的坐标分别为：p1(1，1)，p2(2，2)，p3(6，3)，p4(7，0)这这些些点点可可以以用用 k k 个个矩矩形形(k4)k4)全全部部覆覆盖盖，矩矩形形的
49、的边边平平行行于于坐坐标标轴轴。如图一，当k=2时，可用如图二的两个矩形s1，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：v 覆盖一个点的矩形面积为覆盖一个点的矩形面积为0 0；v覆盖平行于坐标轴直线上点的矩形面积也为覆盖平行于坐标轴直线上点的矩形面积也为0 0；v各个矩形间必须完全分开（边线也不能重合）；各个矩形间必须完全分开（边线也不能重合）；本试题是高中组复赛中最难的本试题是高中组复赛中最难的一道试题，对选手的几何基础一道试题，对选手的几何基础和编程能力是一个比较严峻的和编程能力是一个比较严峻的考验。考验。第43
50、页，共227页，编辑于2022年，星期五算法分析算法分析1、点和矩形的描述和关系、点和矩形的描述和关系平面上的点由坐标（x,y）表示。由于计算过程是按照由下而上、由左而右进行的，因此我们按照x坐标递增的顺序和y坐标递增的顺序将n个点存入a序列。矩形由2条平行于x轴的边界线和2条平行于y轴的边界线围成。为了计算最小矩形的方便，我们将空矩形的左边界设为、右边界为设-、下边界设为、上边界设为-。第44页，共227页，编辑于2022年，星期五2、计算覆盖所有点的一个最小矩形、计算覆盖所有点的一个最小矩形设目前最小矩形的四条边界为maxx，maxy，minx，miny。如何按照面积最小的要求将a点加入矩