冲刺NOIP 2010模拟试题与解析（十三）
一、防护伞
【题目描述】
据说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
其含义为：从第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)
参考程序：