信息学奥赛教程指导

信息学奥赛教程指导第1页，课件共227页，创作于2023年2月6、2002、2003年分区联赛复赛试题解析1、高精度运算2、图的运算3、搜索算法4、构造算法5、动态程序设计第2页，课件共227页，创作于2023年2月2002、2003年全国分区联赛复赛试题解析第3页，课件共227页，创作于2023年2月题

型题目与课内知识相关自由落体、级数求和、乒乓球、麦森数字符串处理字符近似查找贪心法均分纸牌、传染病控制回溯法选数、字串变换、栈、神经网络、侦探推理动态程序设计方法过河卒、数字游戏、加分二叉树几何计算矩形覆盖

虽然2002、2003年全国奥林匹克信息学复赛中含许多可“一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为

第4页，课件共227页，创作于2023年2月特点

1、凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力，激发学生的创造力，2002、2003年全国奥林匹克信息联赛(NOIP)中学科类的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与学科的依赖关系日益凸现，学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势（按照2005年国家教改方案，数学教材增加算法内容，信息科技教材掺入语言知识）。2、“构造法”或贪心策略类试题的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质—知识是不断推陈出新的。第5页，课件共227页，创作于2023年2月3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(字串变换——回溯法中有字符串处理)，也找不到一个纯粹的数据结构问题（级数求和——需要为表达式的计算结果设计合适的数据类型），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；

4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得0分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。第6页，课件共227页，创作于2023年2月

1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）；

启示2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（

爱笛生小学三年级退学、比尔.盖茨大学三年级退学）第7页，课件共227页，创作于2023年2月学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。

3、参与活动的学生应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）第8页，课件共227页，创作于2023年2月学生的心理调适：我掌握的知识仅不过是沧海一粟(进取心)；固守错误的概念比一无所知更可怕（明智）；三人之行必有我师（谦虚）；知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作windows，人类基因工程）（现代意识）；前提条件：水平相当的同质成员或各有所长（包括数学知识、编程能力和思维方式等解题所需的各种因素）的异质成员是开展合作学习的组织基础；合作学习的效应：集思广益容易出好的算法；群体设计的测试数据相对全面；在群体活动中能比较客观的反映自己能力情况；每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性好、乐于帮助他人，并且善于取他人之长的学生（符文杰、张一飞等）。第9页，课件共227页，创作于2023年2月4、选手面对从未遇到过的挑战应调整好心态，不要急功近利，要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两次失误，也是砥砺之石，可从中汲取有益的经验和教训。“不是一番寒彻骨，哪得梅花扑鼻香”。第10页，课件共227页，创作于2023年2月题5、均分纸牌题6、字串变换题7、自由落体题8、矩形覆盖题1、字符近似查找题2、级数求和题3、选数题4、过河卒9、乒乓球

10、数字游戏

11、栈

12、麦森数

13、神经网络

14、侦探推理

15、加分二叉树

16、传染病控制第11页，课件共227页，创作于2023年2月第一题：字符近似查找设有n个单词的字典表（1≤n≤100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）：

i：该单词在字典表中的序号；

Ei：在字典表中仅有一个字符不匹配的单词序号；

Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号；

N：其他情况当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件

输入文件名为a.in，文件的格式如下：

n（字典表的单词数）

n行，每行一个单词待匹配单词

第12页，课件共227页，创作于2023年2月输出文件

输出文件名a.out，格式如下：

iEiFi其中i为字典表中符合条件的单词序号（1≤i≤n），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出1:4E5F1输入2:1ab输出2:0E0F0N第13页，课件共227页，创作于2023年2月我们将字典表中的单词分成3类：第1类：单词与待匹配单词多或少一个字符，其余字符匹配；第2类：单词仅有一个字符与待匹配单词不匹配；第3类：单词与待匹配单词完全匹配；设constnote:array[1..3]ofstring=('F','E','')；{匹配情况的标志}

varwant :string；{待匹配单词}list :array[1..100]ofstring；{字典表。其中list[i]为字典i}ans：array[1..100]ofinteger；{单词的类别序列。其中ans[i]=}第14页，课件共227页，创作于2023年2月1、匹配情况的计算⑴计算两个等长字串中不同字符的个数functionfind(a,b:string):integer；{输入两个等长字串a,b，计算和返回不同字符的个数}var i,tot:integer；begintot←0；fori←1tolength(a)doifa[i]<>b[i]theninc(tot)；find←tot；end；{find}

