信息学奥赛教程指导

1、信息学奥赛教程指导第1页，共227页，2022年，5月20日，16点36分，星期一6、2002、2003年分区联赛复赛试题解析1、高精度运算2、图的运算3、搜索算法4、构造算法5、动态程序设计第2页，共227页，2022年，5月20日，16点36分，星期一2002、2003年全国分区联赛复赛试题解析 第3页，共227页，2022年，5月20日，16点36分，星期一题 型题 目与课内知识相关自由落体、级数求和、乒乓球、麦森数 字符串处理字符近似查找贪心法均分纸牌、传染病控制 回溯法选数、字串变换、栈、神经网络、侦探推理 动态程序设计方法过河卒、数字游戏、加分二叉树 几何计算矩形覆盖 虽然2002

2、、2003年全国奥林匹克信息学复赛中含许多可“一题多解” 的试题，但如果按照较优算法标准分类的话，大致可分为 第4页，共227页，2022年，5月20日，16点36分，星期一特 点 1、凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力，激发学生的创造力，2002、2003年全国奥林匹克信息联赛(NOIP)中学科类的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与学科的依赖关系日益凸现，学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合

3、是奥林匹克信息学联赛活动发展的一个大趋势（按照2005年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。2、“构造法” 或贪心策略类试题的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质知识是不断推陈出新的。第5页，共227页，2022年，5月20日，16点36分，星期一3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(字串变换回溯法中有字符串处理)，也找不到一个纯粹的数据结构问题（级数求和需要为表达式的计算结果设计合适的数据类型），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈

4、高，得胜的机率愈大； 4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得0分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。第6页，共227页，2022年，5月20日，16点36分，星期一 1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相

5、关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）；启 示2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（ 爱笛生小学三年级退学、比尔.盖茨大学三年级退学）第7页，共227页，2022年，5月20日，16点36分，星期一学生必须学会从浩如烟海的

6、信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。 3、参与活动的学生应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算

7、法、集中编程、互测数据等互相合作的方式完成学习任务）第8页，共227页，2022年，5月20日，16点36分，星期一学生的心理调适：我掌握的知识仅不过是沧海一粟(进取心)；固守错误的概念比一无所知更可怕（明智）；三人之行必有我师（谦虚）；知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作windows，人类基因工程）（现代意识）；前提条件：水平相当的同质成员或各有所长（包括数学知识、编程能力和思维方式等解题所需的各种因素）的异质成员是开展合作学习的组织基础；合作学习的效应：集思广益容易出好的算法；群体设计的测试数据相对全面；在群

8、体活动中能比较客观的反映自己能力情况；每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性好、 乐于帮助他人，并且善于取他人之长的学生（符文杰、张一飞等）。第9页，共227页，2022年，5月20日，16点36分，星期一4、选手面对从未遇到过的挑战应调整好心态，不要急功近利，要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两次失误，也是砥砺之石，可从中汲取有益的经验和教训。“不是一番寒彻骨，哪得梅花扑鼻香”。第10页，共227页，2022年，5月20日，16点36分，星期一题5、均分纸牌题6、字串变换题7、自由落体题8、 矩形覆盖题 1、字符近似查找题2、级数求和题3、选数

9、题4、过河卒9、乒乓球 10、数字游戏 11、栈 12、麦森数 13、神经网络 14、侦探推理 15、加分二叉树 16、传染病控制 第11页，共227页，2022年，5月20日，16点36分，星期一第一题：字符近似查找设有n个单词的字典表（1n100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）： i：该单词在字典表中的序号； Ei：在字典表中仅有一个字符不匹配的单词序号； Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号； N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件 输入文件名为a.in，文件的格式如下： n

10、（字典表的单词数） n行，每行一个单词 待匹配单词第12页，共227页，2022年，5月20日，16点36分，星期一输出文件 输出文件名a.out，格式如下： i Ei Fi其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出1:4E5F1输入2:1ab输出2:0E0F0N第13页，共227页，2022年，5月20日，16点36分，星期一我们将字典表中的单词分成3类： 第1类：单词与待匹配单词多或少一个字符，其余字符匹配； 第2类：单词仅有

