|
第十一届全国青少年奥林匹克信息学联赛复赛提高组试题及测试数据
新增解题报告，由[酷叶] 提供
新增薛原、芙蓉哥哥解题报告，由[酷叶] 提供
测试数据：http://www.shzx.net.cn/cms/oi/shiti/2005fstdata.rar
薛原的解题报告：(这份报告叙述的二四题值得推荐)是薛原大牛的告别之作。http://www.shzx.net.cn/cms/oi/shiti/NOIP2005byXueyuanReport.rar
芙蓉哥哥的解题报告(第一题太简单没写，第三题叙述得相当详细。):http://www.shzx.net.cn/cms/oi/shiti/NOIP2005byFuRongReport.rar
（提高组 三小时完成）
谁拿了最多奖学金
(scholar.pas/c/cpp)
【问题描述】
某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：
1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；
2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得；
3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得；
4) 西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得；
5) 班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；
只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。
现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。
【输入文件】
输入文件scholar.in的第一行是一个整数N（1 <= N <= 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。
【输出文件】
输出文件scholar.out包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。
【样例输入】
4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1
【样例输出】
ChenRuiyi
9000
28700
过河
(river.pas/c/cpp)
【问题描述】
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
【输入文件】
输入文件river.in的第一行有一个正整数L（1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【输出文件】
输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。
【样例输入】
2 3 5 6 7
【样例输出】
2
【数据规模】
对于30%的数据，L <= 10000；
对于全部的数据，L <= 109。
篝火晚会
(fire.pas/c/cpp)
【问题描述】
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1, b2,... bm -1, bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？
【输入文件】
输入文件fire.in的第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。
【输出文件】
输出文件fire.out包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。
【样例输入】
4
3 4
4 3
1 2
1 2
【样例输出】
2
【数据规模】
对于30%的数据，n <= 1000；
对于全部的数据，n <= 50000。
等价表达式
(equal.pas/c/cpp)
【问题描述】
明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？
这个选择题中的每个表达式都满足下面的性质：
1． 表达式只可能包含一个变量‘a’。
2． 表达式中出现的数都是正整数，而且都小于10000。
3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）
4． 幂指数只可能是1到10之间的正整数（包括1和10）。
5． 表达式内部，头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子：
((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……
【输入文件】
输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2 <= n <= 26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……
输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。
【输出文件】
输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。
【样例输入】
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a
【样例输出】
AC
【数据规模】
对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’；
对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。
对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。
NOIP2005信息学奥林匹克分区联赛
解题报告
OIBH.KuYe.Cn [麓山NOI战队]
第一题：谁拿了最多的奖学-Scholar
[问题评估]
这个题目据问题本身而言是相当简单的，没有牵涉到过多的算法，属于普及型试题。同时也是对实际问题一种分析和判断。总的来看，本题在方向上，向现实问题迈出了一步，是信息学和生活有了更多的联系。
问题的算法是模拟。当中唯一的难点就是数据处理，考察点为数据库的建立和统计。
[程序实现]
由于程序数据范围只有100，当中不牵涉到数据移动，所以用一个纪录型数组，或者多个数组均可，在这里我们使用纪录型来描述。
对于输入数据有两种方式来实现。
法一〉逐个字符累加。
首先定义C:char; 然后利用Until c=‘ ’;作为终止符，将读入的字符连接存储到a[i].name中。
代码为：
Repeat read(c); a[i].name:=a[i].name+c; until c=’ ‘;
a[i].name:=copy(a[i].name,1,length(a[i].s)-1);
这样做的好处是，后面的值可以直接用read语句读入。但是最后一个值后，要记得readln;
法二〉一次读入,然后分离。
这样做需要逐个分离，对本题来说稍显复杂，但对NOIP来说此方法必须掌握，有的时候一定要用。
具体实现，读入一个字符串S。利用pos(‘ ‘,s);找出空格位置。再利用Copy函数，和Val函数进行截取，和转换。
部分代码：(s:string;j,ok:integer)
readln(s);
j:=pos(‘ ‘,s);
a[i].name:=copy(s,1,j-1);
s:= copy(s,j+1,50); //当长度〉字符串长度是，为后面全部截取。
j:=pos(‘ ‘,s);
Val(copy(s,1,j-1),a[i].qp,ok);
s:= copy(s,j+1,50);
…..
对于符号用if语句作一下判断就是了，太easy不写了，后面还有几个值，用同样方法处理就可以了。
以上完成了数据库的建库工作，后面是统计，当然，我们在没读完一行数据后就可进行统计。用If语句判断他是否能得到相应的分值即可。分5条If语句写，每回可以就加入相应的分值。
将每个的分值汇总计入到总数变量ZD当中。与当前最大值进行比较，得到Max对应的I值。后面就是输出的问题了。
[小结、注意]
本题为简单题，只要思路明确清晰，就可AC。时间复杂度O(n)。但有一个细节，ZD变量必须定义Longint或以上类型否则会Error201的。
第二题 过河-River
[问题分析]
此题初看是一个典型的搜索题。从河的一侧到河的另一侧，要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。
如果搜索石子，方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划，以石子分阶段的一维动规，时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律，而且会有后效性。
这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索，然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。[批注：号称一词已成为湖南OI本世纪流行词汇 ]
[题目实现]
先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值(109)，石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地)，处理时把这些跳过，就只会有M次运算。关键是找出每一个可以跳过的“空长条”。
我们可以先把青蛙可以跳出的所有可能求出，然后就可以求出可以忽略的“空长条”。
[特殊算法]
a[i]:前i个坐标中石子最小个数,初始为第i个坐标的石子个数
b[i]:第i个石子坐标
动规
a[0]=0;
对n>=t
a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}
对s=<n<t
a[n]=max{a[n]+a[n-s],a[n]+a[n-s-1],...,a[n]+a[0]}
但由于n较大直接动规会超时。所以要将n压缩
查看坐标，可以发现，如果b[i]-b[i-1]>t，显然对于b[i-1]+t<n<b[i]，a[n]总是等于a[b[i-1]]..a[b[i-1]+t]中的数，因此可对其进行压缩。
注意，在计算过程中，由于其中有一些坐标是永远走不到的，因此需要用一个布尔型的数组c[n]进行判断。方法是，对于c[n],如果0<n<s,则c[n]为false，如果n>s,c[n-t],c[n-t+1],...,c[n-s]都为false,则c[n]也为false。
第三题 篝火晚会-fire
[问题评估]
此题或许大多数人会觉得很麻烦。或许有人会选择搜索来做，显然，50000的数据量不可能允许搜索不超时。或许有人会用贪心，但是却无从下手。
动态规划？怎么划阶段更是一个难题。然而，此题却不是考察选手的算法的，而是考察你从题目中找出基本核心的能力。
[题目实现]
题目给你的初始状态是一个回路，从第一个同学前断开，不难看出这是一个严格的上升序列。而输入的数据也可以将之构成一个包含所有同学的回路，否则就达不到没个人的愿望。
我们可以用两的数组来储存两个数组的状态，初始状态为st，目标状态为en。st[i]=i,
i<=n。而输入数据我门可以先用一个二维E数组储存，E[I，1]即表示第I 个人的第一个愿望。我们将目标状态数组en的第一个元素赋值为1，然后就可以把s[1]的第一个愿望加入数组为s[2]，依次我们可以逐个加入，加入没个元素的时候，还要判断一下每个元素是否在数组当中，如果在，那就取第2个愿望。如果第二个愿望也在数组当中，那么我们的目标状态的数组也就构造完成了。
如果每个人的愿望都能实现，显然，目标状态的数组的元素必定是N，而假如不是，那么就可以输出-1了。
此时，问题就显的简单些了，如何让一个数组从一中状态变成另一种状态，相信有很多方法，可还是个麻烦事。
从目标状态转换成初始状态的步数是等同于初始状态转换成目标状态，而此时再看看初始状态的数组，相信你已经看出些疑端了吧！
排序！！！
对，其实从目标状态转换成初始状态的过程就是一个排序的过程，而且还是一个最简单的冒泡排序的过程！
到了这了，问题已经明了了，题目所求就是每次进行连续交换的人数总和，这样，一个看似复杂的题目就变的异常的简单了！而题目2秒的时间限制更是保证了冒泡排序经过一些优化以及剪枝后不会超时。
但是，千万不能用其他的排序法来解决。虽然能让你的程序变的更快，却同时你也得不正确的解！
第四题 等价表达式-Equal
[问题分析]
这道题目拿到手后，一般可以想到的方法就是可不可以将所有的表达式全部转化为最简形式，这时，你就想到了一种一般的解决方案。即将所有的表达式全部化为最简，然后再计算，这种方法是一种准确的方法。但要在考场上实现，有一些麻烦，需要一些时间。这种方法的解决过程是：先将阶乘化乘，再展开。计算同时合并同类项，留下一个数组。然后比较每一个表达式的数组与题目数组是否相同，时间效率也并不高。那么怎么办呢？
[模型建立和实现]
我们这里介绍一种利用必要条件的解决方案。
| 