第15页，课件共227页，创作于2023年2月⑵判别一个字串是否比另一个字串多一个字符（其余字符匹配）我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。functioncheck(a,b:string):integer；{输入字串a,b。若b能够在a的基础上添加一个字符得到的话，则返回1；否则返回0}var i:integer；begincheck←0；fori←0tolength(a)dobegina←copy(a,1,i)+b[i+1]+copy(a,i+1,255)；{在a[i]后插入b[i+1]}ifa=b{若插入后两串相同，则成功退出}thenbegincheck←1；exit；end；{then}delete(a,i+1,1)；{删去a中的插入字符}end；{for}end；{check}

第16页，课件共227页，创作于2023年2月2、计算字典表中的每一类单词首先，我们依次计算每一个单词的类别序号Ø

在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为3；若两串仅有一个字符不同，则单词i的类别记为2；Ø

若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0；然后根据ans序列在字典表中依次搜索类别3‥类别1的单词，输出对应的单词序号。如果在字典表中不存在上述3种类别的单词，则输出‘N’。fillchar(ans,sizeof(ans),0)；{单词的类别序列初始化}fori←1tondobegin{对字典中的每个单词进行分类}iflength(list[i])=length(want){若单词i与待匹配单词等长}thenbegink←find(list[i],want)；{计算单词i与待匹配单词的不同字符个数}

ifk=0thenans[i]←3；{记下类别序号}ifk=1thenans[i]←2；

end；{then}第17页，课件共227页，创作于2023年2月{若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0} iflength(list[i])+1=length(want)thenans[i]←check(list[i],want)；

iflength(list[i])=length(want)+1thenans[i]←check(want,list[i])；

end；{for} have←false；{匹配情况存在的标志初始化} fori←3downto1dobegin{依次输出每一类别的单词在字典表最先出现的序号} k←0；

forj←1tondoifans[j]=ithenbegink←j；break；end；{then} have←haveor(k>0)；

writeln(note[i],k)；

end；{for}第18页，课件共227页，创作于2023年2月

第二题：级数求和

已知：Sn=1+1/2+1/3+….+1/n。显然当n.非常大的时候，Sn可大于任何一个整数K。现给出一个整数K（1≤K≤15），要求计算出一个最小的n，使得Sn>K。

输入

键盘输入 k

输出

屏幕输出 n

输入输出样例

输入: 1

输出: 2

第19页，课件共227页，创作于2023年2月算法分析

该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不下。但未必非高精度运算不可。只要启动浮点数运算（{$n+}），将项数设为extended类型，便可以得出正确解。{$n+}{启动浮点数运算}var s,b,k:extended；{数列的和、项数、最接近sn(大于sn)的整数值}begin s←0；{数列的和初始化} b←0；{项数初始化} readln(k)；{读最接近sn(大于sn)的整数值k} whiles<=kdo{若目前数列的和小于k，则项数b+1，计算sb}begin b←b+1； s←s+1/b；end；{while}

输出项数round(b)；end.{main}第20页，课件共227页，创作于2023年2月第三题：选数

已知n个整数x1,x2,…..xn,以及一个整数k(k<n)。从n个整数中任选k个整数组合相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3，7，12，19时，可得全部的组合为：

3+7+12=223+7+19=297+12+19=383+12+19=34。现在，要求你计算出和为素数的组合数有多少种。例如上例，只有一种组合的和为素数：（3+7+19=29）。第21页，课件共227页，创作于2023年2月输入输入文件名为c.in。文件格式

n,k（1≤n≤20，k<n）

x1,x2,…xn（1≤xi≤5000000）输出：输出文件名为c.out。文件格式一个整数（满足条件的种数）。输入输出样例：输入：

4371219

输出：

1第22页，课件共227页，创作于2023年2月1、判别一个数是否为素数由于整数xi的上限为5000000，k的上限为19，这就使得判别k个整数的和是否为素数的问题变得似乎有点困难。为了保证在该范围内能正确出解，我们首先通过筛选法，将1―10000间的素数存入素数表prime。设varmap:array[1..10000]ofboolean；{筛}prime:array[1..5000]oflongint；素数表。其中第i个素数为prime[i]}list:array[1..20]oflongint；{待选数字集合。其中list[i]为xi}tot,ans:longint；{tot为素数表的长度；和为素数的组合的个数为ans}构造素数表prime的过程如下：tot←0；{素数表的长度初始化}fillchar(map,sizeof(map),true)；{初始时所有数在筛中}fori←2to10000do{顺序搜索筛中的最小数i}ifmap[i]thenbegin forj←2to10000dividomap[i*j]←false；{将i的倍数从筛中删去}inc(tot)；prime[tot]←i；{i进入素数表}end；{then}第23页，课件共227页，创作于2023年2月

