2007年Noip提高组题目解析.ppt

[解题思想1]    显然,此题可以用排序的方法来解决,根据n的范围,可以看出,O(nlogn)的算法是可以接受的。[解题思想2]    维护一个二叉树,以数的大小作为节点的权值,以数的重复次数作为节点的附加信息。之后中序遍历即可。看起来,树内的节点个数应该不到n,所以可能表现不错,其算法复杂度依然为O(nlogn)[实际数据规模]    挺小的,全部数据都是送分的。[分析]  这个题目实在不能说是一道TG组的好题。实际上,个人认为题目最大的意义在于:提供了10个测试排序算法的不怎么特别好的数据。话说回来,此题是送分题,但是送分题送的这么水,考察的也就只有OIers的细心程度了。在考试的时候,要相信有简单的题目,要相信有直接的算法。在我的身边就有几个同学因为这个题目与一等失之交臂,这是最可惜的事情。第二个题目expand[题目转述]    给定一个字符串,如果某个'-'左边同为数字或同为字母,并且右边的Ascii码严格大于左边的Ascii码,则在原串中删去'-',并在该位置上插入左右字符之间的字符。其中插入字符有3个参数。参数p1=1==>字母为小写    =2==>字母为大写    =3==>字母、数字都用'*'代替参数p2    ==>同一字母填充的个数参数p3=1按ascii递增填充,      =2按ascii递减填充。其中原串的长度不大于100。[解题思想]    直接模拟,按照题目的大意转述即可。代码复用率要尽量高一些。尽量直接读入之后输出。[实际数据规模]    数据规模不大,但是各种情况都考虑了一些。[分析]  该题目实在是为了提高总分而用的。测试数据没有保证第一位不是'-'第三个题目game[题目转述]  给出一行m个有序的数,每次取数可以从左端或右端取,第i次取数的权值为2^i,每次取出的数的值乘上权值累加,使得总得分最大。游戏进行n次。n,m<=80,操作的数<=1000[解题思想]  其实看题目,读到这里,显然也要估计到这是一道DP的题目。稍微分析一下就可以知道,这是一个较为经典的DP题目,对于区间[i,j],由于区间长度是确定的,所以无论从左边取还是右边取,权值必然也是确定的。这时,可以写出方程f[i,j]=max{f[i+1,j]+w*a,f[i,j-1]+w*a[j]}按照j-i的大小进行DP即可,每一层循环之后,另w:=w+w。其中j-i的最大值是m-2,最小值是0。最后,max{f[i,i]+w*a,i=1..m}就是所求。在计算中,需要进行大约2N^2次高精加、2N^2次高精乘单精,写得不好就会TLE,所以我考试的时候采用了10000进制。[解题思想2]  每一层的w重复计算了好多好多次,考虑优化,只要把w算进f内。考虑到w每次*2,问题规模扩大后,本质没有变化。设g[l,r]表示从l到r的区间内进行游戏(只有r-l+1个数)的最大得分,那么g[l,r]=2*max{g[l+1,r]+a[l],g[l,r-1]+a[r]}省去了高精乘的时间复杂度。总共只需要n^2次的高精加高精,2n^2次的高精加单精。[实际数据规模]依然是不大,覆盖的范围也比较全。但是如果高精度写得不好也会TLE[分析]作为一道DP题,该题的模型还是可以认为是显而易见的。仅从我个人的观点来看,题目设计的比较有水平,但是DP模型还是暴漏的太明显,数据还是小了些。高精度算法如果写得不好也会TLE。这要求我们平常多攒RP,要用快速的高精度。[小小的技巧]其实,本题的最大答案理论上也不会超过2^100。所以可以直接采用recordx,y:int64;这种结构进行运算。typebignum=recordx,y:int64;end;令max=10^20即可(不要直接':=')这样,类似于复数相加,写procedure也方便了,即使人工inline也很方便进位也只有一种。可以大大的缩短行数。不过由于int64这么多事事,还是不推荐。[题目转述]给出一棵无根树,边上有权。称最长路径为直径,定义路径的偏心距为:点到路径的上的点的最小值的距离的最大值,给出一个s,找出直径上的某段长度不超过s的路径,使得偏心距最小。[解题思想]算法是严格立方的。中心理念是不要做重复的工作。算法比较笨拙。考虑到树的性质,对于任意两点,最短路=联通路=最长路。首先求出多源最短路,该步可以由类似Tarjan的算法,在O(N^2)内解决。实际上由于下一步的复杂度高达三次方,这里就直接floyd了。同时可以求出最长路径上都有哪些点。在NOI2007中,记录最短路的中间结点是很有用的。设mid[a,b]是a,b之间的联通路上的一个中间点,。