11、一个字符与待匹配单词不匹配； 第3类：单词与待匹配单词完全匹配；设constnote :array1.3 of string=(F,E,)； 匹配情况的标志var want:string； 待匹配单词list:array1.100 of string； 字典表。其中listi为字典ians ：array1.100 of integer；单词的类别序列。其中ansi= 第14页，共227页，2022年，5月20日，16点36分，星期一1、匹配情况的计算计算两个等长字串中不同字符的个数function find(a,b:string):integer；输入两个等长字串a,b，计算和返回不同字符的个

12、数vari,tot:integer；begintot0；for i1 to length(a) do if aibi then inc(tot)；findtot；end； find 第15页，共227页，2022年，5月20日，16点36分，星期一判别一个字串是否比另一个字串多一个字符（其余字符匹配）我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。function check(a,b:string):integer；输入字串a,b。若b能够在a的基础上添加一个字符得到的话，

13、则返回1；否则返回0vari:integer；begincheck0；for i0 to length(a) do begin acopy(a,1,i)+bi+1+copy(a,i+1,255)；在ai后插入bi+1if a=b 若插入后两串相同，则成功退出then begin check1；exit；end；thendelete(a,i+1,1)； 删去a中的插入字符end；forend；check第16页，共227页，2022年，5月20日，16点36分，星期一2、计算字典表中的每一类单词首先，我们依次计算每一个单词的类别序号在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为

14、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(listi,want)；计算单词i与待匹配单词的不同字符个

15、数 if k=0 then ansi 3； 记下类别序号 if k=1 then ansi 2； end；then第17页，共227页，2022年，5月20日，16点36分，星期一若单词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 dow

16、nto 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第18页，共227页，2022年，5月20日，16点36分，星期一 第二题：级数求和 已知：Sn=1+1/2+1/3+.+1/n。显然当n.非常大的时候，Sn可大于任何一个整数K。现给出一个整数K（1K15），要求计算出一个最小的n，使得SnK。输入 键盘输入k输出 屏幕输出n输入输出样例输入:1输出:2第19页，共227页，

17、2022年，5月20日，16点36分，星期一算法分析 该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数列是递减的，而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；

18、ss+1/b； end；while 输出项数round(b)；end.main第20页，共227页，2022年，5月20日，16点36分，星期一第三题：选数 已知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）。第21页，共227页，2022年，5月20日，1

19、6点36分，星期一输入 输入文件名为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 搜索素数表 if primei*primeia then exit；若超出搜索范围的上限，则说明a是素数，返回true if a mod primei=0 then begi

20、n checkfalse；exit；end；thenend；forend； check 第24页，共227页，2022年，5月20日，16点36分，星期一2、递归搜索方案数 由于数列是随机和无序的，因此只能通过搜索的办法求解。设 状态(left,now,all)：目前组合为all，还需要从xnowxn中选出left个数； 约束条件(leftn-now+1)：xnowxn中数的个数大于等于left； 边界条件（(left=0) and (now=n+1)）和目标状态（check(all)=true）：从x1xn中选出k个数为边界。在这种情况下，若k个数的和为素数，则满足条件的种数+1。到达边界后

21、，应回溯； 搜索范围为两种选择： 当前组合不选xnow,递归计算子状态(left,now+1,all)； 在还有数需要选的情况下（left0），xnow选入组合，递归计算子状态(left-1,now+1,all+listnow)；由此得出子程序第25页，共227页，2022年，5月20日，16点36分，星期一Procedure solve(left,now,all:longint)；递归计算选数情况beginif (leftn-now+1)then exit；若xnowxn中不足left个数，则回溯 if (left=0) and (now=n+1) 若从x1xn中选出了k个数 then be

22、gin 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页，共227页，2022年，5月20日，16点36分，星期一过河卒如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者