我们在素数表prime的基础上判别某数a是否为素数。任何数都可以分解成素因子的乘积形式。按照递增方向将prime表中的每一个素数去试除a。若某个素数能被a整除，则说明a为合数；若prime[i]*prime[i]>a，则说明a不可能分解出比prime[i]大的素数了，a本身为素数。由于prime[i]表的最大素数接近10000，其平方远大于xi的上限5000000，因此是一个比较可行的方法：functioncheck(a:longint):boolean；{判断a是否是素数}begincheck←true；{素数标志初始化}fori←1tototdobegin{搜索素数表} ifprime[i]*prime[i]>athenexit；{若超出搜索范围的上限，则说明a是素数，返回true} ifamodprime[i]=0thenbegincheck←false；exit；end；{then} end；{for}end；{check}

第24页，课件共227页，创作于2023年2月2、递归搜索方案数由于数列是随机和无序的，因此只能通过搜索的办法求解。设

状态(left,now,all)：目前组合为all，还需要从xnow‥xn中选出left个数；

约束条件(left≤n-now+1)：xnow‥xn中数的个数大于等于left；

边界条件（(left=0)and(now=n+1)）和目标状态（check(all)=true）：从x1‥xn中选出k个数为边界。在这种情况下，若k个数的和为素数，则满足条件的种数+1。到达边界后，应回溯；

搜索范围为两种选择：

当前组合不选xnow,递归计算子状态(left,now+1,all)；

在还有数需要选的情况下（left>0），xnow选入组合，递归计算子状态(left-1,now+1,all+list[now])；由此得出子程序第25页，课件共227页，创作于2023年2月Proceduresolve(left,now,all:longint)；{递归计算选数情况}beginif(left>n-now+1)thenexit；{若xnow‥xn中不足left个数，则回溯}if(left=0)and(now=n+1){若从x1‥xn中选出了k个数}thenbegin ifcheck(all)theninc(ans)；{若k个数的和为素数，则满足条件的种数+1}exit；{回溯} end；{then}solve(left,now+1,all)；{当前组合不选xnow,递归计算子状态} ifleft>0{在还有数需要选的情况下，xnow选入组合，递归计算子状态}thensolve(left-1,now+1,all+list[now])；end；{solve}显然，递归调用solve(k,1,0)后得出的ans即为问题的解。第26页，课件共227页，创作于2023年2月过河卒如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。

第27页，课件共227页，创作于2023年2月

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

输出：0第28页，课件共227页，创作于2023年2月1、计算对方马的控制点按照题意，对方的马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒不能通过对方马的控制点。在卒出发之前，必须计算对方马的所有控制点。显然，若（0，0）或（n,m）为控制点，则输出路径数为0。设constmove:array[1..8,1..2]ofinteger=((1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1))；{move[k，1..2]为马沿k方向跳跃一步的水平增量和垂直增量}varlist:array[-1..20,-1..20]ofcomp；{路径数序列，其中list[i,j]为卒从(0,0)到(i,j)的路径数}can:array[0..20,0..20]ofboolean；{点(i,j)允许卒通行的标志}马的初始位置为（x,y）。我们按照下述方式计算can序列： can[x,y]←false；{对方马所在的点为控制点}fori←1to8dobegin{从（x，y）出发，沿8个跳马方向计算控制点}j←x+move[i,1]；{计算i方向的跳马位置(j，k)}k←y+move[i,2]；

if(j>=0)and(k>=0)and(j<=n)and(k<=m){若（j,k）在界内，则为控制点}thencan[j,k]←false；end；{for}if(notcan[0,0])or(notcan[n,m]){若卒的起点和终点为控制点，则输出路径数0}thenwriteln(0)elsebegin计算和输出卒从（0，0）走到（n,m）点的路径数list[n,m]；end；{else}第29页，课件共227页，创作于2023年2月2、 计算和输出卒从（0，0）走到（n,m）点的路径条数我们按照由上而下、由左而右的顺序，将卒可能到达的每一个位置（i,j）(0≤i≤n，0≤j≤m)设为阶段,显然这样做，可以取消对状态的枚举。首先，将卒的出发点（0，0）的路径数设为1（list[0,0]←1），并将该位置设为控制点（can[0,0]←fals）。然后从（0，0）出发，按照由上而下、由左而右的顺序计算卒经过每一个可行点的路径数。若（i，j）为可行点，则卒可由上侧的（i-1,j）和左侧的（i,j-1）进入该点。将这两点的路径数加起来，即为从（0，0）走到（i，j）的路径数，即

