信息学奥赛教程指导.ppt

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 :array1.3 of string=(F,E,)； 匹配情况的标志 var want:string； 待匹配单词 list:array1.100 of string； 字典表。其中listi为字典i a

10、ns ：array1.100 of integer；单词的类别序列。其中 ansi= ,1、匹配情况的计算 计算两个等长字串中不同字符的个数 function find(a,b:string):integer；输入两个等长字串a,b，计算和返回不同字符的个数 vari,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 vari: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中的插入字符 en

12、d；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 对字典中的每个单词进行分类 if

13、 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 che

14、ck(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 beginb

16、b+1；ss+1/b； end；while 输出项数round(b)； end.main,第三题：选数,已知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，kn） x1,x2,xn（1xi50000

17、00） 输出： 输出文件名为c.out。文件格式 一个整数（满足条件的种数）。 输入输出样例： 输入： 4 3 7 12 19 输出： 1,1、判别一个数是否为素数 由于整数xi的上限为5000000，k的上限为19，这就使得判别k个整数的和是否为素数的问题变得似乎有点困难。为了保证在该范围内能正确出解，我们首先通过筛选法，将110000间的素数存入素数表prime。设 var map:array1.10000 of boolean；筛 prime:array1.5000 of longint；素数表。其中第i个素数为primei list:array1.20 of longint；待选数字集

18、合。其中listi为xi tot,ans:longint；tot为素数表的长度；和为素数的组合的个数为ans 构造素数表prime的过程如下： tot0； 素数表的长度初始化 fillchar(map,sizeof(map),true)；初始时所有数在筛中 for i2 to 10000 do 顺序搜索筛中的最小数i if mapi then begin for j2 to 10000 div i do mapi*jfalse；将i的倍数从筛中删去 inc(tot)；primetot i；i进入素数表 end；then,我们在素数表prime的基础上判别某数a是否为素数。任何数都可以分解成素因

19、子的乘积形式。按照递增方向将prime表中的每一个素数去试除a。若某个素数能被a整除，则说明a为合数；若primei*primeia，则说明a不可能分解出比primei大的素数了，a本身为素数。由于primei表的最大素数接近10000，其平方远大于xi的上限5000000，因此是一个比较可行的方法： function check(a:longint):boolean； 判断a是否是素数 begin checktrue； 素数标志初始化 for i1 to tot do begin 搜索素数表 if primei*primeia then exit；若超出搜索范围的上限，则说明a是素数，返回t

20、rue if a mod primei=0 then begin checkfalse；exit；end；then end；for end； check ,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)； 由此得出子程序,Procedure solve(left,now,all:longint)；递归计算选数情况 begin if (leftn-now+1)then exit；若xnowxn中不足left个数，则回溯 if (left=0) and (now=n+1) 若从x1xn中选出了k个数 then begin if check(all) then inc(a

22、ns)；若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即为问题的解。,过河卒,如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。,同时在棋盘上的任一点有一个对方的马（如上图的C点）,该马所在的点和所有跳跃一步可达的点称为对方马的控制点

23、。例如上图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 2 2 输出：0,1、计算对方马的控制点 按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控

24、制点。显然，若（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 comp；路径数序列，其中listi,j为卒从(0,0)到(i,j)的路径数 can:array0.20,0.20 of boolean； 点(i,j)允许卒通行的标志 马的初始位置为（x,y）。我们按照下述方式计算can序列： ca

25、nx,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；for if (not can0,0)or(not cann,m) 若卒的起点和终点为控制点，则输出路径数0 then writeln(0) else begin 计算和输出卒从（0，0）走到（n,m）点的路径数listn,m；en

26、d；else,2、计算和输出卒从（0，0）走到（n,m）点的路径条数 我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,j）(0in，0jm)设为阶段,显然这样做，可以取消对状态的枚举。 首先，将卒的出发点（0，0）的路径数设为1（list0,01），并将该位置设为控制点（can0,0 fals）。然后从（0，0）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数。若（i，j）为可行点，则卒可由上侧的（i-1,j）和左侧的（i,j-1）进入该点。将这两点的路径数加起来，即为从（0，0）走到（i，j ）的路径数，即 listi,j=listi-1,j+listi,j-

