信息学奥赛教程指导

1、上海市控江中学上海市控江中学 王建德王建德6 6、20022002、20032003年分区联赛复赛试年分区联赛复赛试题解析题解析1 1、高精度运算、高精度运算2 2、图的运算、图的运算3 3、搜索算法、搜索算法4 4、构造算法、构造算法5 5、动态程序设计、动态程序设计题题 型型题题 目目与课内知识相关与课内知识相关自由落体、级数求和、乒乓球、自由落体、级数求和、乒乓球、麦森数麦森数 字符串处理字符串处理字符近似查找字符近似查找贪心法贪心法均分纸牌、传染病控制均分纸牌、传染病控制 回溯法回溯法选数、字串变换、栈、神经网络、选数、字串变换、栈、神经网络、侦探推理侦探推理 动态程序设计方法动态程序

2、设计方法过河卒、数字游戏、加分二叉树过河卒、数字游戏、加分二叉树 几何计算几何计算矩形覆盖矩形覆盖 虽然虽然2002、2003年全国奥林匹克信息学复赛中含许多可年全国奥林匹克信息学复赛中含许多可“一题多解一题多解” 的试题，但如果按照较优算法标准分类的话，大致的试题，但如果按照较优算法标准分类的话，大致可分为可分为 1、凸现信息学知识和学科知识整合的趋势凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力，激发学生为了考核学生运用学科知识的能力，激发学生的创造力，的创造力，2002、2003年全国奥林匹克信息联年全国奥林匹克信息联赛赛(NOIP)中学科类的试题增加，并且首次出现中

3、学科类的试题增加，并且首次出现了计算几何类的试题了计算几何类的试题。这说明信息学与学。这说明信息学与学科的依赖关系日益凸现，学科基础好、尤其是科的依赖关系日益凸现，学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势林匹克信息学联赛活动发展的一个大趋势（按照（按照2005年国家

4、教改方案，数学教材增加算法内容，信息科技教材掺入语言知年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。识）。2、“构造法构造法” 或贪心策略类试题的引或贪心策略类试题的引入，使得入，使得算法知识的不确定性和不稳定算法知识的不确定性和不稳定性增加。性增加。这正体现了科学的本质这正体现了科学的本质知识知识是不断推陈出新的。是不断推陈出新的。3、试题的综合性增加试题的综合性增加，并不一定随知，并不一定随知识的分类而发生变化，有时几乎找不识的分类而发生变化，有时几乎找不到一个单一的经典算法到一个单一的经典算法，也找不到一个纯粹的数据结，也找不到一个纯粹的数据结构问题构问题，关键是你从

5、哪个角度去分析，关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；愈高，得胜的机率愈大； 4、经常面对着不知道算法的试题，经常面对着不知道算法的试题，面对着谁都不知如何处置的情境面对着谁都不知如何处置的情境，因此必须使学生正确地理解问因此必须使学生正确地理解问题、深入问题的空间并形成解决问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能题的意识、习惯和能力。能不能创创造性地应答没有遇到过的挑战造性地应答没有遇到过的挑战，成成为培训的基本要求和目标。为培训的基本

6、要求和目标。 1 1、培养问题意识和问题能力。培养问题意识和问题能力。创造始创造始于问题。于问题。“有了问题才会思考，有了思有了问题才会思考，有了思考才有解决问题的方法，才有找到独立考才有解决问题的方法，才有找到独立思路的可能（陶行知）思路的可能（陶行知）”。有问题虽然。有问题虽然不一定有创造，但没有问题一定没有创不一定有创造，但没有问题一定没有创造造； 2、处理好前沿性与基础性、直线培训和、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林

7、匹克信息学活动的学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的都有必要的跳跃，不少人还能够实现比较大的跳跃跳跃v学生必须学会从浩如烟海的信息中选择最有价值的知识，构建

8、个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构v培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的，因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。3、参与活动的学生应由竞、参与活动的学生应由竞争关系和独立关系争关系和独立关系转向合作学习的关系转向合作学习的关系学生的心理调适：学生的心理调适：v我掌握的知识仅不过是沧海一粟我掌握的知识仅不过是沧海一粟(进取心进取心)；v固守错误的概念比一无所知更可怕固守错误的概念比一无所知更可怕（

