冲刺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%的数据:解压缩后的字符串长度在1000以内,最多只有三重压缩。
对于100%的数据:解压后的字符串长度在20000以内,最多只有十重压缩
保证只包含数字、大写字母、‘[’和‘]’。
三、迷之阶梯
[题目描述]
在经过地球防卫小队的数学家连续多日的工作之后,外星人发的密码终于得以破解。它告诉我们在地球某一处的古老遗迹中,存在有对抗这次灾难的秘密道具。防卫小队立刻派出了一个直升机小分队,迅速感到了这处遗迹。要进入遗迹,需要经过一段迷之阶梯。登上阶梯必须要按照它要求的方法,否则就无法登上阶梯。它要求的方法有以下三个限制:
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-1条长度不等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为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<=1000
对于100%的数据:1<=N<=20000
1<=A,B,C,u,v<=N且A,B,C不相等;u,v不相等
1<=w<=1000