解题报告.docx

《解题报告.docx》由会员分享，可在线阅读，更多相关《解题报告.docx（5页珍藏版）》请在第一文库网上搜索。

1、NOIP2005信息学奥林匹克分区联赛解题报告麓山NOI战队第一题：谁拿了最多的奖学-Scholar问题评估这个题目据问题本身而言是相当简单的，没有牵涉到过多的算法，属于普及型试题。同时也是对实际问题一种分析和判断。总的来看，本题在方向上，向现实问题迈出了一步，是信息学和生活有了更多的联系。问题的算法是模拟。当中唯一的难点就是数据处理，考察点为数据库的建立和统计。程序实现由于程序数据范围只有100,当中不牵涉到数据移动，所以用一个纪录型数组，或者多个数组均可，在这里我们使用纪录型来描述。对于输入数据有两种方式来实现。法一逐个字符累加。首先定义C:char;然后利用Until作为终止符，将读入的

2、字符连接存储到ai.name中。代码为：Repeat read(c); ai.name:=ai.nanic+c; until c=,ai.name:=copy(ai.name,l,length(ai.s)-l);这样做的好处是，后面的值可以直接用read语句读入。但是最后一个值后，要记得readln;法二一次读入，然后分离。这样做需要逐个分离，对本题来说稍显复杂，但对NOIP来说此方法必须掌握，有的时候一定要用。具体实现，读入一个字符串So利用pos(一,s);找出空格位置。再利用Copy函数，和Vai函数进行截取，和转换。部分代码：(s:string;j,ok:integer)readln(

3、s);j:=pos(：s);ali.name:=copy(s,l ,j-l);s:二copy(s,j+l,50);当长度字符串长度是，为后面全部截取。j:二pos(：s);Val(copy(s,l ,j-l),ai.qp,ok);s:= copy(s,j+l,50);对于符号用if语句作一下判断就是了，太easy不写了，后面还有几个值，用同样方法处理就可以了。以上完成了数据库的建库工作，后面是统计，当然，我们在没读完一行数据后就可进行统计。用If语句判断他是否能得到相应的分值即可。分5条If语句写，每回可以就加入相应的分值。将每个的分值汇总计入到总数变量ZD当中。与当前最大值进行比较，得到Ma

4、x对应的I值。后面就是输出的问题了。小结、注意本题为简单题，只要思路明确清晰，就可ACo时间复杂度0(n)。但有一个细节，ZD变量必须定义Longint或以上类型否则会Error201的。第二题过河-River问题分析此题初看是一个典型的搜索题。从河的一侧到河的另一侧，要找最少踩到的石头数。但从数据范围来看。1.109长度的桥。就算是O(n)的算法也不能在一秒内出解。如果搜索石子，方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划，以石广分阶段的维动规，时间复杂度是0(n2)。最多也只有100X100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律，而且会有后

5、效性。这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索，然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。批注：号称一词已成为湖南OI本世纪流行词汇题目实现先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值(109),石头数也为最大值(100)。这样中间一定会有很多“空长条”(两个石子中的空地)，处理时把这些跳过，就只会有M次运算。关键是找出每一个可以跳过的“空长条”。我们可以先把青蛙可以跳出的所有可能求出，然后就可以求出可以忽略的“空长条特殊算法ai:前i个坐标中石子最小个数，初始为