23、向右。第27页，共227页，2022年，5月20日，16点36分，星期一 同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制8个点（图中的P1，P2.P8）。卒不能通过对方马的控制点。 棋盘用坐标表示，A点（0，0）、B点（n，m）(n,m为不超过20的整数,并由键盘输入)，同样马的位置坐标是需要给出的（约定：CA，同时CB）。现在要求你计算出卒从A 点能够到达B点的路径的条数。输 入： 键盘输入B点的坐标(n,m)以及对方马的坐标（X，Y）输 出： 屏幕输出一个整数（路径的条数）。输入输出样例： 输入：3 3

24、2 2 输出：0第28页，共227页，2022年，5月20日，16点36分，星期一1、计算对方马的控制点 按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设const move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)； movek，1.2为马沿k方向跳跃一步的水平增量和垂直增量var list:array-1.20,-1.20 of c

25、omp；路径数序列，其中listi,j为卒从(0,0)到(i,j)的路径数 can:array0.20,0.20 of boolean； 点(i,j)允许卒通行的标志马的初始位置为（x,y）。我们按照下述方式计算can序列：canx,y false； 对方马所在的点为控制点for i1 to 8 do begin从（x，y）出发，沿8个跳马方向计算控制点 jx+movei,1； 计算i方向的跳马位置(j，k) ky+movei,2； if (j=0) and (k=0) and (j=n) and (k=m) 若（j,k）在界内，则为控制点 then canj,k false；end；fori

26、f (not can0,0)or(not cann,m) 若卒的起点和终点为控制点，则输出路径数0 then writeln(0) else begin 计算和输出卒从（0，0）走到（n,m）点的路径数listn,m；end；else第29页，共227页，2022年，5月20日，16点36分，星期一2、计算和输出卒从（0，0）走到（n,m）点的路径条数 我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,j）(0in，0jm)设为阶段,显然这样做，可以取消对状态的枚举。 首先，将卒的出发点（0，0）的路径数设为1（list0,01），并将该位置设为控制点（can0,0 fals）。

27、然后从（0，0）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数。若（i，j）为可行点，则卒可由上侧的（i-1,j）和左侧的（i,j-1）进入该点。将这两点的路径数加起来，即为从（0，0）走到（i，j ）的路径数，即 listi,j=listi-1,j+listi,j-1（i，j）非控制点依次类推，最后得出的listn,m即为问题的解。由此得出算法： fillchar(list,sizeof(list),0)； 路径数序列初始化 list0,01；卒从（0，0）出发的路径数为1，该位置不再允许卒通行 can0,0 false； for i0 to n do对于每个可行点,小兵要

28、么从左侧、要么从上方走到,由此计算从(0,0)到(i,j)的路径数 for j0 to m do if cani,j then listi,jlisti-1,j+listi,j-1；输出卒从（0，0）走到（n,m）点的路径条数listn,m；第30页，共227页，2022年，5月20日，16点36分，星期一题一 均分纸牌问题描述 有N堆纸牌，编号分别为1，2，.N。每堆上有若干张， 但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右

29、边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如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) 输 出 ：所有堆均达到相等时的最少移动次数。输入输出样例第31页，共227页，2022年，5月20日，16点36分，星期一输入： 4 9 8 17 6 输出： 3设list为纸牌序列，其中listi为第i堆纸牌的张数（1i