list[i,j]=list[i-1,j]+list[i,j-1]∣（i，j）非控制点依次类推，最后得出的list[n,m]即为问题的解。由此得出算法：

fillchar(list,sizeof(list),0)；{路径数序列初始化}list[0,0]←1；{卒从（0，0）出发的路径数为1，该位置不再允许卒通行}can[0,0]←false；

fori←0tondo{对于每个可行点,小兵要么从左侧、要么从上方走到,由此计算从(0,0)到(i,j)的路径数}forj←0tomdoifcan[i,j]thenlist[i,j]←list[i-1,j]+list[i,j-1]；输出卒从（0，0）走到（n,m）点的路径条数list[n,m]；第30页，课件共227页，创作于2023年2月题一均分纸牌[问题描述]

有N堆纸牌，编号分别为1，2，….N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如N=4，4堆纸牌数分别为：①9②8③17④6移动3次可达到目的：从③取4张牌放到④（981310）→从③取3张牌放到②（9111010）→从②取1张牌放到①（10101010）。[输入]：N

（N堆纸牌，1≤N≤100）

A1，A2，….An(N堆纸牌，每堆纸牌初始数，1≤Ai≤10000)[输出]：所有堆均达到相等时的最少移动次数。[输入输出样例]第31页，课件共227页，创作于2023年2月输入：

498176

输出：

3设list为纸牌序列，其中list[i]为第i堆纸牌的张数（1≤i≤n），ave为均分后每堆纸牌的张数，即；ans为最少移动次数。我们按照由左而右的顺序移动纸牌。若第i堆纸牌的张数list[i]超出平均值，则移动一次(ans+1)，将超出部分留给下一堆，既第i+1堆纸牌的张数增加list[i]-ave；若第i堆纸牌的张数list[i]少于平均值，则移动一次(ans+1)，由下一堆补充不足部分，既第i+1堆纸牌的张数减少ave-list[i]；右邻堆取的牌第32页，课件共227页，创作于2023年2月问题是，在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(list[i+1]-(ave-list[i])<0)的情况，这时可以理解为一个“先出后进”的栈。由于纸牌的总数是n的倍数，因此后面的堆会补充第i+1堆ave-list[i]-list[i+1]+ave张纸牌，使其达到均分的要求。

第四堆补充第三堆第三堆补充第二堆第二堆补充第一堆在枚举分牌方案时，是否可以利用上述计数方法呢？第33页，课件共227页，创作于2023年2月题二字串变换[问题描述]：已知有两个字串A$，B$及一组字串变换的规则：

A1$→B1$A2$→B2$………规则的含义为：在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…..。例如：A$=‘abcd’B$=‘xyz’变换规则为：‘abc’→‘xu’‘ud’→‘y’‘y’→‘yz’则此时，A$可以经过一系列的变换变为B$，其变换的过程为：‘abcd’→‘xud’→‘xy’→‘xyz’共进行了三次变换，使得A$变换为B$。第34页，课件共227页，创作于2023年2月[输入]：输入文件名为A.in。文件格式如下：

A$，B$A1$→B1$A2$→B2$变换规则

………所有字符串长度的上限为255。[输出]：输出文件名为A.out。若在30步（包含30步）以内能将A$变换为B$，则向A.out输出最少的变换步数；否则向A.out输出‘ERROR！’。[输入输出样例]A.in文件：abcd,xyzabc->xuud->yy->yzA.out文件：

3第35页，课件共227页，创作于2023年2月1、分析变换规则设规则序列为rule，其中第i条规则为rule[i，1]→rule[i，2]；当前串为now，其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的，因此设j为now的指针，即从now的第j个字符开始匹配rule[i,1]。now适用第i条规则的条件是now中的子串被第i条规则替换后的长度小于255，即

length(now)+length(rule[i,2])-length(rule[i,1])≤255rule[i,1]是now的一个子串（k=pos(rule[i,1],tmp)≠0）在使用了第i条规则后，now变换为now=copy(now,1,j+k-1)+rule[i,2]+copy(now,j+k+length(rule[i,1]),255)由于now中可能有多个子串被第i条规则替换，因此每替换一次后，为了方便地找出下一个替换位置，我们将当前被替换串前（包括被替换串）的子串删除。第36页，课件共227页，创作于2023年2月2、使用回溯法计算最少替换次数由于原串a、目标串b和规则rule是随机输入的，因此不可能找出直接计算最少替换次数best的数学规律，只能采用回溯搜索的办法。设