9、明智）（明智）；v三人之行必有我师三人之行必有我师（谦虚）（谦虚）；v知识生产社会化条件下人的基本素质之一知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如上千科学家进行长期甚至跨国的合作，例如制作制作windows，人类基因工程），人类基因工程）（现代意识）（现代意识）；前提条件：前提条件：水平相当的同质成员水平相当的同质成员或各有所长（包括数学知识、编或各有所长（包括数学知识、编程能力和思维方式等解题所需的程能力和思维方式等解题所需的各种因素）的异质成员是开展合各种因素）的异质成员是开展合作

10、学习的组织基础；作学习的组织基础；合作学习的效应：合作学习的效应：v集思广益容易出好的算法；集思广益容易出好的算法；v群体设计的测试数据相对全面；群体设计的测试数据相对全面；v在群体活动中能比较客观的反映自己在群体活动中能比较客观的反映自己能力情况；能力情况；v每个学生在付出与给予中可提高合作每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相精神和编程能力，成功者往往是那些相容性好、容性好、 乐于帮助他人，并且善于取乐于帮助他人，并且善于取他人之长的学生他人之长的学生（符文杰、张一飞等）。（符文杰、张一飞等）。4、选手面对从未遇到过的、选手面对从未遇到过的挑战应调整好心态，挑战

11、应调整好心态，不要急不要急功近利，要只管耕耘、不问收获、功近利，要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两潜心钻研、其乐无穷。那怕是一两次失误，也是砥砺之石，可从中汲次失误，也是砥砺之石，可从中汲取有益的经验和教训。取有益的经验和教训。“不是一番不是一番寒彻骨，哪得梅花扑鼻香寒彻骨，哪得梅花扑鼻香”。 第一题：字符近似查找第一题：字符近似查找设有n个单词的字典表（1n100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）： i：该单词在字典表中的序号； Ei：在字典表中仅有一个字符不匹配的单词序号； Fi：在字典表中多或少一个字符（其余字符匹配）

12、的单词序号； N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件输入文件 输入文件名为a.in，文件的格式如下： n（字典表的单词数） n行，每行一个单词 待匹配单词 输出文件输出文件 输出文件名a.out，格式如下： i Ei Fi其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。输入输出样例输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出输出1:4E5F1输入输入2:1ab输出输出2:0E0F0N我们将字典表中的单词分成3类： 第1类：单词与待匹配单词多

13、或少一个字符，其余字符匹配； 第2类：单词仅有一个字符与待匹配单词不匹配； 第3类：单词与待匹配单词完全匹配；设constnote :array1.3 of string=(F,E,)； 匹配情况的标志 var want:string； 待匹配单词list:array1.100 of string； 字典表。其中listi为字典ians ：array1.100 of integer；单词的类别序列。其中ansi= 其他情况相同与有一个字符不同与得到中添加或删除一个字符在0321ilistwantilistwantilistwant1、匹配情况的计算、匹配情况的计算计算两个等长字串中不同字符的个

14、数计算两个等长字串中不同字符的个数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 n判别一个字串是否比另一个字串多一个字符（其余字符匹配）判别一个字串是否比另一个字串多一个字符（其余字符匹配）n我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则

15、猜想不成立。nfunction check(a,b:string):integerfunction check(a,b:string):integer； 输入字串输入字串a,ba,b。若。若b b能够在能够在a a的基础的基础上添加一个字符得到的话，则返回上添加一个字符得到的话，则返回1 1；否则返回；否则返回00nvarvar i:integeri:integer；nbeginbeginncheck0check0；nfor i0 to length(a) do begin for i0 to length(a) do begin nacopy(a,1,i)+bi+1+copy(a,i+1,2

16、55)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 a中的插入字符中的插入字符 nendend；forfornendend；checkcheckn2 2、计算字典表中的每一类单词、计算字典表中的每一类单词首先，我们依次计算每一个单词的类别序号 在单词

17、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 对字典中的每个单词进行分类 if length(listi)=length(want) 若单词i与待匹配单词等长 then begin kfind