30、n），ave为均分后每堆纸牌的张数，即 ；ans为最少移动次数。我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数listi超出平均值，则移动一次(ans+1)，将超出部分留给下一堆，既第i+1堆纸牌的张数增加listi-ave；若第i堆纸牌的张数listi少于平均值，则移动一次(ans+1)，由下一堆补充不足部分，既第i+1堆纸牌的张数减少ave-listi； 右邻堆取的牌第32页，共227页，2022年，5月20日，16点36分，星期一问题是，在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(listi+1-(ave-listi)xu ud-yy-yzA.ou

31、t文件： 3第35页，共227页，2022年，5月20日，16点36分，星期一1、分析变换规则设规则序列为rule，其中第i条规则为rulei，1rulei，2；当前串为now，其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的，因此设j为now的指针，即从now的第j个字符开始匹配rulei,1。now适用第i条规则的条件是now中的子串被第i条规则替换后的长度小于255，即 length(now)+length(rulei,2)-length(rulei,1)255rulei,1是now的一个子串（k=pos(rulei,1,tmp)0）在使用了第i条规则后，now变换为no

32、w= copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多个子串被第i条规则替换，因此每替换一次后，为了方便地找出下一个替换位置，我们将当前被替换串前（包括被替换串）的子串删除。 第36页，共227页，2022年，5月20日，16点36分，星期一2、使用回溯法计算最少替换次数由于原串a、目标串b和规则rule是随机输入的，因此不可能找出直接计算最少替换次数best的数学规律，只能采用回溯搜索的办法。设 状态（need,now）:替换次数为need，替换结果为now； 边界条件（needbest）和目标状态（n

33、ow=b）：替换次数达到或超过目前得出的最小值为边界；已经替换出目标串为目标状态； 搜索范围i：尝试每一条规则,即1i规则数n；约束条件（length(now)+length(rulei,2)-length(rulei,1)255）：now中的子串被第i条规则替换后的长度小于255；由此得出计算过程： 第37页，共227页，2022年，5月20日，16点36分，星期一procedure solve(need；now)；从当前串now出发，递归第need次替换vari,k,j:integer；tmp:string；beginif need=best then exit； 若到达边界，则回溯if

34、now=b then begin若达到目标状态，则记下替换次数，并回溯 bestneed； exit； end；thenfor i1 to n do 搜索每一条规则 第38页，共227页，2022年，5月20日，16点36分，星期一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)；将当前被替换串前（

35、包括被替换串）的子串删除 jj+k； 右移匹配指针 kpos(rulei,1,tmp)； 继续尝试第i条规则 end；while end；thenend； solve 第39页，共227页，2022年，5月20日，16点36分，星期一由此得出主程序：读入初始串a和目标串；读入替换规则rule；best31； 设定替换次数的上限solve(0,a)； 回溯搜索最少的替换次数if best=30 输出最少替换次数 then writeln(best) else writeln(ERROR!)；、第40页，共227页，2022年，5月20日，16点36分，星期一题三 自由落体问题描述: 在高为H 的

36、天花板上有n个小球，体积不计，位置分别为0，1，2，n-1。在地面上有一个小车(长为L，高为K，距原点距离为S1)。已知小球下落距离计算公式为 S=1/2*g*t2，其中 g=10， t为下落时间。地面上的小车以速度 V 前进。如下图： 小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个小球。输入：H，S1，v，L，k，n （1H，S1，v，L，k，n100000）输出：小车能接受到的小球个数。 这是分区联赛最容易失误的一道试题，关键是弄清小车行程的物理意义和计算的精度误差！第41页，共227页，202

37、2年，5月20日，16点36分，星期一算法分析由题意可知，车顶与天花板的距离为h-k，小球由天花板落至车顶所花费的时间为t1= ，由天花板落至地面的时间为t2= 。小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。显然，若n1n2，则小车接受的小球数为n1-n2+1；否则小车未接受任何一个小球。 小车在行驶了t1*v-0.00001路程后接受了第一个小球，其编号为n1=minn-1, 小车在行驶了t2*v+0.00001路程后小球落地，小车接受最后一个小球的编号为n2=max0， 。为什么在n1的公式中加上L？为什么在n2的公式中

38、加上0.5？为什么n1取下整、n2取上整？第42页，共227页，2022年，5月20日，16点36分，星期一矩形覆盖问题描述：在平面上有n个点 (n100)，每个点用一对整数坐标表示。例如：当n=4 时，4 个点的坐标分别为： p1(1，1)， p2(2，2)， p3 (6，3)， p4(7，0)这些点可以用 k 个矩形( k4) 全部覆盖，矩形的边平行于坐标轴。如图一，当 k=2时，可用如图二的两个矩形s1，s2覆盖， s1，s2面积和为4。问题是当 n个点坐标和 k 给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定： 覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形

