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

第一个题目count

[题目转述]

????给定n个自然数，统计不同的自然数出现的个数，按照从小到大的顺序输出。其中自然数的范围为0..1.5e9,n=200000

**[解题思想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次的高精加单精。本思路代码为game.cpp

[实际数据规模]

依然是不大，覆盖的范围也比较全。但是如果高精度写得不好也会TLE

[分析]

作为一道DP题，该题的模型还是可以认为是显而易见的。仅从我个人的观点来看，题目设计的比较有水平，但是DP模型还是暴漏的太明显，数据还是小了些。高精度算法如果写得不好也会TLE。这要求我们平常多攒RP，要用快速的高精度。

[小小的技巧]

其实，本题的最大答案理论上也不会超过2^100。所以可以直接采用recordx,y:int64;这种结构进行运算。

typebignum=recordx,y:int64;end;令max=10^20即可（不要直接:=）

这样，类似于复数相加，写procedure也方便了，即使人工inline也很方便进位也只有一种。可以大大的缩短行数。不过由于int64这么多事事，还是不推荐。代码为game2.cpp

第四个题目core

[题目转述]

给出一棵无根树，边上有权。称最长路径为直径，定义路径的偏心距为：点到路径的上的点的最小值的距离的最大值，给出一个s，找出直径上的某段长度不超过s的路径，使得偏心距最小。

[解题思想]

算法是严格立方的。中心理念是不要做重复的工作。算法比较笨拙。考虑到树的性质，对于