NOIP2007提高组解题报告 v0.3

第一个题目 count
[题目转述]
    给定n个自然数，统计不同的自然数出现的个数，按照从小到大的顺序输出。其中自然数的范围为0..1.5e9, n<=200000
[解题思想1]
    显然，此题可以用排序的方法来解决，根据n的范围，可以看出，O(nlogn)的算法是可以接受的。
[解题思想2]
    维护一个二叉树，以数的大小作为节点的权值，以数的重复次数作为节点的附加信息。之后中序遍历即可。 看起来，树内的节点个数应该不到n，所以可能表现不错，其算法复杂度依然为O(nlogn)
[实际数据规模]
    挺小的，而且也没有传说中的卡Qsort的数据，全部都很温柔。
[分析]
    这个题目实在不能说是一道TG组的好题。实际上，个人认为题目最大的意义在于：提供了10个测试排序算法的不怎么特别好的数据。 话说回来，此题是送分题，但是送分题送的这么水，考察的也就只有OIers的细心程度了。在考试的时候，要相信有简单的题目，要相信有直接的算法。在我的 身边就有几个同学因为这个题目与一等失之交臂，这是最可惜的事情。 为了仿拷贝，加了这些信息

第二个题目 expand
[题目转述]
    给定一个字符串，如果某个'-'左边同为数字或同为字母，并且右边的Ascii码严格大于左边的Ascii码，则在原串中删去'-'，并在该位置上插入左右字符之间的字符。其中插入字符有3个参数。
参数p1=1 ==> 字母为小写
      =2 ==> 字母为大写
      =3 ==> 字母、数字都用'*'代替
参数p2    ==> 同一字母填充的个数
参数p3 =1 按ascii递增填充，
       =2 按ascii递减填充。
其中原串的长度不大于100。
[解题思想]
    直接模拟，按照题目的大意转述即可。代码复用率要尽量高一些。尽量直接读入之后输出。
[实际数据规模]
    数据规模不大，但是各种情况都考虑了一些。
[分析]
    这是NOIP2007中我唯一一道没有AC的题目。没能AC这个实在不能不说是遗憾。该题目实在是为了提高总分而用的。测试数据没有保证第一位不是'-' 义乌教育

第三个题目 game
[题目转述]
   给出一行m个有序的数，每次取数可以从左端或右端取，第i次取数的权值为2^i，每次取出的数的值乘上权值累加，使得总得分最大。游戏进行n次。n,m<=80，操作的数<=1000
[解题思想]
   其实看题目，读到这里，显然也要估计到这是一道DP的题目。稍微分析一下就可以知道，这是一个较为经典的DP题目，对于区间[i,j]，由于区间长度是确定的，所以无论从左边取还是右边取，权值必然也是确定的。这时，可以写出方程
f[i,j]=max{f[i+1,j]+w*a[i] , 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]，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次的高精加单精。

第四个题目 core
[题目转述]
给出一棵无根树，边上有权。称最长路径为直径，定义路径的偏心距为：点到路径的上的点的最小值的最大值，给出一个s，找出直径上的某段长度不超过s的路径，使得偏心距最小。
[解题思想]
我的算法是严格立方的。中心理念是不要做重复的工作。算法比较笨拙。考虑到树的性质，对于任意两点，最短路=联通路=最长路。
首 先求出多源最短路，该步可以由类似Tarjan的算法，在O(N^2)内解决。实际上由于下一步的复杂度高达三次方，这里就直接floyd了。同时可以求 出最长路径上都有哪些点。在NOI2007中，记录最短路的中间结点是很有用的。设mid[a,b]是a,b之间的联通路上的一个中间点，。
由于 这是一棵树，最短路必然唯一。考虑问题的解，构造一个函数F(k,a,b)为K到ab间的最短路的长度。则f(k,a,b)=min{d[k,mid [a,b],f[k,a,mid[a,b]],f[k,mid[a,b],b]} 写出了这个方程，便不难得出一个三次方的算法。
在实际coding的时候，把k放在最外层枚举，这样内层实际上只用到了f的后面2维，用2维数组记录即可。
[解题思想2，by peterche1990/2wsx2wsx2wsx/czp]
容易求出所有最长路，以及所有最长路上的点。依次枚举，复杂度是O(KN^3)，其中K是最长路的条数。 该算法易于实现，但是写得不好会TLE1个点，部分大牛就是这样没有得400的。 提供最前沿信息技术教育信息及IT技术
[实际数据规模]
太小了。 基于最短路径条数的算法也能过。 三次方的算法也能过， 边的权还那么小。。。。
[分析]
某人一直说，NOIP要考图论题， 现在终于考到了。事实证明，NOIP的图论题还是很简单的哦。但是这个“简单”仅仅体现在数据限制上。 我们已经看到，有O(N)，O(N^2)的算法。个人认为，作为NOIP的一道压轴题目，本题的数据范围如果限定在 70% n<300, 30% n<50, 100% n<2000，还是不错的。

义乌教育

[题目综述]
作为NOIP最近几年来最简单的一套题目，此 次NOIP的区分度还是不够的。这也就是NOIP发展的方向。OI考察的不是一堆堆的难的算法，而是一种心态和思维缜密性。去年我个人NOIP考得不是一 般的恶心，两年初评的分数加起来刚好400。现在对于NOIP的选手，要做的不是去学习一堆一堆的东西，而是一些心态和思维上的稳定性。在这几个月中，我 亲眼目睹了一位强牛的成长和壮大，从a+b到NOIP390，若不是亲眼所见，我绝对不会相信。我敢保证，这位牛即使碰上2005年的题目难度，也是肯定 能300+的。 义乌市信息技术教育网，itedu

看完这篇新闻有何感觉