39、面积也为0；各个矩形间必须完全分开（边线也不能重合）；本试题是高中组复赛中最难的一道试题，对选手的几何基础和编程能力是一个比较严峻的考验。 第43页，共227页，2022年，5月20日，16点36分，星期一算法分析 1、点和矩形的描述和关系 平面上的点由坐标（x,y）表示。由于计算过程是按照由下而上、由左而右进行的，因此我们按照x坐标递增的顺序和y坐标递增的顺序将n个点存入a序列。矩形由2条平行于x轴的边界线和2条平行于y轴的边界线围成。为了计算最小矩形的方便，我们将空矩形的左边界设为、右边界为设-、下边界设为、上边界设为-。 第44页，共227页，2022年，5月20日，16点36分，星期一

40、2、计算覆盖所有点的一个最小矩形设目前最小矩形的四条边界为maxx，maxy，minx，miny。如何按照面积最小的要求将a点加入矩形呢？显然需要调整边界线，使a点位于对应的边界线上。初始时，我们设最小矩形为空，即左边界left为、右边界right为-、下边界top为、上边界bottom为-。然后由左而右，依次往矩形放入n个点，调整对应的边界线。最后得出的矩形为最小矩形，其面积为（右边界-左边界）*（上边界-下边界）第45页，共227页，2022年，5月20日，16点36分，星期一3、计算覆盖所有点的两个面积和最小的独立矩形 我们称彼此完全分开的矩形是独立的。两个覆盖所有点的独立矩形有两种形态

41、： 我们将覆盖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为什么一定要考虑两个轴向,如果仅考虑一个轴向的话,有什么反例?第46页，共227页，2022年，5月20日，16点36分，星期一问题是面积和最小的两个独立矩形究竟取哪一个形态，区分两个矩形的分界线j为何值，我们无法确定。

42、不得已，只能将所有可能的情况枚举出来。设var 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； 第47页，共227页，2022年，5月20日，16点36分，星期