27、1（i，j）非控制点 依次类推，最后得出的listn,m即为问题的解。由此得出算法： fillchar(list,sizeof(list),0)； 路径数序列初始化 list0,01；卒从（0，0）出发的路径数为1，该位置不再允许卒通行 can0,0 false； for i0 to n do对于每个可行点,小兵要么从左侧、要么从上方走到,由此计算从(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；,题一 均分纸牌 问题描述 有N堆纸牌，

28、编号分别为1，2，.N。每堆上有若干张， 但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-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 堆纸牌，

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

30、堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(listi+1-(ave-listi)0 )的情况，这时可以理解为一个“先出后进”的栈。由于纸牌的总数是n的倍数，因此后面的堆会补充第i+1堆ave-listi-listi+1+ ave张纸牌，使其达到均分的要求。,第四堆补充第三堆,第三堆补充第二堆,第二堆补充第一堆,在枚举分牌方案时，是否可以利用上述计数方法呢？,题二 字串变换 问题描述：已知有两个字串A$，B$及一组字串变换的规则： A1$B1$ A2$B2$ 规则的含义为：在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$.。例如： A$ =abcd B$=x

31、yz 变换规则为： abcxu udy yyz 则此时，A$可以经过一系列的变换变为B$，其变换的过程为： abcdxudxyxyz 共进行了三次变换，使得A$变换为B$。,输入：输入文件名为A.in。文件格式如下： A$，B$ A1$ B1$ A2$ B2$ 变换规则 所有字符串长度的上限为255。,输 出：输出文件名为A.out。若在30步（包含30步）以内能将A$变换为B$，则向A.out输出最少的变换步数；否则向A.out输出ERROR！。 输入输出样例 A.in文件： abcd,xyz abc-xu ud-y y-yz,A.out文件： 3,1、分析变换规则 设 规则序列为rule，

32、其中第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)255 rulei,1是now的一个子串（k=pos(rulei,1,tmp)0）,在使用了第i条规则后，now变换为 now= copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rule

33、i,1),255) 由于now中可能有多个子串被第i条规则替换，因此每替换一次后，为了方便地找出下一个替换位置，我们将当前被替换串前（包括被替换串）的子串删除。,2、使用回溯法计算最少替换次数 由于原串a、目标串b和规则rule是随机输入的，因此不可能找出直接计算最少替换次数best的数学规律，只能采用回溯搜索的办法。设 状态（need,now）:替换次数为need，替换结果为now； 边界条件（needbest）和目标状态（now=b）：替换次数达到或超过目前得出的最小值为边界；已经替换出目标串为目标状态； 搜索范围i：尝试每一条规则,即1i规则数n； 约束条件（length(now)+le

