tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

noip2007题解


解题报告 第一个题目 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。 [解题思想]

直接模拟,按照题目的大意转述即可。代码复用率要尽量高一些。尽量直接读入 之后输出。 [实际数据规模] 数据规模不大,但是各种情况都考虑了一些。 [分析] 该题目实在是为了提高总分而用的。测试数据没有保证第一位不是'-'

第三个题目 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.pas [实际数据规模] 依然是不大,覆盖的范围也比较全。但是如果高精度写得不好也会 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.pas

第四个题目 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题解_学科竞赛_高中教育_教育专区。解题报告 第一个题目 count [题目转述] 给定 n 个自然数,统计不同的自然数出现的个数,按照从小到大的顺序输出。其...


NOIP2007提高组复赛试题解题报告

NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料。NOIP2007提高组复赛试题解题报告今日推荐 160份文档 四季养生 中医养生与保健 中医养生知识大全 女人...


noip2007矩阵取数游戏 个人题解

noip2007矩阵取数游戏 个人题解_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 noip2007矩阵取数游戏 个人题解_IT/计算机_专业资料。矩阵取数游戏 (...


NOIP2007提高组试题及解析

NOIP2007提高组试题及解析_IT/计算机_专业资料。NOIP2007 提高组试题和题解NOIP2007 提高组试题及解析 1.统计数字(count.pas/c/cpp) 【问题描述】 某次科研调查...


NOIP2007普及组解题报告

NOIP2007普及组解题报告_IT/计算机_专业资料。NOIP2008普及组复赛试题与解题报告 ...(output); halt; end; end; a:=b; end; writeln('No'); {无解} ...


守望者的逃离noip2007——解题报告

局部 最优 全局最优, 其条件 是每一步都选择最优解, 递推 而动规呢?动...NOIP2007普及组初赛试题... 9页 免费 第十三届NOIP2007年普及... 8页 免费...


NOIP2007试题+答案+解析(学生版)

NOIP2007试题+答案+解析(学生版)_计算机硬件及网络_IT/计算机_专业资料。NOIP...( m?1) ? C(m?1)?( m?1) , 于是,所求的解为C(55??1)?( 7?1...


2007noip解题报告

2007noip 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见...乎都拿了满分??其实纯贪心所解出的结果并不一定是最优解(废话) ,这一题最...


NOIP 2007 普及组 解题报告

NOIP 2007 普及组 解题报告 By 江苏省赣榆县实验中学初二参赛选手 夏雨( 阿洛....其实纯贪心所解出的结果并不一定是最优解(废话) ,这一题最好 的方法还是 ...


NOIP2007提高组解题报告

NOIP2007提高组解题报告_IT/计算机_专业资料。四道题 NOIP2007 提高组解题报告 ...NOIP2007提高组试题及解... 12页 免费 NOIP2007解题报告 11页 免费 NOIP ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com