状态（need,now）:替换次数为need，替换结果为now；

边界条件（need≥best）和目标状态（now=b）：替换次数达到或超过目前得出的最小值为边界；已经替换出目标串为目标状态；

搜索范围i：尝试每一条规则,即1≤i≤规则数n；约束条件（length(now)+length(rule[i,2])-length(rule[i,1])≤255）：now中的子串被第i条规则替换后的长度小于255；由此得出计算过程：第37页，课件共227页，创作于2023年2月proceduresolve(need；now)；{从当前串now出发，递归第need次替换}vari,k,j:integer；tmp:string；beginifneed>=bestthenexit； {若到达边界，则回溯}ifnow=bthenbegin{若达到目标状态，则记下替换次数，并回溯} best←need；exit；

end；{then}fori←1tondo{搜索每一条规则}

第38页，课件共227页，创作于2023年2月iflength(now)+length(rule[i,2])-length(rule[i,1])<=255thenbegin{若使用了第i条规则后，串长不会超过上限}j←0；tmp←now；{匹配指针初始化和待匹配子串初始化}k←pos(rule[i,1],tmp)；{尝试第i条规则}whilek>0do{反复在tmp中寻找子串rule[i,1]}beginsolve(need+1，copy(now,1,j+k-1)+rule[i,2]+copy(now，j+k+length(rule[i，1])，255))；{递归下一次替换}delete(tmp,1,k)；{将当前被替换串前（包括被替换串）的子串删除}j←j+k；{右移匹配指针}k←pos(rule[i,1],tmp)；{继续尝试第i条规则}end；{while}end；{then}end；{solve}第39页，课件共227页，创作于2023年2月由此得出主程序： 读入初始串a和目标串； 读入替换规则rule；

best←31；{设定替换次数的上限} solve(0,a)； {回溯搜索最少的替换次数} ifbest<=30{输出最少替换次数}thenwriteln(best)elsewriteln('ERROR!')；、第40页，课件共227页，创作于2023年2月题三自由落体[问题描述]:在高为H的天花板上有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（1≤H，S1，v，L，k，n≤100000）[输出]：小车能接受到的小球个数。

这是分区联赛最容易失误的一道试题，关键是弄清小车行程的物理意义和计算的精度误差！第41页，课件共227页，创作于2023年2月算法分析由题意可知，车顶与天花板的距离为h-k，小球由天花板落至车顶所花费的时间为t1=，由天花板落至地面的时间为t2=。小车与所有小球同时开始运动，当小球距小车的距离≤0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）。显然，若n1≥n2，则小车接受的小球数为n1-n2+1；否则小车未接受任何一个小球。

小车在行驶了t1*v-0.00001路程后接受了第一个小球，其编号为n1=min{n-1,}小车在行驶了t2*v+0.00001路程后小球落地，小车接受最后一个小球的编号为n2=max{0，}。为什么在n1的公式中加上L？为什么在n2的公式中加上0.5？为什么n1取下整、n2取上整？第42页，课件共227页，创作于2023年2月矩形覆盖[问题描述]：在平面上有n个点(n≤100)，每个点用一对整数坐标表示。例如：当n=4时，4个点的坐标分别为：p1(1，1)，p2(2，2)，p3(6，3)，p4(7，0)这些点可以用k个矩形(k<4)全部覆盖，矩形的边平行于坐标轴。如图一，当k=2时，可用如图二的两个矩形s1，s2覆盖，s1，s2面积和为4。问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0；各个矩形间必须完全分开（边线也不能重合）；

本试题是高中组复赛中最难的一道试题，对选手的几何基础和编程能力是一个比较严峻的考验。

第43页，课件共227页，创作于2023年2月算法分析

1、点和矩形的描述和关系

平面上的点由坐标（x,y）表示。由于计算过程是按照由下而上、由左而右进行的，因此我们按照x坐标递增的顺序和y坐标递增的顺序将n个点存入a序列。矩形由2条平行于x轴的边界线和2条平行于y轴的边界线围成。为了计算最小矩形的方便，我们将空矩形的左边界设为∞、右边界为设-∞、下边界设为∞、上边界设为-∞。第44页，课件共227页，创作于2023年2月2、计算覆盖所有点的一个最小矩形设目前最小矩形的四条边界为maxx，maxy，minx，miny。如何按照面积最小的要求将a点加入矩形呢？显然需要调整边界线，使a点位于对应的边界线上。初始时，我们设最小矩形为空，即左边界left为∞、右边界right为-∞、下边界top为∞、上边界bottom为-∞。然后由左而右，依次往矩形放入n个点，调整对应的边界线。最后得出的矩形为最小矩形，其面积为（右边界-左边界）*（上边界-下边界）第45页，课件共227页，创作于2023年2月3、计算覆盖所有点的两个面积和最小的独立矩形

