当前位置:文档之家 > 冲刺NOIP2010模拟试题与解析(十三)

冲刺NOIP2010模拟试题与解析(十三)

冲刺NOIP 2010模拟试题与解析(十三)

冲刺NOIP2010模拟试题与解析(十三)

一、防护伞

【题目描述】

据说2012的灾难和太阳黑子的爆发有关。于是地球防卫小队决定制造一个特殊防护伞,挡住太阳黑子爆发的区域,减少其对地球的影响。由于太阳相对于地球来说实在是太大了,我们可以把太阳表面看作一个平面,中心定为(0,0)。根据科学家的情报,在2012年时,太阳表面上产生N个黑子区域,每一个黑子视为一个点。特殊防护伞可以看作一个巨大的圆面,现在地球防卫小队决定将它的中心定位于某一个黑子,然后用伞面挡住其他黑子。因为制造防护伞的材料成本特别高,所以我们希望伞面尽可能的小。

【输入格式】

第1行:一个整数N,表示黑子个数。

第2..N-1行:每行两个整数,表示黑子的坐标(X,y)。

【输出格式】

第1行:一个实数,表示伞的面积。

【输入样例】

3

0 1

-8 -4

-1 4

【输出样例】

279.6017

【数据范围】

对于50%的数据:2≤N≤100。对于100%的数据:2≤N≤1,000。-10,000≤x,y≤10,000。【注意】

精确到小数点后4位。Pi=3.1415926535

二、外星密码

【题目描述】

有了防护伞,并不能完全避免2012的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力,小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码,才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码,外星人对于连续的若干个相同的子串“x”会压缩为“[DX]”的形式(D是一个整数且1≤D ≤99),比如说字符串“CBCBCBCB”就压缩为“[4CB]”或者“[2[2CB]]”,类似于后面这种压缩之后再压缩的我们称之为二重压缩。如果是“[2[2[2CB]]]",则是三重。现在我们给

你外星人发送的密码,请你对其进行解压缩。

【输入格式】

第1行:一个字符串

【输出格式】

第1行:一个字符串

【输入样例】

AC[3FUN]

【输出样例】

ACFUNFUNFUN

【数据范围】

对于50%的数据:解压后的字符串长度在1,000以内,最多只有三重压缩。

对于100%的数据:解压后的字符串长度在20,000以内,最多只有十重压缩。

保证只包含数字、大写字母、‘[’和‘]’。

三、迷之阶梯

【题目描述】

在经过地球防卫小队的数学家连续多日的工作之后,外星人发的密码终于得以破解。它告诉我们在地球某一处的古老遗迹中,存在有对抗这次灾难的秘密道具。防卫小队立刻派出了一个直升机小分队,迅速赶到了这处遗迹。要进入遗迹,需要通过一段迷之阶梯。登上阶梯必须要按照它要求的方法,否则就无法登上阶梯。它要求的方法有以下三个限制:

1.如果下一步阶梯的高度只比当前阶梯高1,则可以直接登上。

2.除了第一步阶梯外,都可以从当前阶梯退到前一步阶梯。

3.当你连续退下k步后,你可以一次跳上不超过当前阶梯高度2^k的阶梯。比如说你现在位于第j步阶梯,并且是从第j+k步阶梯退下来的,那么你可以跳到高度不超过当前阶梯高度+ 2k的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯。由于时间紧迫,我们需要用最少的移动次数登上迷之阶梯。请你计算出最少的移动步数。

【输入格式】

第1行:一个整数N,表示阶梯步数。

第2行:N个整数,依次为每层阶梯的高度,保证递增。

【输出格式】

第1行:一个整数,如果能登上阶梯,输出最小步数,否则输出-1。

【输入样例】

5

0 1 2 3 6

【输出样例】

7

【数据范围】

对于50%的数据:1≤N≤20。对于100%的数据:1≤N≤200。每步阶梯高度不超过231-1。

四、逃离遗迹

【题目描述】

根据外星人的回信,在遗迹分布着三样道具。当三样道具都拿走后,遗迹就很快自动毁灭,所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-l条长度不

等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A,B,C的房间内拿到道具,并且准备撤退。由于只有一架直升机,所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上,能够使三人到达该房间的距离之和最短。

【输入格式】

第1行:四个整数N、A、B、C。

第2..N行:每行三个整数u,v,w,表示存在连接房间u,v的通道,长度w。

【输出格式】

第1行:一个整数,表示汇合房间的编号。若存在多个解,输出字典序最小的。

第2行:一个整数,表示三人到该房间距离之和。

【输入样例】

5 3 1 4

3 5 5

4 3 9

4 1 7

1 2 1

【输出样例】

4

16

【数据范围】

对于50%的数据:1≤N≤1,000。对于l00%的数据:1≤N≤20,000。

1≤A,B,C,u,v<=N且A,B,C不相等;u,v不相等。1≤w≤1,000。

试题解析

一、防护伞

【考查算法】枚举

【算法描述】依次枚举每一个点i,计算出所有点j与点i的距离dist[i][j],则以i为圆心覆盖所有点的圆的半径为R[i] =Max{dist[i][j] |1≤j≤N),因为要求圆的面积最小,即圆的半径最小,所以答案就是R[]数组中最小的一个。

【时间复杂度】O(N2)

参考程序:

二、外星密码

【考查算法】字符串处理递归

【算法描述】从里层到外层,对每一个“[x]”进行展开即可。细节的考虑是本题能否AC的关键。

【时间复杂度】O(展开后的字串长度)

参考程序:

三、迷之阶梯

【考查算法】动态规划

