1基础题和串运算重点课件

上海市控江中学王建德全国奥林匹克信息学联赛最近三年全国分区联赛复赛

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

题型

题型与课内知识和编程基础相关自由落体、级数求和、乒乓球、麦森数、不高兴的津津、花生采摘、津津的储蓄计划构造法均分纸牌、传染病控制、火星人数据结构字符近似查找、合并果子（堆排序）、栈、FBI树（二叉树）、神经网络（图）枚举法虫食算、侦探推理回溯法选数、字串变换动态程序设计方法过河卒、数字游戏、加分二叉树、合唱队形

几何计算矩形覆盖特点

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

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

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

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

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

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

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

输入

键盘输入 k

输出

屏幕输出 n

输入输出样例

输入: 1

输出: 2

算法分析

该题考核选手的并不是编程能力，而是选择变量类型的能力。由于该数列是递减的，而k的上限为15，因此项数很大，即便是longint也容纳不下。但未必非高精度运算不可。只要启动浮点数运算（{$n+}），将项数设为extended类型，便可以得出正确解。{$n+}{启动浮点数运算}vars,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}关键是s的类型。如果设为string，则增加了编程难度；如果设为除extended外的其它类型，则会失分！乒乓球（Table.pas）【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

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

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

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

算法分析

首先，对当前输入行计算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)）为止。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);

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);{读一个字符}

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);{关闭输入文件和输出文件}关键是文件操作。如果在计算21分制的得分前，不会通过reset(input)将读头移到文件首，则会出错！串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。长度为零的串称为空串，它不包含任何字符。串运算1.连接运算——函数concat(s1，[，s2，…，sn])：其中值参s1，‥，sn为string类型，函数值为string类型。若连接后的串长大于255，则自动截断超出部分。2.求子串——函数copy(s，i，l)：其中值参s为string类型，i和l为integer类型。函数返回s串中第i个字符开始、长度为l的子串（string类型）。若i大于s的长度，则回送一个空串；若l大于第i个字符开始的余串长度，则仅回送余串。3.删子串——过程delete(vars，i，l)：其中变量参数s为string类型，值参i、l为ingteger类型。该过程删去s中第i个字符开始的长度为l的子串，并返回剩余串s。若i大于原串s的长度，则不删任何字符；若l大于第i个字符开始的余串长度，则删去余串。在串运算中充分利用系统的库函数4.插入子串——过程insert(s1，vars，i)：变量参数s为string类型，值参s1为string类型。该过程将s1子串插入空串s的第i个字符位置处，并返回插入后的结果s。若插入后s的串长大于255个字符，则截断超出部分。5.求串长——函数length(s)：值参s为string类型。该函数返回s串的实际长度值（integer类型）。6.搜索子串位置——函数pos(s1，s2)：值参s1和s2为string类型。若s1是s2的一个子串，则返回s1中第1个字符在s2串中的位置（integer类型）；若s1非s2的一个子串，则返回0。7.数值转换为数串——过程str(x，vars)：值参x为integer类型或real类型，变量参数s为string类型。该过程将返回数值x对应的数串s。

8.数串转换为数值——过程val(s，varv，varc)：值参s为string类型，变量参数v为integer类型或real类型，变量参数c为integer类型。该过程试将s串转换成数值v。若转换成功，则c为0，并返回对应的数值v；否则c为无效字符的序数。9.字符的大写转换——函数upcase(ch)：值参ch为char类型。该函数返回ch字符的大写体（char类型）数码排序设有n个正整数，将他们连接成一排，组成一个最大的多位整数.例如：n=3时，3个整数13，312，343，连成的最大整数为：34331213。又如：n=4时，4个整数7，13，4，246连接成的最大整数为7424613。程序输入：N N个数程序输出：连接成的多位数

