oip2005提高组解题报告(转).ppt

第一题：谁拿了最多奖学金,【问题描述】 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 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,这是一道标准的送分题（也称水题），算法就是纯粹的模拟。,算法分析：,这道题唯一值得一提的就是怎样存储数据。 从输入格式可以看出人名需要一个字符串来存储，成绩需要整型存储，剩下的需要字符来存储。由此可以想到用一个记录类型来存储是个不错的选择，当然，用5个数组来存储也是可以的。,存储结构：,接下来的就是一个一个数据来模拟算出第n个人可以得到的奖学金数，比较一下是否是最多的，然后在累计器上加上这个奖学金数。 最后按格式输出。（注意文末换行） 正如开始所说的，这是一道水题，是一定要拿满分的。,第二题：过河,【问题描述】 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。,输入格式 输入文件的第一行有一个正整数 L （ 1 = L = 109 ），表示独木桥的长度。第二行有三个正整数 S ， T ， M ，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中 1 = S = T = 10 ， 1 = M = 100 。第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 输出格式 输出文件只包括一个整数，表示青蛙过河最少需要踩到的石子数。,样例输入 ： 10 2 3 5 2 3 5 6 7 样例输出 ： 2 数据范围： 对于30%的数据，L = 10000； 对于全部的数据，L = 109。,如果要求出跳到第L个点踩到石子的最小值，就要涉及到两个量（1）.第L个点是否有石子；（2）.跳到第L-s个点第L-t个点（就是可以跳到L点的点）需要踩到的最少石子数。也就是说fL与fL-s,fL-s-1,fL-s-2，fL-t有关，由此很容易联想到使用动态规划。,算法分析：,依据题意可以得到DP状态转移方程为： fk-s fk-s-1 fk=max fk-s-2 + datak (石子数) fk-t 即: fk=maxfk-j+datak (s=j=t),但是仔细考虑一下如果把所有的点都算一下的话，时间复杂度为O（L*（t-s+1）,空间复杂度为O（L*2），当L=109时，无论是空间，还是时间，都无法承受。然而M却又t且l mod t0，那么我们就可以将第二个石子挪到以第一个石子为原点l mod t 的位置,即将第二个石子向前挪 （l div t）*t 个 位置，但是要注意：不光要挪动第二个石子，还要挪动后面的所有石子。,这是一个简单的优化，处理出来的数组数据量最多会比10000稍大一点，这样的话时间和空间便都可以优化了。但优化的方法也不只这一个，网上还有其他方法：比如在llcm(s,t)或l100+2*t进行压缩状态，其本质是一样的，这里就不再多提。,for k:=1 to m do begin ak:=ak-s; if (ak-ak-1-1)mod t0 then j:=(ak-ak-1-1)div t)*t else if ak-ak-1-1t then j:=(ak-ak-1-1)div t)-1)*t else j:=0; j用于记录第k个石子需要向前挪动的位置 ak:=ak-j; bak:=1; s:=s+j; s用于记录前面的k个石子一共向前挪动的位置 end;,注意事项： 注意题目中给的条件“当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。” 这是什么意思呢？ 就是说fL不一定是要求的结果，这个结果可以是fL+1,fL+2,.这到什么时候是个头呢？ 其实很简单，和上面压缩状态一样，只需找到min(fL+k) (0=kt)即可。,还要注意的一点是： 不要以为样例中给出的石子位置是升序的就忘了把石子数排序。,这不是一道非常简单的动规题，这道题用朴素的动态规划只能得到L=10000的30分，而加上压缩状态后就可以轻松AC，所以这一点技巧是应当掌握的。,第三题：篝火晚会,【问题描述】 佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有 n 个同学，编号从 1 到 n 。一开始，同学们按照 1 ， 2 ， n 的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。 佳佳可向同学们下达命令，每一个命令的形式如下： (b 1 , b 2 ,. b m -1 , b m ),这里 m 的值是由佳佳决定的，每次命令 m 的值都可以不同。这个命令的作用是移动编号是 b 1 ， b 2 ， b m 1 ， b m 的这 m 个同学的位置。要求 b 1 换到 b 2 的位置上， b 2 换到 b 3 的位置上，要求 b m 换到 b 1 的位置上。 执行每个命令都需要一些代价。我们假定如果一个命令要移动 m 个人的位置，那么这个命令的代价就是 m 。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？,输入格式 输入文件 的第一行是一个整数 n （ 3 = n = 50000 ），表示一共有 n 个同学。其后 n 行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是 1 的同学最希望相邻的两个同学的编号，编号是 2 的同学最希望相邻的两个同学的编号，编号是 n 的同学最希望相邻的两个同学的编号。 输出格式 输出文件 包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出 -1 。,样例输入 ： 4 3 4 4 3 1 2 1 2 样例输出 ： 2,刚开始看到这道题的时候我们可能会觉得无从下手，搜索的方法肯定超时动态规划？贪心？找不出思路但认真读题，再模拟样例，我们可以发现这道题就要是从一个起始状态转换到满足输入数据的目标状态，而结果正是这个状态转换过程中所要进行移动的最小次数。,算法分析：,起始状态： 所谓的起始状态便是1，2，3，n这n个节点组成的一个环，而这个环有n种正序读法，和n种倒序读法。 目标状态： 目标状态也是一个环，但我们最好把它转换成2*n条链，只要满足这些链的关系，便称为达到了目标状态。,构造起始状态： For t:=1 to n do begin at:=t; at+n:=t; end; 将环转换成链，枚举起点t，便可得到终点t+n-1的序列,构造目标状态： l1:=1; j:=1; bo1:=1; 初始化，构建起点为1的目标状态 l为记录目标状态的数组，bo判断某个节点是否在l中出现过 repeat if (alj,1lj-1)and(alj,2lj-1)and(j1) then 在此前需构造临接表 begin writeln(-1); halt; end; 如果某两个点之间不能满足相邻关系，就无法构成目标状态 for t:=1 to 2 do if boalj,t=0 then begin boalj,t:=1; inc(j); lj:=alj-1,t; break;找到一个可以相邻的点即可，即找到一个目标状态即可 end; until j=n; 得到一个目标状态以后，便可以像转化初始状态那样处理目标状态,认真分析佳佳的命令： (b 1 , b 2 ,. b m -1 , b m ) 这里并没有指这m个点必须是在一块的，只是说从原序列里找出了m个点进行交换，交换代价为m。 由此我们可以想到，如果起始状态和目标状态的某一位置是相同的数字，那么这个数字便可以不进行交换，也不计入代价；而若这一位置上的数字不是相同的数字，那么这个数字就必须进行交换来达到目标状态，这个交换的最小代价是1。 于是，我们的任务便是找出起始状态和目标状态之间的最小差异，这个差异便可以成为这种转换的最小代价。,For t:=1 to n do for x:=1 to n do begin j:=0; for k:=t to t+n-1 do if aklx+k-t then inc(j); if jmin then min:=j; end; 仔细分析一下这个代码只枚举了两种状态的正序读法，倒序还没有枚举，如果再加上倒序，时间复杂度就是O（2n*2n*n）,即O（4*n3），就算是稍加优化，固定某个状态，也只能优化到O（2*N2），如果代入50000的话，结果可想而知，最多过前3个点。所以这个算法仍需要优化！,究竟该怎么优化呢？ 这里我们通过一个例子来分析： 如初始环为1 2 3 4 5 6 7 8 9 10，目标环若为1 8 2 7 5 3 6 4 10 9，则可通过命令（1，8，10）使之变成8 2 3 4 5 6 7 10 9 1，再通过命令（7，4，5，3）使之变成8 2 7 5 3 6 4 10 9 1（这就是目标环），总代价为7。 上述的总代价7可以这样得出：由目标环可得到2*n个不同的目标序列， 即： 1 8 2 7 5 3 6 4 10 9、8 2 7 5 3 6 4 10 9 1、2 7 5 3 6 4 10 9 1 8、 7 5 3 6 4 10 9 1 8 2、5 3 6 4 10 9 1 8 2 7、及9 10 4 6 3 5 7 2 8 1 1 9 10 4 6 3 5 7 2 8、8 1 9 10 4 6 3 5 7 2、2 8 9 10 4 6 3 5 7、,由以上两个表格可以得出这个结论： 将目标环顺时针移动1步，或移动2步，3步时得到的结果是不一样的，但是拥有相同差值的数在每次移动后差值改变但仍相同。所以拥有相同差值的数总会在移动k步后使差值成为0，即达到目标状态。将初始状态和目标状态转换，这样目标状态就迅速压缩到两个，一个是以1为起点的正序序列，一个是以n为起点的倒序序列，我们要求的结果便是在这两个序列里差值相同的数最多的数个数max，然后是其他数都移动到这个差值。而要输出的结果便是n-max。,procedure search; var t,k,o,max:longint; begin o:=0; max:=0; for k:=1 to n do 正序序列 begin o:=lk-k; if omax then max:=so; end; o:=0; fillchar(s,sizeof(s),0) ; for k:=1 to n do 倒序序列 begin o:=ln-k+1-k; if omax then max:=so; end; min:=n-max; end;,由此这个问题完美解决，时间复杂度迅速降低到 O（k*n） k为不超过4的正整数，包括了做状态(O(2*n)和求值(O(2*n)两个部分，而且这里的状态不必包括做初始状态,第四题：等价表达式,【问题描述】 明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？ 这个选择题中的每个表达式都满足下面的性质：,1 表达式只可能包含一个变量a。 2 表达式中出现的数都是正整数，而且都小于10000。 3 表达式中可以包括四种运算+（加），-（减），*（乘），（乘幂），以及小括号(，)。小括号的优先级最高，其次是，然后是*，最后是+和-。+和-的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符+，-，*，以及小括号(，)都是英文字符） 4 幂指数只可能是1到10之间的正整数（包括1和10）。 5 表达式内部，头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子： (a1) 2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1 + (a -1)3，1109,输入格式 ： 输入文件 的第一行给出的是题干中的表达式。第二行是一个整数 n （ 2 = n = 26 ），表示选项的个数。后面 n 行，每行包括一个选项中的表达式。这 n 个选项的标号分别是 A ， B ， C ， D 输入中的表达式的长度都不超过 50 个字符，而且保证选项中总有表达式和题干中的表达式是等价的。 输出格式 ： 输出文件 包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。,对于30%的数据，表达式中只可能出现两种运算符+和-； 对于其它的数据，四种运算符+，-，*，在表达式中都可能出现。 对于全部的数据，表达式中都可能出现小括号(和)。,样例输入 : (a+1)2 3 (a-1)2+4*a a+1+a a2+2*a*1+12+10-10+a-a 样例输出 : AC,这道题作为noip2005的压轴题，自然十分麻烦，不过仔细分析，不难发现题意还是很明确的，算法也较为直接，就是代入一个或多个数据代替未知数，然后用栈来进行表达式求值，如果值一样，那就是等价的表达式。,算法分析：,表达式求值： 以(a-1)2+4*a为例： 假设a为5. 最终留在数字栈顶的元素就是最终结果,5,1,-,（,）,4,）,2,+,16,+,*,5,4,20,36,用栈进行表达式计算时，应注意以下几点： 1. 表达式中符号的优先级关系： / + - * ( ) +(,), -(,), *(,), (,), (), )(,=,), (,); 这种优先级关系也可以通过将符号“赋值”来实现 p+:=3; p-:=3; p*:=2; p/:=2; p:=1;,2.过滤字符串中的空格，替换未知数的值。 遇到空格可以直接跳过，不作