我们称彼此完全分开的矩形是独立的。两个覆盖所有点的独立矩形有两种形态：

我们将覆盖x轴左方点集a[1,1..j]的最小独立矩形存入tac[1,j]；将覆盖x轴右方点集a[1,j..n]的最小独立矩形存入tdc[1,j]；将覆盖y轴下方点集a[2,1..j]的最小独立矩形存入tac[2,j]；将覆盖y轴上方点集a[2,j..n]的最小独立矩形存入tdc[2,j]（注意：当k=3时，对应的点集不包括被矩形1覆盖的点（1≤j≤n）。Tac[1,j-1]Tdc[1,j]Tac[2,j-1]Tdc[2,j]为什么一定要考虑两个轴向,如果仅考虑一个轴向的话,有什么反例?第46页，课件共227页，创作于2023年2月问题是面积和最小的两个独立矩形究竟取哪一个形态，区分两个矩形的分界线j为何值，我们无法确定。不得已，只能将所有可能的情况枚举出来。设varbest，now:longint；{两个独立矩形的最小面积和、当前方案中两个独立矩形的面积和}枚举过程如下：计算tac和tdc序列；

best←maxlongint；{最小矩形面积初始化}fori←1to2dobegin{依次分析x轴向和y轴向}k=3时顺序寻找i轴向上第一个未被矩形1覆盖的点j；

whilej≤ndo{枚举i轴向上所有可能的两个独立矩形，从中找出最佳方案}begin

记下i轴向上点j的坐标h；顺序寻找i轴向上最接近h点(k=3时，该点未被矩形1覆盖)的点j；

第47页，课件共227页，创作于2023年2月if点j存在并且k=2，或者k=3时以点j为分界线的左矩形和右矩形与矩形1没有交集

thenbeginnow←(tac[i，j-1，1]-tac[i，j-1，3])*(tac[i，j-1，2]-tac[i，j-1，4])+(tdc[i，j，1]-tdc[i，j，3])*(tdc[i，j，2]-tdc[i，j，4])；{则计算两个独立矩形的面积和}ifnow<bestthenbest←now；{若面积和为目前最小，则记下}end；{then}end；{while}end；{for}ifbest=maxlongint{若找不到的两个独立矩形}then返回失败标志-1else返回两个矩形的最小面积和best；end；{getans}

第48页，课件共227页，创作于2023年2月4、计算覆盖所有点的三个面积和最小的独立矩形

我们先枚举第一个矩形，该矩形覆盖x轴向上的点1、点i、点j、点h（1≤i≤n,i≤j≤n,j≤h≤n）,求出覆盖它们的最小矩形。该矩形的上边界、下边界、左边界和右边界分别记为bottom、top、left、right。显然其面积为(bottom-top)*(right-left)。我们将该矩形称为矩形1。那么，平面上还有哪些点未在矩形1内，这些点将被另外两个独立的矩形所覆盖。判断（x,y）是否在矩形1内的条件

(x≥left)and(x≤right)and(y≤bottom)and(y≥top)

判断矩形是否与矩形1相交的条件(min(x1,right)≥max(x2,left))and(min(y1,bottom)≥max(y2,top))第49页，课件共227页，创作于2023年2月我们在得出矩形1的基础上，直接调用上述算法计算与矩形1分开的另外两个独立矩形的面积和，加上矩形1的面积便是三个独立矩形的面积和。问题是矩形1究竟覆盖了哪些点才能得出最优解呢？我们无法得知。无奈之下，只能通过枚举法搜索所有的可能情况 fori←1tondo{枚举x轴向上三个点（点i、点j、点h）的所有可能组合}forj←itondoforh←jtondobegin

计算覆盖点1、点i、点j、点h的最小矩形（矩形1）的四条边界right、bottom、left、top；

now←(bottom-top)*(right-left)；{计算矩形1的面积}

计算未被矩形1覆盖的点集u；计算覆盖u且与矩形1不相交的两个独立矩形的最小面积和g；

if(g≥0)and(g+now<best)thenbest←g+now；{若三个独立矩形的面积和为目前最小，则记下}end；{for}

输出最小面积和best；

第50页，课件共227页，创作于2023年2月由此得出主程序：读点数n和矩形数k；读平面上的n个点；分别沿x轴和y轴对n个点进行排序；casekof1:

