冲刺noip2011模拟试题(二)

《冲刺noip2011模拟试题(二)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、冲刺NOIP2011模拟试题(二)题目区间运算拯救小tim树的序号蠕虫游戏源程序名输入文件输出文件时间限制1SIS1S1S空间限制128M128M128M128M1.区间运算区问运算是数学的一个领域。在区间运算屮，常量和变量并不表示为一个单独、精确的值，而是表示为一个有着上界和下界的区间或范围。在普通的运算中，一个数量可以表示为数轴上的一个点；而在区间运算屮，一个数量表示数轴上的一段，例如［3,5］表示数轴上从3到5的一段。当精确的数值表示为区间时，上界与下界是相同的，如5表示为区间即为［5,5］。两个区I'可的运算，是指一个区间中的每个点与另一个区间中的每个

2、点所做的运算，通过运算所得的所有点的集合即为运算的结果。例如，［3,5J+1-10,1］=［-7,6］。你的任务是写一个可以根据单行表达式进行取相反数、力口、减、乘、除等基本的区间运算的程序。下面是一些运算的例子：取相反数-卜3,5]=卜5,3]加法[3,5]+卜10,1]二卜7,6]减法[3,5]-[-10,1]=[2,15]乘法[3,5]卩0,1]二卜50,5]除法[3,5]/[-10,-0.1]=[-50,-0.3]【输入文件】程序的输入包含一行或多行区间运算的屮缀表达式，每个区间都表示为rmin,maxl，表达式中包括括号、负号(-)、加号(+)、减号

3、(-)、乘号(*)和除号(/),括号可能是嵌套的。每一行中都有可能有空格，但空格不会在表示区间的括号“［min,m“x］“中间或负号后出现。程序不需要处理科学记数法(如2E6=2000000)o每一行都不超过80个字符。运算采用标准的优先级规则。下面按优先级递减的顺序给出各个算符：()括号・取相反数*/,乘法和除法，同级运算按从左到右的顺序+■加法和减法，同级运算按从左到右的顺序【输出文件】对于输入文件屮每一行的表达式，以rmin,max］(minimax,均保留3位小数)的形式输岀运算结果。每个结果占一行。结果中不应有空格。在运算中，如果将一个包含0的区间用

4、作除数，则输!11“Divisionbyzero”。【样例输入】-[3,5][3.5]+卜10,1]13,5J-1-1O,1J[3.5]*[・1O,1](([3,5]/[-10,-0.11)/-[2,2])【样例输出】[-5.000,3.000]L-7.000,6.000]12.000,15.000][-50.000,5.000][0.150,25.000]1.拯救小tim小tim在游乐场，有一天终于逃了出來！但是不小心又被游乐场的工作人员发现了……所以你的任务是安全地把小hm护送回家。但是，A市复杂的交通状况给你出了一大难题。A市一共有n个路口，m条单行马路

5、。但是，每条马路都只有一段时间是开放的。为了安全，你必须选择一条护送路线，使得小tim在路上的吋间最短，即到家的吋刻减去离开游乐场的时刻最短。【输入格式】第一行4个数，分别是n,m,s,t(2WnW100;0WmW1000;lWs,tWn；sHt)。基地在路口s,码头在路口to接下来m行每行5个数x,y,b,e,c表示一-条x路口到y路口的单行线，在b吋刻到e时刻之间开放，需要c的时间通过这条路(必须保证行进在路中间时，路一直开放，否则小tim会被捉住)。两个路口之间可能会有多条道路。一开始的时刻是0(当然，你可以不用马上出发，在基地多呆一段时间)。如果不存在

6、任何一种方案使得小tim能成功到达码头，输出“Impossible”。【输出格式】一行，为小tim在路上停留的最短时间。【样例输入】45141201112012131322434134341【样例输出】3【样例解释】最优方案应该是，在1号点停留至时刻1,然后走到3号点，然后走到4号点。到达时刻为时刻4。tim在路上的时间为4-l=3o我们可以用下面的方案给二叉树标号：空树的序号为0。只有一个根结点的树序号为1。所有包含m个结点的二叉树的序号一定比任何一个包含m+1个结点的二叉树的序号小。任何一棵二叉树其左子树序号为L,右子树序号为R,且它有m个结点，若它的序号

7、为n,则所有序号大于n的且有m个结点的二叉树必满足下列条件之一：——左子树序号大于L一一左子树序号等于L且右子树序号大于R头5棵二叉树的形状如下：01234・・・•・•XXXXXX你的任务就是对给定的序号，输出该序号所对应的二叉树。【输入格式】输入文件包含多组数据，每个数据只有一个单独的整数n(l^n^500,000,000)o当n=0时表示输入文件结束，但你不必输出n=()时的空树。【输出格式】对每个数据产生一个输出。每个数据仅须输出一行，表示对应序号的树。输出树时使用下列格式：一棵树若没有子树则输出根：X。一棵树有左子树L和右子树R应当输出：(LJX(RJ

8、,U和艮为序号L和R对应的二叉树。当然