当前位置:首页 >> 学科竞赛 >>

2007年noip提高组题目解析


第一个题目 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。所以可以直接采用record x,y:int64; 这种结构进行运算。 type bignum=record x,y:int64; end; 令max=10^20即可(不要直接':=') 这样,类似于复数相加,写procedure也方便了,即使人工inline也很方便进位也 只有一种。可以大大的缩短行数。不过由于int64这么多事事,还是不推荐。代码 为game2.cpp

第四个题目 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的。

[解题思想3] 引理:如果树有多条直径,则每条直径上都存在一个core。 明:首先,如图,如果ABCD和FBCE都是直径的话,则AB=FB, CD=CE(如果不然,可设AB>FB,则FBCE<ABCE,矛盾!)。 这样,ABCE,FBCD也都是直径。我们给BC起个名字叫“公共 段”。题目中说过,公共段必然存在。 考虑ecc的定义,路径的ecc是指所有的点到路径的距离的最大值。 核指的是直径上长度满足约束的ECC最小的子路经。假如根据直径 ABCE算得的core是GHBI,路径GHBI的ecc就是max{BF,AG,DI,EI}, 这个最大值取到了最小。由于DC=EC,也就是说,如果路径和公 共段有交集,公共段的一端上,不包含CORE的直径是可以任选的。 换言之,此时max{BF,AG,ID}有最小值,此时用AB替换BF,发现必 然有BF=AB>AG,ecc=max{BF,ID}。也就是说,如果路径和公共段 有交集,实际计算max时,只需要计算路径在公共段上的部分的 ecc,然后和公共段两端的路径长取一遍MAX就行了。

下面证明,使得ecc取到最小的core必然和公共段有交集。设没有 交集,则必然有一条直径和这个core没有交集,此core的ecc就至 少严格大于公共段长度+除去公共段的半条路径长度,然而,公共 段上的点到其他点的最长距离,最大不会大于这个长度,这与ecc 最小矛盾! 通过上面的论述,得出core只与公共段有关,也就是说引理成立。 所以在计算时任选一条直径即可,因为任意一条路径都覆盖了公共 段。 到了这里,写出O(N^2)的算法应该不难了。 通过一次DFS,可以求出所有点之间的连通路。此算法类似LCA, 复杂度为O(N^2*A),其中A<=4。 取一条直径,从直径上的点开始DFS,计算出每个点处伸出的树枝 的长度最大值f(v)。则路径ABCD的ecc就是 Max{f(A),F(B),f(C),F(D),AD到直径两端的距离}。枚举开始点,结束 点即可,所有到两端的距离直接可以顺便求出来,总复杂度依然是 O(N^2)的。

[解题思想4] 算法的瓶颈在于找直径,容易证明,如果A路径是B 路径的子段,则ECC(A)>=ECC(B),所以尽量沿直径 伸展core即可,直到不能向前伸展(长度超过了s)。 这类似于凸包求最远点对。实现时维护首尾指针统计 即可。这样的实现是O(n)的。


相关文章:
NOIP2007提高组试题及解析
NOIP2007提高组试题解析_IT/计算机_专业资料。NOIP2007 提高组试题和题解NOIP2007 提高组试题解析 1.统计数字(count.pas/c/cpp) 【问题描述】 某次科研调查...
NOIP2007提高组解题报告
NOIP2007提高组解题报告_英语考试_外语学习_教育专区。noip历届复赛试题解析NOIP2007 提高组解题报告 1. 统计数字(count.pas/c/cpp)【问题描述】 某次科研调查时...
NOIP2007提高组复赛试题解题报告
NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料。NOIP2007提高组复赛...休闲农庄项目可行性研究报告 2014年建筑幕墙建筑装饰行业分析报告文档...
NOIP2007_提高组_复赛试题
全国信息学奥林匹克联赛(NOIP2007)复赛提高组 全国信息学奥林匹克联赛(NOIP2007)复赛提高组 1.统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了...
noip2007初赛提高组试题和答案
noip2007初赛提高组试题和答案_理学_高等教育_教育专区。第十三届全国青少年信息学...(提示:对 N=2m+r 进行分析,其中 0≤r<2m) 。 四.阅读程序写结果(共 4...
NOIP2008提高组复赛试题及题解
NOIP2008提高组复赛试题及题解_IT认证_资格考试/认证_教育专区。noip历届复赛试题解析全国信息学奥林匹克联赛(NOIP2008)复赛 提高组一、题目概览中文题目名称 英文...
历年NOIP(普及组提高组)试题分析
历年NOIP(普及组提高组)试题分析_IT认证_资格考试/认证_教育专区。历年 NOIP(普及...2007 2008 2009 考查内容 枚举 高精度运算 数学(进制转换) 模拟 或 数学 ...
2008noip提高组复赛题解
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组解题报告...【解题分析】 1、读入字符串(文件) 2、构造一个数组,记录 a-z 各字符出现...
2007-2011年noip初赛提高组试题及答案
2007-2011年noip初赛提高组试题及答案_学科竞赛_高中教育_教育专区。第十七届...(提示:对 N=2 +r 进行分析,其中 0≤r<2 )。 四.阅读程序写结果(共 4...
历年NOIP提高组试题难度列表
NOIP 提高组复赛考察点详细分析题目编号 NOIP-2000-A NOIP-2000-B NOIP-2000-...NOIP-2006-D NOIP-2007-A NOIP-2007-B NOIP-2007-C NOIP-2007-D NOIP-...
更多相关标签:
noip2007提高组复赛 | noip2007提高组初赛 | noip2007提高组初赛c | noip2016提高组复赛 | noip2015提高组复赛 | noip2015提高组初赛 | noip2016提高组初赛 | noip2014提高组复赛 |