由于连接后的字串长度不变，我们可以利用字符串的大小顺序和十进制的进位关系，对n个数串s进行排序fori←1ton-1do{顺序排定s1…sn-1}forj←i+1tondoifs[i]+s[j]<s[j]+s[i]thenbegins1←s[i]；s[i]←s[j]；s[j]←s1；end；{then}fori←1tondowrite(s[i])；{输出最大的多位整数}字符串编辑

从键盘输入一个字符串(长度≤40个字符)，并以字符’.’结束.例如：’Thisisabook.’，现对该字符串进行编辑，编辑功能有：D：删除一个字符，命令的方式为：Da。其中a为被删除的字符。例如：Ds表示删除字符’s’，若字符串中有多个’s’，则删除第一次出现的，如上例中删除的结果为’Thiisabook.’I：插入一个字符，命令的格式为：Ia1a2。其中a1表示插入到指定字符前面，a2表示将要插入的字符。例如：Isd表示在指定字符’s’的前面插入字符’d’，若原串中有多个’s’，则插入在最后一个字符的前面。如上例中，原串：’Thisisabook.’，插入后：’Thisidsabook.’R：替换一个字符，命令格式为：Ra1a2。其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1，则应全部替换。例如：原串：’Thisisabook.’。输入命令：Roe，替换后：’Thisisabeek.’。在编辑过程中，若出现被指定的字符不存在时，则给出提示信息设s—原串和目标串；que—命令串。其中que[1]为命令字，que[2]和que[4]为空格。que[3]和que[5]的定义如下：在D命令中，que[3]为被删字符；在I命令中，que[3]为插入位置字符，que[5]为被插入字符；在R命令中，que[3]为被替换字符，que[5]为替换字符；删除操作：字串S中寻找que[3]。若找不到，则失败退出；否则，将该字符删去：i←pos(que[3]，s)；ifi=0thenbeginwriteln(’Error!’)；halt；end{then}elsedelete(s，i，1)；插入操作：从S串尾出发，由右而左寻找que[3]字符的位置。若找不到，失败退出；否则将que[5]字符插在该位置前

i←length(s)；{由右而左寻找que[3]字符的位置i}while(i>0)and(s[i]≠que[3])doi←i-1；ifi≠0theninsert(que[5]，s，i){将que[5]字符插在i位置前}elsebeginwriteln(’Error!’)；halt；end；{else}替换操作：从串首出发，由左而右寻找que[3]字符的位置。若找不到，失败退出；否则将que[5]替换所有的que[3]字符：error←true；fori←1tolength(s)do{由左而右替换que[3]字符}ifs[i]=que[3]thenbeginerror←false；s[i]←que[5]；end；{then}iferrorthen{若找不到，失败退出}beginwriteln(’Error!’)；halt；end{then}主程序输入原串s和命令串que；caseque[1]of’D’：begin删除操作；end；{’D’}’I’：begin插入操作；end；{’I’}’R’：begin替换操作；end；{’R’}end；{case}输出s；字符近似查找设有n个单词的字典表（1≤n≤100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）：i：该单词在字典表中的序号；Ei：在字典表中仅有一个字符不匹配的单词序号；Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号；N：其他情况当查找时有多个单词符合条件，仅要求第一个单词的序号即可。输入文件

输入文件名为a.in，文件的格式如下：n（字典表的单词数）n行，每行一个单词待匹配单词输出文件

输出文件名a.out，格式如下：iEiFi其中i为字典表中符合条件的单词序号（1≤i≤n），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。输入输出样例输入1:5abcdeabcasdfasfdabcdaacdabcd输出1:4E5F1输入2:1ab输出2:0E0F0N我们将字典表中的单词分成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]=}1、匹配情况的计算⑴计算两个等长字串中不同字符的个数functionfind(a,b:string):integer；{输入两个等长字串a,b，计算和返回不同字符的个数}var i,tot:integer；begin tot←0； fori←1tolength(a)doifa[i]<>b[i]theninc(tot)； find←tot；end；{find}

⑵判别一个字串是否比另一个字串多一个字符（其余字符匹配）我们不知道长度大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