【算法描述】定义两个数组h[],step[],分别表示阶梯的高度和达到某步阶梯的最小步数。那么可以很容易写出状态转移方程:

step[i]=Min{step[j]+j口k+l | k=h [i]}

其含义为:从第j步阶梯向下退到第k步,此时登上i的最少行动次数。step[i]的初始化为Inf或者step[i-1]+1(h[i]=h[i-1]+1)。如果枚举到当前step[i]=Inf,则可以判断后面的层数一定不可达,直接返回-1。

【时间复杂度】O(N2)

参考程序:

四、逃离遗迹

【考查算法】最短路

【算法描述】最先想到的算法是,依次枚举每个结点,并计算出三个点到它的距离,这样的时间复杂度为O(N2),对于N≤20,000必然会超时,需要改进。因为题目中两点间的距离是绝对不会改变的,计算i到j的距离,也可以通过计算j到i的距离得到。所以我们只需要以三个点为源点,分别计算出它们到每个点的距离。再依次枚举每一个点,取出三个点距离之和最小的点即可,即:

ans=Min {dist_A [i]+dist_B[i]+dist_C[i] |1<=i<=N},其中,dist_A[],dist_B[],dist_C[]分别表示各点到A,B,C的距离。

又因为树的特殊性,当前结点到根的距离就等于它父亲到根的距离加上边长。所以我们只需要对树进行一次遍历就可以算出每个结点到根的距离。

注意,这道题如果用普通的Dijkstra或者SPFA来求最短路,只能通过50%的数据。要考虑到树形结构的特殊之处:用DFS可以求出根到其他结点的最短距离(如果担心DFS会爆栈,可用BFS做更安全)。

【时间复杂度】O(N)

参考程序:

冲刺NOIP2010模拟试题与解析6
模拟试题与解析( 冲刺 NOIP 2010 模拟试题与解析(六)(提高组 复赛)...
冲刺NOIP2010模拟试题与解析(十五)
冲刺NOIP2010模拟试题与解析(十五)_IT/计算机_专业资料。冲刺NOIP2010模拟试题与解析(十五)NOIP 提高组复赛模拟题(一) 提高组复赛模拟题 组复赛模拟题(题目 试题名......
冲刺NOIP2010模拟试题
冲刺NOIP2010 模拟试题五 (提高组 复赛)无穷的序列(seq)【问题描述...
NOIP2010模拟试题
NOIP2010 模拟试题 故事背景: 话说小 FF 在经历了上次“寻找古代王族...
NOIP2010模拟题
NOIP2010模拟题_IT/计算机_专业资料。NOIP2010模拟题 NOIP...
NOIP冲刺2010试题
NOIP 冲刺 2010 试题三; 第一题:abbreviate; 【题目描述】...
(完整word)NOIP2010提高组初赛试题及详细解析
⑥ i - m 将前面过时的信息删除 NOIP2010 年提高组(C++语言)参...
Noip2010提高组初赛试题及详细解析(C语言)
Noip2010提高组初赛试题及详细解析(C语言)_建筑/土木_工程科技_专业资...
NOIP2010提高组复赛试题及解题报告
NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate....
noip2010提高组初赛试题及答案
(); return 0; } 输入: 5 13579 4 2 6 10 14 输出: CCF NOIP2010 提高组( C 语言)参考答案与评分标准一、单项选择题(共 10 题,每题 1.5 分,共计......
noip2010题
冲刺NOIP2010模拟试题与... 11页 免费 NOIP2010复习资料 8...
NOIP2010普及组复赛试题分析
试题分析 NOIP2010普及组复赛 NOIP2010普及组复赛 新昌信奥培训 ...
noi导刊《冲刺noip2010 七》翻转游戏题解
noi导刊《冲刺noip2010 七》翻转游戏题解_高中教育_教育专区。noi导刊《冲刺noip2010 七》翻转游戏题解 翻转游戏 题目描述 ? ? ? ? ? ? ? ? ? ? ? ? ?...
NOIP2010普及组复赛试题
NOIP2010普及组复赛试题_初三数学_数学_初中教育_教育专区。NOIP2010普及组复赛试题 全国信息学奥林匹克联赛( 全国信息学奥林匹克联赛(NOIP2010)复)赛 普及组(请......
金华一中信息学奥林匹克联赛(NOIP2010)复赛模拟试题(十八)
题目来源:NOI 专刊冲刺 NOIP2008 金华一中信息学奥林匹克联赛(NOIP2010)复赛模拟试题(十八) 一、题目概览 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出......
NOIP2010普及组解题报告
===文件名:解题报告.pas=== 全国信息学奥林匹克联赛(NOIP2010)复赛 普及组 解题报告 难度:★★★ 【数字统计】 [总评] 难度:★★★ 概括:从 a 到 b 的......
NOIP2010提高组初赛试题_C++含答案
(IOI) NOIP2010 初赛 提高组 C++ 1 D.亚太地区信息学奥林匹...
NOIP2010初赛普及组C++题目及答案
NOIP2010初赛普及组C++题目及答案_学科竞赛_高中教育_教育专区。本文是noip2010年普及组c++的题目及答案,有需要的可以下载学习。第十六届全国青少年信息学奥林匹克联赛......
NOIP2010普及组初赛试题答案C++
[i]=RIGHT; } NOIP2010 初赛 提高组 C++ 9 cout<<go[RIGHT_TO_LEFT)<<endl; return 0; } NOIP2010 年普及组(C++语言)参考答案与评分标准 普及组 语言)......
NOIP2010普及组初赛试题及答案P
NOIP2010普及组初赛试题及答案P_从业资格考试_资格考试/认证_教育专区。...