34、ngth(rulei,2)-length(rulei,1)255）：now中的子串被第i条规则替换后的长度小于255； 由此得出计算过程：,procedure solve(need；now)；从当前串now出发，递归第need次替换 var i,k,j:integer； tmp:string； begin if need=best then exit； 若到达边界，则回溯 if now=b then begin若达到目标状态，则记下替换次数，并回溯 bestneed； exit； end；then for i1 to n do 搜索每一条规则,if length(now)+length(rul

35、ei,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；then end； solve ,由此得出主程序： 读入初始串a和目标串； 读入替换规则rule； best31； 设定替换次数的上限 solv

36、e(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 前进。如下图： 小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。请你计算出小车能接受到多少个小球。 输入：

37、H，S1，v，L，k，n （1H，S1，v，L，k，n100000） 输出：小车能接受到的小球个数。,这是分区联赛最容易失误的一道试题，关键是弄清小车行程的物理意义和计算的精度误差！,算法分析 由题意可知，车顶与天花板的距离为h-k，小球由天花板落至车顶所花费的时间为t1= ，由天花板落至地面的时间为t2= 。小车与所有小球同时开始运动，当小球距小车的距离0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。,显然，若n1n2，则小车接受的小球数为n1-n2+1；否则小车未接受任何一个小球。,小车在行驶了t1*v-0.00001路程后接受了第一个小球，其编号为n1=minn-1,

38、 ,小车在行驶了t2*v+0.00001路程后小球落地，小车接受最后一个小球的编号为n2=max0， 。,为什么在n1的公式中加上L？为什么在n2的公式中加上0.5？为什么n1取下整、n2取上整？,矩形覆盖 问题描述：在平面上有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 给出后，怎样才能使得覆盖所有点

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

40、形 设目前最小矩形的四条边界为maxx，maxy，minx，miny。如何按照面积最小的要求将a点加入矩形呢？显然需要调整边界线，使a点位于对应的边界线上。,初始时，我们设最小矩形为空，即左边界left为、右边界right为-、下边界top为、上边界bottom为-。然后由左而右，依次往矩形放入n个点，调整对应的边界线。最后得出的矩形为最小矩形，其面积为（右边界-左边界）*（上边界-下边界）,3、计算覆盖所有点的两个面积和最小的独立矩形,我们称彼此完全分开的矩形是独立的。两个覆盖所有点的独立矩形有两种形态：,我们将覆盖x轴左方点集a1,1.j的最小独立矩形存入tac1,j；将覆盖x轴右方点集a

41、1,j.n的最小独立矩形存入tdc1,j；将覆盖y轴下方点集a2,1.j的最小独立矩形存入tac2,j；将覆盖y轴上方点集a2,j.n的最小独立矩形存入tdc2,j（注意：当k=3时，对应的点集不包括被矩形1覆盖的点（1j n ）。,Tac1,j-1,Tdc1,j,Tac2,j-1,Tdc2,j,为什么一定要考虑两个轴向,如果仅考虑一个轴向的话,有什么反例?,问题是面积和最小的两个独立矩形究竟取哪一个形态，区分两个矩形的分界线j为何值，我们无法确定。不得已，只能将所有可能的情况枚举出来。设 var best，now:longint；两个独立矩形的最小面积和、当前方案中两个独立矩形的面积和 枚举

42、过程如下： 计算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 now(taci，j-1，1-taci，j-1，3)*(taci，j-1，2-taci，j-1，4

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

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

45、是三个独立矩形的面积和。问题是矩形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+nowbest

46、) then bestg+now；若三个独立矩形的面积和为目前最小，则记下 end；for 输出最小面积和best；,由此得出主程序： 读点数n和矩形数k； 读平面上的n个点； 分别沿x轴和y轴对n个点进行排序； case k of 1: 计算和输出覆盖所有点的一个最小矩形面积； 2: 计算和输出覆盖所有点的两个最小独立矩形的面积和； 3: 计算和输出覆盖所有点的三个最小独立矩形的面积和； end；case,如果k4，则算法将如何修改？,一、NOIP2003普及组复赛试题,题一、乒乓球（Table.pas） 【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动

47、在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。 【问题描述】华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。 比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：,WWWWWWWWWWWWWWWWWWWWWWLW 在11分制下，此时比赛的结果是华华第一局11比0获胜，第

48、二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。 你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。 【输入格式】每个输入文件包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。 【输出格式】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。,算法分析,首先，对当前输

49、入行计算11分制下每一局比赛的比分。设 a为当前局华华的得分，每输入一个W，a+1；b为当前局对方的得分，每输入一个L，b+1。若输入E或者华华的得分a或者对方得分b达到11分且双方的分数差值大于1（(a11) or(b11)and (abs(a-b)1)），则输出当前局的比分a：b。请注意，如果输入的字符为E，则标志比赛结束，11分制计算完毕；否则，继续读下一个字符，计算新一局的比分。然后，对当前输入行计算21分制下每一局比赛的比分。计算方法基本如上。有所不同的是，若华华得分a或者对方得分b达到21分且双方的分数差值大于1（(a21) or(b21)and (abs(a-b)1)），则输出当

50、前局的比分a：b。 按照上述方法对每一输入行计算11分制和21分制的比赛结果，直至文件读完（eof(input)）为止。,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若当前行处理完，则11分制的比赛结束 begin read(ch);读一个字符 case ch of根据字符的种类分情形处理,E: be

51、gin若比赛结束，则输出双方比分 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);,a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln; end; while a:=0; b:=0; 新一局的比分初始化 wri

52、teln; reset(input);重新读输入行 while not eof(input) do若文件未读完且比赛未结束，则循环 begin while not eoln(input) do若当前行处理完，则21分制的比赛结束 begin read(ch);读一个字符,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

53、(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);关闭输入文件和输出文件,数字游戏（Game.pas）,丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分

54、内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如，对于下面这圈数字（n=4，m=2）：,当要求最小值时，(2-1) mod 10)(4+3) mod 10)=17=7，要求最大值时，为(2+4+3) mod 10)(-1 mod 10)=99=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。 丁丁请你编写程序帮他赢得这个游戏。 【输入格式】输入文件第一行有两个整数，n（1n50）和m（1m9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。 【输出格式】输出文件有两行，各包含一

55、个非负整数。第一行是你程序得到的最小值，第二行是最大值。,算法分析,设圆周上的n个数字为a1、a2、an。按照模运算的规则（a1+a2+ +ak）mod 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；,fmax1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相

56、加，相加所得的p个结果对10取模后再相乘，最终得到最大数。显然，fmax11,i,j= gi，j； fmin1p,I,j为ai、ai+1、aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后再相乘，最终得到最小数。显然，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； 显然，状态转移方

57、程为 fmin1p,i,j= fmin1p-1,i,k*gk+1,j fmax1p,i,j= fmax1p-1,i,k*gk+1,j 2pm-1,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。,read(n,m);读数字个数和划分的部分数 fillchar(fmax1,sizeof(fmax1),0); fillchar(fmin1,sizeof(fmin1)

58、,$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:=gi,j; end;for for p:=2 to m-1 do阶段：递推计算划分2部分m-1部分的结果值 begin fillcha