43、一if 点j存在并且k=2，或者k=3时以点j为分界线的左矩形和右矩形与矩形1没有交集 then begin now(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第

44、48页，共227页，2022年，5月20日，16点36分，星期一4、计算覆盖所有点的三个面积和最小的独立矩形 我们先枚举第一个矩形，该矩形覆盖x轴向上的点1、点i、点j、点h（1in, ijn, jhn）,求出覆盖它们的最小矩形。该矩形的上边界、下边界、左边界和右边界分别记为bottom、top、left、right。显然其面积为(bottom-top)*(right-left)。我们将该矩形称为矩形1。那么，平面上还有哪些点未在矩形1内，这些点将被另外两个独立的矩形所覆盖。 判断（x,y）是否在矩形1内的条件 (xleft) and (xright) and (ybottom) and (y

45、top) 判断矩形是否与矩形1相交的条件(min(x1,right) max(x2,left) and (min(y1,bottom) max(y2,top)第49页，共227页，2022年，5月20日，16点36分，星期一我们在得出矩形1的基础上，直接调用上述算法计算与矩形1分开的另外两个独立矩形的面积和，加上矩形1的面积便是三个独立矩形的面积和。问题是矩形1究竟覆盖了哪些点才能得出最优解呢？我们无法得知。无奈之下，只能通过枚举法搜索所有的可能情况for i1 to n do 枚举x轴向上三个点（点i、点j、点h）的所有可能组合 for ji to n do for hj to n do b

46、egin 计算覆盖点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。请注意，如果输入的字符为E，则标志比赛结束，11分制计算完毕；否则，继续读下一个字符，计算新一局的比分。然后，对当前输入行计算21分制下每一局比赛的比分。计算方法基本如上。有所不同的是，若华华得分a或者对方得分b达到21分且双方的分数差值大于1（(

47、a21) or(b21)and (abs(a-b)1)），则输出当前局的比分a：b。 按照上述方法对每一输入行计算11分制和21分制的比赛结果，直至文件读完（eof(input)）为止。第54页，共227页，2022年，5月20日，16点36分，星期一assign(input,inp); reset(input);输入文件读准备 assign(output,out);rewrite(output);输出文件写准备 a:=0;b:=0; 当前局双方的比分初始化 while not eof (input) do若文件未读完，则循环 begin while not eoln(input) do若当前

48、行处理完，则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 (abs(a-b)1) then若有一方得分达到11分且双方的分数差值大于1，则输出双方比分 begin writeln(a,:,b); 第55页，共227页，2022年，5月20日，16点36分，星期一a:=0

49、;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);读一个字符 第56页，共227页，2022年，5月20日，16点36分，星期一case ch of根据字符的种类分情形处理 E: begin若比赛

50、结束，则输出双方比分，退出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; end;while close(input); close(output);关

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

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

53、 10=(a1 mod 10+a2 mod 10+ ak mod 10)mod 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；第60页，共227页，2022年，5月20日，16点36分，星期一fmax1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后再相乘，最终得到最大数。显然，fmax11,i,j= gi

54、，j；fmin1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后再相乘，最终得到最小数。显然，fmin11,i,j= gi，j；(1pm)问题是当ai、ai+1、aj划分成的部分数p大于1时，怎么办。我们采用动态程序设计的方法计算。第61页，共227页，2022年，5月20日，16点36分，星期一设 阶段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= fm

55、in1p-1,i,k*gk+1,j fmax1p,i,j= fmax1p-1,i,k*gk+1,j2pm-1第62页，共227页，2022年，5月20日，16点36分，星期一max=min= 由于p-1阶段仅和p阶段发生联系，因此我们将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。 第63页，共227页，2022年，5月20日，16点36分，星期一 read(n,m);读数字个数和划分的部分数 fillchar(fmax1

56、,sizeof(fmax1),0); fillchar(fmin1,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

57、mask; fmax1i,j:=gi,j; fmin1i,j:=gi,j;end;forfor p:=2 to m-1 do阶段：递推计算划分2部分m-1部分的结果值beginfillchar(fmax,sizeof(fmax),0); 划分p部分的状态转移方程初始化fillchar(fmin,sizeof(fmin),$FF); 第64页，共227页，2022年，5月20日，16点36分，星期一for i:=1 to n do状态：枚举被划分为p部分的数字区间 for j:=i to n do for k:=i to j-1 do决策：aiak被划分为p-1部分 begin if fmax1

58、i,k*gk+1,jfmaxi,j 计算将ai、ai+1、aj划分成p个部分的状态转移方程 then fmaxi,j:=fmax1i,k*gk+1,j; if(fmin1i,k=0)and(fmin1i,k*gk+1,jfmini,j)or(fmini,j0)then fmini,j:=fmin1i,k*gk+1,j; end;for fmin1:=fmin;fmax1:=fmax; end;formax:=0;min:=maxlongint;将a1、a2、an划分成m个部分的最大值和最小值初始化if m=1 计算n个数划分成一部分的最大值和最小值 then begin max:=g1,n;m

59、in:=g1,n;endthen 第65页，共227页，2022年，5月20日，16点36分，星期一else for i:=1 to n do将a1ai-1、aj+1an设为第m部分，计算最大值和最小值 for j:=i to n do if (i1) or (jn) then begin if(g1,i-1+gj+1,n) mod mask*fmax1i,jmaxthen max:=(g1,i-1+gj+1,n) mod mask*fmax1i,j; if(fmin1i,j=0) and (g1,i-1+gj+1,n) mod mask*fmin1i,jmin)then min:=(g1,i

60、-1+gj+1,n) mod mask*fmin1i,j; end;then writeln(min); writeln(max);输出最小值和最大值第66页，共227页，2022年，5月20日，16点36分，星期一栈（Stack.pas） 【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。【问题描述】第67页，共227