6、第i个坐标的石子个数bi:第i个石子坐标动规a0=0;对 n=lan=minan+an-s,an+an-s-l, .,an+an-t)对 s=ntan=max an+an-s,an+an-s-1 ,.,an+a0但由于n较大直接动规会超时。所以要将n压缩查看坐标，可以发现，如果显然对于bil+tvnvbi, an总是等于中的数,因此可对其进行压缩。注意，在计算过程中，由于其中有些坐标是永远走不到的，因此需要用个布尔型的数组cn进行判断。方法是,对于 cn,如果 0ns,c(n-t,cn-t+l cn-s都为 false,则 c叶也为 falseo第三题篝火晚会fire问题评估此题或许大多数人会

7、觉得很麻烦。或许有人会选择搜索来做，显然，5()000的数据量不可能允许搜索不超时。或许有人会用贪心，但是却无从下手。动态规划？怎么划阶段更是-一个难题。然而，此题却不是考察选手的算法的，而是考察你从题目中找出基本核心的能力。题目实现题目给你的初始状态是一个回路，从第一个同学前断开，不难看出这是一个严格的上升序列。而输入的数据也可以将之构成一个包含所有同学的回路，否则就达不到没个人的愿望。我们可以用两的数组来储存两个数组的状态，初始状态为st,目标状态为en。sti=i,i=no而输入数据我门可以先用一个二维E数组储存，EL 1即表示第I个人的第一个愿望。我们将目标状态数组cn的第-个元素赋值

8、为I,然后就可以把sl的第个愿望加入数组为s2,依次我们可以逐个加入，加入没个元素的时候，还要判断一下每个元素是否在数组当中，如果在，那就取第2个愿望。如果第二个愿望也在数组当中，那么我们的目标状态的数组也就构造完成了。如果每个人的愿望都能实现，显然，目标状态的数组的元素必定是N,而假如不是，那么就可以输出-1 了。此时，问题就显的简单些了，如何让一个数组从一中状态变成另一种状态，相信有很多方法，可还是个麻烦事。从目标状态转换成初始状态的步数是等同于初始状态转换成目标状态，而此时再看看初始状态的数组，相信你已经看出些疑端了吧！排序！ ！对，其实从目标状态转换成初始状态的过程就是一个排序的过程，

9、而且还是一个最简单的冒泡排序的过程！到了这了，问题已经明了了，题目所求就是每次进行连续交换的人数总和，这样，一个看似复杂的题目就变的异常的简单了！而题目2秒的时间限制更是保证了冒泡排序经过一些优化以及剪枝后不会超时。但是，千万不能用其他的排序法来解决。虽然能让你的程序变的更快，却同时你也得不正确的解！第四题等价表达式Equal问题分析这道题目拿到手后，般可以想到的方法就是可不可以将所有的表达式全部转化为最简形式，这时，你就想到了一种一般的解决方案。即将所有的表达式全部化为最简，然后再计算，这种方法是一种准确的方法。但要在考场上实现，有一些麻烦，需要一些时间。这种方法的解决过程是：先将阶乘化乘，

10、再展开。计算同时合并同类项，留下一个数组。然后比较每一个表达式的数组与题目数组是否相同，时间效率也并不高。那么怎么办呢？模型建立和实现我们这里介绍一种利用必要条件的解决方案。即两个表达式如果等价，那么无论a为何值，两个表达式计算出的值都相等。这时，我们以不同的a值代入各式，可以快速排斥那些不同的表达式，留下的便是等价的了。我们怎样取值呢？这里推荐几种有效的方法：1取随机函数生成的数列。这种方法比较有效，无规律。2取伪随机数列。这是一种比较便于人工控制的手段。3取实数。由于其他皆为整数，小数部分便成为判断的优越条件。般情况下取47组值便可通过极大部分情况，实数需要更小。如果取更多组的值，便可以通

11、过几乎所有的情况（将两式连立，只有当取值都为方程的解时才会出现误判，显然这样的几率是极小的）。补充：这道题可能会有选手在数据类型上选择不当，导致一些情况会出现溢出。表达式求值经过上面的叙述，难点落在了表达式求值上，在这里我们介绍下最般、最简单的方法，栈运算。用栈实现表达式求值的方法：首先，我们要给每一个符号一个优先级:符号+ -* /A()栈内级别24608栈外级别13580可以看到，优先级高的符号先算。为了方便起见，我们定义特殊符号#,它级别最低（赋-1）先将它置栈底，然后依次读入每个字符，如果是数字则入数栈。如果是符号，就与栈顶符号比较优先级。如果相等，则退栈，读下一字符。如果栈外大，则入

12、栈。如果栈内大，则取栈顶元素与数栈最顶2元素运算，结果入数栈。这个符号继续处理（再与栈顶比较）。直到读到最后符号#使栈底#出栈时。数栈顶即为表达式结果。由此，本题已经变得清晰了，剩下的就是具体将我们的表述变成代码。文档信息文章总排版、总发布：Qf-梁怦In麓山国际长郡集团第一题分析：Clf-梁炜In麓山国际长郡集团第二题分析：标准算法-Eastorn-李向东In麓山国际长郡集团特殊算法-Whb-吴海波In麓山国际长郡集团第三题分析：MaskCai-蔡湘In麓山国际长郡集团第四题分析：Lc-刘诚In麓山国际长郡集团鸣谢：我们的教练老师：王灿、周祖松，以及长郡中学所有老师。解题报告并非源程，这样更有助于思维的锻炼，第一题中的一些代码均是在Word中编写，如有语法错误，还请谅解。谢谢！NOI 战队2005-11-19