计算和输出覆盖所有点的一个最小矩形面积；2:

计算和输出覆盖所有点的两个最小独立矩形的面积和；3:

计算和输出覆盖所有点的三个最小独立矩形的面积和；end；{case}

如果k≥4，则算法将如何修改？第51页，课件共227页，创作于2023年2月一、NOIP2003普及组复赛试题

题一、乒乓球（Table.pas）【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

【问题描述】华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：第52页，课件共227页，创作于2023年2月WWWWWWWWWWWWWWWWWWWWWWLW在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。

【输入格式】每个输入文件包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。

【输出格式】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。

第53页，课件共227页，创作于2023年2月算法分析

首先，对当前输入行计算11分制下每一局比赛的比分。设a为当前局华华的得分，每输入一个‘W’，a+1；b为当前局对方的得分，每输入一个‘L’，b+1。若输入‘E’或者华华的得分a或者对方得分b达到11分且双方的分数差值大于1（((a≥11)or(b≥11))and(abs(a-b)>1)），则输出当前局的比分a：b。请注意，如果输入的字符为‘E’，则标志比赛结束，11分制计算完毕；否则，继续读下一个字符，计算新一局的比分。然后，对当前输入行计算21分制下每一局比赛的比分。计算方法基本如上。有所不同的是，若华华得分a或者对方得分b达到21分且双方的分数差值大于1（((a≥21)or(b≥21))and(abs(a-b)>1)），则输出当前局的比分a：b。按照上述方法对每一输入行计算11分制和21分制的比赛结果，直至文件读完（eof(input)）为止。第54页，课件共227页，创作于2023年2月assign(input,inp);reset(input);{输入文件读准备}assign(output,out);rewrite(output);{输出文件写准备}a:=0;b:=0;{

当前局双方的比分初始化}whilenoteof(input)do{若文件未读完，则循环}beginwhilenoteoln(input)do{若当前行处理完，则11分制的比赛结束}beginread(ch);{读一个字符}casechof{根据字符的种类分情形处理}

'E':begin{若比赛结束，则输出双方比分}writeln(a,':',b);break;{退出11分制的计算过程}end;{'E'}'W',’L’:begin{华华或对方得一分}ifch=’W’theninc(a)elseinc(b);if((a>=11)or(b>=11))and(abs(a-b)>1)then{若有一方得分达到11分且双方的分数差值大于1，则输出双方比分}beginwriteln(a,':',b);

第55页，课件共227页，创作于2023年2月a:=0;b:=0;{新一局的比分初始化}end;{then}end;{'W',’L’}end;{case}end;{while}readln;end;{while}a:=0;b:=0;{新一局的比分初始化}writeln;reset(input);{重新读输入行}whilenoteof(input)do{若文件未读完且比赛未结束，则循环}beginwhilenoteoln(input)do{若当前行处理完，则21分制的比赛结束}beginread(ch);{读一个字符}

第56页，课件共227页，创作于2023年2月casechof{根据字符的种类分情形处理}