18、(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 check(want,listi)；end；forhavefalse； 匹配情况存在的标志初始化for i3 downto

19、 1 do begin 依次输出每一类别的单词在字典表最先出现的序号 k0； for j1 to n do if ansj=i then begin kj；break；end；thenhavehave or (k0)；writeln(notei,k)；end；for 第二题：级数求和第二题：级数求和 已知：Sn=1+1/2+1/3+.+1/n。显然当n.非常大的时候，Sn可大于任何一个整数K。现给出一个整数K（1K15），要求计算出一个最小的n，使得SnK。输入输入 键盘输入k 输出输出 屏幕输出n 输入输出样例输入输出样例输入: 1输出: 2算法分析算法分析 该题考核选手的并不是编程能力，而

20、是选择变量类型的能力。由于该数列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不下。但未必非高精度运算不可。只要启动浮点数运算（$n+），将项数设为extended类型，便可以得出正确解。$n+ 启动浮点数运算vars,b,k:extended； 数列的和、项数、最接近sn(大于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第三题：

21、选数第三题：选数 已知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+12+19=38 3+12+19=34。 现在，要求你计算出和为素数的组合数有多少种。例如上例，只有一种组合的和为素数：（3+7+19=29）。输入输入 输入文件名为c.in。文件格式n, k（1n20，ka，则说明a不可能分解出比primei大的素数了，a本身为素数。由于primei表的最大素数接近10000，其平方远大于xi的

22、上限5000000，因此是一个比较可行的方法：function check(a:longint):boolean； 判断a是否是素数beginchecktrue； 素数标志初始化for i1 to tot do begin 搜索素数表 if primei*primeia then exit；若超出搜索范围的上限，则说明a是素数，返回true if a mod primei=0 then begin checkfalse；exit；end；thenend；forend； check 2 2、递归搜索方案数、递归搜索方案数 由于数列是随机和无序的，因此只能通过搜索的办法求解。设 状态(left,n

23、ow,all)：目前组合为all，还需要从xnowxn中选出left个数； 约束条件(leftn-now+1)：xnowxn中数的个数大于等于left； 边界条件（(left=0) and (now=n+1)）和目标状态（check(all)=true）：从x1xn中选出k个数为边界。在这种情况下，若k个数的和为素数，则满足条件的种数+1。到达边界后，应回溯； 搜索范围为两种选择： 当前组合不选xnow,递归计算子状态(left,now+1,all)； 在还有数需要选的情况下（left0），xnow选入组合，递归计算子状态(left-1,now+1,all+listnow)；由此得出子程序Pr

24、ocedure solve(left,now,all:longint)；递归计算选数情况beginif (leftn-now+1)then exit；若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 sol

25、ve(left-1,now+1,all+listnow)；end； solve显然，递归调用solve(k,1,0)后得出的ans即为问题的解。过河卒过河卒如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。 同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2.P8）。卒不能通过对方马的控制点。 棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A 点能

26、够到达B点的路径的条数。输输 入：入： 键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输输 出：出： 屏幕输出一个整数（路径的条数）。输入输出样例：输入输出样例： 输入：3 3 2 2 输出：01 1、计算对方马的控制点、计算对方马的控制点 按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（显然，若（0，0）或（）或（n,m）为控制点，则输出路径数为）为控制

27、点，则输出路径数为0。设。设constconst move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(- move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)2,1),(-2,-1)； movek movek，1.21.2为马沿为马沿k k方向跳跃一步的水平增量和垂直增量方向跳跃一步的水平增量和垂直增量 varvar list:array-1.20,-1.20 of comp list:array-

28、1.20,-1.20 of comp； 路径数序列，其中路径数序列，其中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 b

29、eginfor i1 to 8 do begin从（从（x 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 (n

30、ot can0,0)or(not cann,m) if (not can0,0)or(not cann,m) 若卒的起点和终点为控制点，则输出路径数若卒的起点和终点为控制点，则输出路径数00 then writeln(0) then writeln(0) else begin else begin 计算和输出卒从（计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径数）点的路径数listn,mlistn,m；endend；elseelse2 2、计算和输出卒从（计算和输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条）点的路径条数数 我们按照由上而下、由左而右的顺

31、序，将卒可能到达的每一个位置（我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,ji,j）(0in(0in，0jm)0jm)设为阶段设为阶段, ,显然这样做，可以取消对状态的枚举。显然这样做，可以取消对状态的枚举。 首先，将卒的出发点（首先，将卒的出发点（0 0，0 0）的路径数设为）的路径数设为1 1（list0,01list0,01），并将该），并将该位置设为控制点（位置设为控制点（can0,0 falscan0,0 fals）。然后从（）。然后从（0 0，0 0）出发，按照由上而）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数。若（下、由左而右的顺序计算卒

32、经过每一个可行点的路径数。若（i i，j j）为可）为可行点，则卒可由上侧的（行点，则卒可由上侧的（i-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即为问题的解。由此得出算法：即为问题的解。由此得出算法： f

33、illchar(list,sizeof(list),0)fillchar(list,sizeof(list),0)； 路径数序列初始化路径数序列初始化 list0,01 list0,01； 卒从（卒从（0 0，0 0）出发的路径数为）出发的路径数为1 1，该位置不再允许卒通行，该位置不再允许卒通行 can0,0 false can0,0 false； for i0 to n dofor i0 to n do对于每个可行点对于每个可行点, ,小兵要么从左侧、要么从上方走到小兵要么从左侧、要么从上方走到, ,由此由此计算从计算从(0,0)(0,0)到到(i,j)(i,j)的路径数的路径数 for

34、j0 to m do if cani,j for j0 to m do if cani,j then listi,jlisti-1,j+listi,j-1 then listi,jlisti-1,j+listi,j-1；输出卒从（输出卒从（0 0，0 0）走到（）走到（n,mn,m）点的路径条数）点的路径条数listn,mlistn,m；问题描述问题描述 有N堆纸牌，编号分别为1，2，.N。每堆上有若干张， 但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为：在编号为1 1堆上取的纸牌，只能移到编号为堆上取的纸牌，只能移到编号为2 2的堆上；在编号为的堆上；在编

35、号为N N的堆上的堆上取的纸牌，只能移到编号为取的纸牌，只能移到编号为N-1N-1的堆上；其他堆上取的纸牌，可以移到相邻的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每用最少的移动次数使每堆上纸牌数都一样多堆上纸牌数都一样多。例如N=4，4堆纸牌数分别为： 9 8 17 6移动3次可达到目的：从取4张牌放到（9 8 13 10）从取3张牌放到（9 11 10 10）从取1张牌放到（10 10 10 10）。 输输 入入 ： N （ N 堆纸牌，1N100） A1，A2，.An (N 堆纸牌，每堆纸牌初始数，1Ai10000

36、) 输输 出出 ：所有堆均达到相等时的最少移动次数。输入输出样例输入输出样例输入：输入： 4 9 8 17 6 输出：输出： 3设list为纸牌序列，其中listi为第i堆纸牌的张数（1in），ave为均分后每堆纸牌的张数，即 ；ans为最少移动次数。nilistni1我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数listi超出平均值，则移动一次(ans+1)，将超出部分留给下一堆，既第i+1堆纸牌的张数增加listi-ave；若第i堆纸牌的张数listi少于平均值，则移动一次(ans+1)，由下一堆补充不足部分，既第i+1堆纸牌的张数减少ave-listi； 右邻堆取的牌问题是，在从第i

37、+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(listi+1-(ave-listi)xu ud-yy-yzA.out文件：文件： 3设规则序列为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的一个子串（k=pos

38、(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条规则替换，因此每替换一次后，为了方便地找出下一个替换位置，我们将当前被替换串前（包括被替换串）的子串删除。 由于原串a、目标串b和规则rule是随机输入的，因此不可能找出直接计算最少替换次数best的数学规律，只能采用回溯搜索的办法。设v 状态（need,now）:替换次数为need，替换结果为now；v 边界条件（needbest）和目标状态（now=b）：替换次数达到

39、或超过目前得出的最小值为边界；已经替换出目标串为目标状态；v 搜索范围i：尝试每一条规则,即1i规则数n；v约束条件（length(now)+length(rulei,2)-length(rulei,1)255）：now中的子串被第i条规则替换后的长度小于255；由此得出计算过程： procedure solve(need；now)；从当前串now出发，递归第need次替换vari,k,j:integer；tmp:string；beginif need=best then exit； 若到达边界，则回溯if now=b then begin若达到目标状态，则记下替换次数，并回溯 bestnee

40、d； exit； end；thenfor i1 to n do 搜索每一条规则 if length(now)+length(rulei,2)-length(rulei,1)0 do 反复在tmp 中寻找子串rulei,1 begin solve(need+1，copy(now,1,j+k-1)+rulei,2+copy(now，j+k+length(rulei，1)，255)； 递归下一次替换 delete(tmp,1,k)；将当前被替换串前（包括被替换串）的子串删除 jj+k； 右移匹配指针 kpos(rulei,1,tmp)； 继续尝试第i条规则 end；while end；thenend

41、； solve 由此得出主程序：读入初始串a和目标串；读入替换规则rule；best31； 设定替换次数的上限solve(0,a)； 回溯搜索最少的替换次数if best=30 输出最少替换次数 then writeln(best) else writeln(ERROR!)；、问题描述问题描述: 在高为H 的天花板上有n个小球，体积不计，位置分别为0，1，2，n-1。在地面上有一个小车(长为L，高为K，距原点距离为S1)。已知小球下落距离计算公式为 S=1/2*g*t2，其中 g=10， t为下落时间。地面上的小车以速度 V 前进。如下图： 小车与所有小球同时开始运动，当小球距小车的距离小车与

42、所有小球同时开始运动，当小球距小车的距离0.000010.00001时，即认为时，即认为小球被小车接受小球被小车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个小球。输入输入：H，S1，v，L，k，n （1H，S1，v，L，k，n100000）输出输出：小车能接受到的小球个数。 由题意可知，车顶与天花板的距离为h-k，小球由天花板落至车顶所花费的时间为t1= ，由天花板落至地面的时间为t2= 。小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。10)(*2kh10*2 h00001. 0*1lvts5 . 00000

43、1. 0*2vts显然，若n1n2，则小车接受的小球数为n1-n2+1；否则小车未接受任何一个小球。 小车在行驶了t1*v-0.00001路程后接受了第一个小球，其编号为n1=minn-1, 小车在行驶了t2*v+0.00001路程后小球落地，小车接受最后一个小球的编号为n2=max0， 。问题描述问题描述：在平面上有n个点 (n100)，每个点用一对整数坐标表示。例如：当n=4 时，4 个点的坐标分别为： p1(1，1)， p2(2，2)， p3 (6，3)， p4(7，0)这些点可以用这些点可以用 k k 个矩形个矩形( k4) ( k4) 全部覆盖，矩形的边平行于坐标轴全部覆盖，矩形的边

44、平行于坐标轴。如图一，当 k=2时，可用如图二的两个矩形s1，s2覆盖， s1，s2面积和为4。问题是当 n个点坐标和 k 给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：v 覆盖一个点的矩形面积为覆盖一个点的矩形面积为0 0；v覆盖平行于坐标轴直线上点的矩形面积也为覆盖平行于坐标轴直线上点的矩形面积也为0 0；v各个矩形间必须完全分开（边线也不能重合）；各个矩形间必须完全分开（边线也不能重合）； 平面上的点由坐标（x,y）表示。由于计算过程是按照由下而上、由左而右进行的，因此我们按照x坐标递增的顺序和y坐标递增的顺序将n个点存入a序列。矩形由2条平行于x轴的边界线和2条平行

45、于y轴的边界线围成。为了计算最小矩形的方便，我们将空矩形的左边界设为、右边界为设-、下边界设为、上边界设为-。 2、计算覆盖所有点的一个最小矩形、计算覆盖所有点的一个最小矩形设目前最小矩形的四条边界为maxx，maxy，minx，miny。如何按照面积最小的要求将a点加入矩形呢？显然需要调整边界显然需要调整边界线，使线，使a a点位于对应的边界线上。点位于对应的边界线上。初始时，我们设最小矩形为空，即左边界left为、右边界right为-、下边界top为、上边界bottom为-。然后由左而右，依次往矩形放入n个点，调整对应的边界线。最后得出的矩形为最小矩形，其面积为（右边界-左边界）*（上边界

46、-下边界） 我们称彼此完全分开的矩形是独立的。两个覆盖所有点的独立矩形有两种形态： 我们将覆盖x轴左方点集a1,1.j的最小独立矩形存入tac1,j；将覆盖x轴右方点集a1,j.n的最小独立矩形存入tdc1,j；将覆盖y轴下方点集a2,1.j的最小独立矩形存入tac2,j；将覆盖y轴上方点集a2,j.n的最小独立矩形存入tdc2,j（注意：当k=3时，对应的点集不包括被矩形1覆盖的点（1j n ）。 Tac1,j-1Tdc1,jTac2,j-1Tdc2,j问题是面积和最小的两个独立矩形究竟取哪一个形态，区分两个矩形的分界线j为何值，我们无法确定。不得已，只能将所有可能的情况枚举出来。设var

47、best，now:longint；两个独立矩形的最小面积和、当前方案中两个独立矩形的面积和枚举过程如下： 计算tac和tdc序列； bestmaxlongint； 最小矩形面积初始化 for i1 to 2 do begin 依次分析x轴向和y轴向 k=3时顺序寻找i轴向上第一个未被矩形1覆盖的点j； while jn do枚举i轴向上所有可能的两个独立矩形，从中找出最佳方案 begin 记下i轴向上点j的坐标h； 顺序寻找i轴向上最接近h点(k=3时，该点未被矩形1覆盖)的点j； if 点j存在并且k=2，或者k=3时以点j为分界线的左矩形和右矩形与矩形1没有交集 then begin no

48、w(taci，j-1，1-taci，j-1，3)*(taci，j-1，2-taci，j-1，4)+(tdci，j，1-tdci，j，3)*(tdci，j，2-tdci，j，4)；则计算两个独立矩形的面积和 if nowbest then bestnow； 若面积和为目前最小，则记下 end；thenend；whileend；for if best=maxlongint 若找不到的两个独立矩形 then返回失败标志-1 else返回两个矩形的最小面积和best；end；getans 我们先枚举第一个矩形，该矩形覆盖x轴向上的点1、点i、点j、点h（1in, ijn, jhn）,求出覆盖它们的最小

49、矩形。该矩形的上边界、下边界、左边界和右边界分别记为bottom、top、left、right。显然其面积为(bottom-top)*(right-left)。我们将该矩形称为矩形1。那么，平面上还有哪些点未在矩形1内，这些点将被另外两个独立的矩形所覆盖。 (xleft) and (xright) and (ybottom) and (ytop) (min(x1,right) max(x2,left) and (min(y1,bottom) max(y2,top)我们在得出矩形1的基础上，直接调用上述算法计算与矩形1分开的另外两个独立矩形的面积和，加上矩形1的面积便是三个独立矩形的面积和。问题

50、是矩形1究竟覆盖了哪些点才能得出最优解呢？我们无法得知。无奈之下，只能通过枚举法搜索所有的可能情况for i1 to n do 枚举x轴向上三个点（点i、点j、点h）的所有可能组合 for ji to n do for hj to n do begin 计算覆盖点1、点i、点j、点h的最小矩形（矩形1）的四条边界right、bottom、left、top； now(bottom-top)*(right-left)； 计算矩形1的面积 计算未被矩形1覆盖的点集u； 计算覆盖u且与矩形1不相交的两个独立矩形的最小面积和g； if (g0) and (g+now1)），则输出当前局的比分a：b。请注

51、意，如果输入的字符为E，则标志比赛结束，11分制计算完毕；否则，继续读下一个字符，计算新一局的比分。然后，对当前输入行计算21分制下每一局比赛的比分。计算方法基本如上。有所不同的是，若华华得分a或者对方得分b达到21分且双方的分数差值大于1（(a21) or(b21)and (abs(a-b)1)），则输出当前局的比分a：b。 按照上述方法对每一输入行计算11分制和21分制的比赛结果，直至文件读完（eof(input)）为止。a s s i g n ( i n p u t , i n p ) ; reset(input);输入文件读准备 assign(output,out);rewrite(o

52、utput);输出文件写准备 a:=0;b:=0; 当前局双方的比分初始化 while not eof (input) do若文件未读完，则循环 begin while not eoln(input) do若当前行处理完，则11分制的比赛结束 begin read(ch);读一个字符 case ch of根据字符的种类分情形处理 E: begin若比赛结束，则输出双方比分 writeln(a,:,b); break;退出11分制的计算过程 end; E W,L: begin华华或对方得一分 if ch=Wthen inc(a)else inc(b); if(a=11)or(b=11) and

53、(abs(a-b)1) then若有一方得分达到11分且双方的分数差值大于1，则输出双方比分 begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln; end; while a:=0; b:=0; 新一局的比分初始化 writeln; reset(input);重新读输入行 while not eof(input) do若文件未读完且比赛未结束，则循环 begin while not eoln(input) do若当前行处理完，则21分制的比赛结束 begin read(ch);

54、读一个字符 case ch of根据字符的种类分情形处理 E: begin若比赛结束，则输出双方比分，退出21分制的计算过程 writeln(a,:,b); break; end; E W,L: begin华华或对方得一分 if ch=Wthen inc(a) else inc(b); if (a=21)or(b=21) and (abs(a-b)1) 若有一方得分达到21分且双方的分数差值大于1，则输出双方比分 then begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln;

55、 end;while close(input); close(output);关闭输入文件和输出文件 数字游戏（数字游戏（Game.pasGame.pas） 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如，对于下面这圈数字（n=4，m=2）：当要求最小值时，(2-1) mod 10)(4+3) mod 10)=17=7，要求

56、最大值时，为(2+4+3) mod 10)(-1 mod 10)=99=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。 【输入格式】输入文件第一行有两个整数，n（1n50）和m（1m9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。 【输出格式】输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。算法分析算法分析 设圆周上的n个数字为a1、a2、an。按照模运算的规则（a1+a2+ +ak）mod 10=(a1 mod 10+a2 mod 10+ ak mod 10)mod

57、10；gi，j为ai、ai+1、aj的数和对10的模，即 gi，j=（ai+ai+1+ +aj）mod 10显然 gi，i=（ai mod 10+10）mod 10 gi，j= (gi,j-1+gj,j) mod 10 (1in，i+1jn)当m=1时，程序得到的最小值和最大值为g1,n；fmax1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后 再 相 乘 ， 最 终 得 到 最 大 数 。 显 然 ，fmax11,i,j= gi，j；fmin1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后再相

58、乘，最终得到最小数。显然，fmin11,i,j= gi，j；(1pm)问题是当ai、ai+1、aj划分成的部分数p大于1时，怎么办。我们采用动态程序设计的方法计算。设 阶段p：划分成的部分数,2pm-1； 状态（i，j）:将ai、ai+1、aj划分成p个部分，1in，ijn； 决策k: 将ai、ai+1、ak划分成p-1个部分，ak+1、aj为第p部分，ikj-1；显然，状态转移方程为 fmin1p,i,j= fmin1p-1,i,k*gk+1,j fmax1p,i,j= fmax1p-1,i,k*gk+1,j2pm-11minjki1maxjkimax=min= 由于p-1阶段仅和p阶段发生

59、联系，因此我们将p-1阶段的状态转移方程fmin1p-1,i,j设为fmin1i,j、fmax1p-1,i,j 设为fmax1i,j，将p阶段的状态转移方程fmin1p,i,j设为fmini,j、fmax1p,i,j设为fmaxi,j。 )() 1( , 1 1max*10mod), 1 1, 1 (max1njorijimfnjgignjini )() 1( , 1 1min*10mod), 1 1, 1 (min1njorijimfnjgignjini read(n,m);读数字个数和划分的部分数 fillchar(fmax1,sizeof(fmax1),0); fillchar(fmin

60、1,sizeof(fmin1),$FF);状态转移方程初始化 fillchar(g,sizeof(g),0); for i:=1 to n do依次读入每个数，一个数组成一部分 begin read(gi,i); gi,i:=(gi,imod mask+mask) mod mask; min1i,i:=gi,i;fmax1i,i:=gi,i; end;for for i:=1 to n do计算一部分内的数和对10的模的所有可能情况 for j:=i+1 to n do begin gi,j:=(gi,j-1+gj,j) mod mask; fmax1i,j:=gi,j; fmin1i,j:=