‘E’:begin{若比赛结束，则输出双方比分，退出21分制的计算过程}writeln(a,':',b);break;end;{'E'}'W',’L’:begin{华华或对方得一分}ifch=’W’theninc(a)elseinc(b);if((a>=21)or(b>=21))and(abs(a-b)>1){若有一方得分达到21分且双方的分数差值大于1，则输出双方比分}thenbeginwriteln(a,':',b);a:=0;b:=0;{新一局的比分初始化}end;{then}end;{'W',’L’}end;{case}end;{while}readln;end;{while}close(input);close(output);{关闭输入文件和输出文件}第57页，课件共227页，创作于2023年2月数字游戏（Game.pas）

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如，对于下面这圈数字（n=4，m=2）：第58页，课件共227页，创作于2023年2月当要求最小值时，((2-1)mod10)×((4+3)mod10)=1×7=7，要求最大值时，为((2+4+3)mod10)×(-1mod10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。

【输入格式】输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。

【输出格式】输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。第59页，课件共227页，创作于2023年2月算法分析

设圆周上的n个数字为a1、a2、…an。按照模运算的规则（a1+a2+…+ak）mod10=(a1mod10+a2mod10+akmod10)mod10；g[i，j]为ai、ai+1、…aj的数和对10的模，即

g[i，j]=（ai+ai+1+…+aj）mod10显然

g[i，i]=（aimod10+10）mod10g[i，j]=(g[i,j-1]+g[j,j])mod10(1≤i≤n，i+1≤j≤n)当m=1时，程序得到的最小值和最大值为g[1,n]；第60页，课件共227页，创作于2023年2月fmax1[p,I,j]为ai、ai+1、…aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后再相乘，最终得到最大数。显然，fmax1[1,i,j]=g[i，j]；fmin1[p,I,j]为ai、ai+1、…aj分为p个部分，各部分内的数字相加，相加所得的p个结果对10取模后再相乘，最终得到最小数。显然，fmin1[1,i,j]=g[i，j]；(1≤p≤m)问题是当ai、ai+1、…aj划分成的部分数p大于1时，怎么办。我们采用动态程序设计的方法计算。第61页，课件共227页，创作于2023年2月设阶段p：划分成的部分数,2≤p≤m-1；状态（i，j）:将ai、ai+1、…aj划分成p个部分，1≤i≤n，i≤j≤n；决策k:

将ai、ai+1、…ak划分成p-1个部分，ak+1、…aj为第p部分，i≤k≤j-1；显然，状态转移方程为

fmin1[p,i,j]={fmin1[p-1,i,k]*g[k+1,j]}fmax1[p,i,j]={fmax1[p-1,i,k]*g[k+1,j]}2≤p≤m-1第62页，课件共227页，创作于2023年2月max=min=

由于p-1阶段仅和p阶段发生联系，因此我们将p-1阶段的状态转移方程fmin1[p-1,i,j]设为fmin1[i,j]、fmax1[p-1,i,j]设为fmax1[i,j]，将p阶段的状态转移方程fmin1[p,i,j]设为fmin[i,j]、fmax1[p,i,j]设为fmax[i,j]。第63页，课件共227页，创作于2023年2月read(n,m);{读数字个数和划分的部分数}fillchar(fmax1,sizeof(fmax1),0);fillchar(fmin1,sizeof(fmin1),$FF);{状态转移方程初始化}fillchar(g,sizeof(g),0);fori:=1tondo{依次读入每个数，一个数组成一部分}beginread(g[i,i]);g[i,i]:=(g[i,i]modmask+mask)modmask;min1[i,i]:=g[i,i];fmax1[i,i]:=g[i,i];end;{for}fori:=1tondo{计算一部分内的数和对10的模的所有可能情况}forj:=i+1tondo

beging[i,j]:=(g[i,j-1]+g[j,j])modmask;fmax1[i,j]:=g[i,j];fmin1[i,j]:=g[i,j];end;{for}forp:=2tom-1do{阶段：递推计算划分2部分…m-1部分的结果值}beginfillchar(fmax,sizeof(fmax),0);{划分p部分的状态转移方程初始化}fillchar(fmin,sizeof(fmin),$FF);

第64页，课件共227页，创作于2023年2月fori:=1tondo{状态：枚举被划分为p部分的数字区间}forj:=itondofork:=itoj-1do{决策：ai…ak被划分为p-1部分}beginiffmax1[i,k]*g[k+1,j]>fmax[i,j]{计算将ai、ai+1、…aj划分成p个部分的状态转移方程}thenfmax[i,j]:=fmax1[i,k]*g[k+1,j];

if(fmin1[i,k]>=0)and((fmin1[i,k]*g[k+1,j]<fmin[i,j])or(fmin[i,j]<0))thenfmin[i,j]:=fmin1[i,k]*g[k+1,j];end;{for}fmin1:=fmin;fmax1:=fmax;end;{for}max:=0;min:=maxlongint;{将a1、a2、…an划分成m个部分的最大值和最小值初始化}ifm=1{计算n个数划分成一部分的最大值和最小值}thenbeginmax:=g[1,n];min:=g[1,n];end{then}

第65页，课件共227页，创作于2023年2月elsefori:=1tondo{将a1…ai-1、aj+1…an设为第m部分，计算最大值和最小值}forj:=itondoif(i<>1)or(j<>n)thenbeginif(g[1,i-1]+g[j+1,n])modmask*fmax1[i,j]>maxthenmax:=(g[1,i-1]+g[j+1,n])modmask*fmax1[i,j];if(fmin1[i,j]>=0)and((g[1,i-1]+g[j+1,n])modmask*fmin1[i,j]<min)thenmin:=(g[1,i-1]+g[j+1,n])modmask*fmin1[i,j];end;{then}writeln(min);writeln(max);{输出最小值和最大值}第66页，课件共227页，创作于2023年2月栈（Stack.pas）

【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。【问题描述】第67页，课件共227页，创作于2023年2月宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）1113使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由123生成序列231的过程。（原始状态如上图所示）你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。第68页，课件共227页，创作于2023年2月【输入格式】输