冲刺NOIP2010模拟试题五.doc

NOIP2010模拟试题、（提高组 复赛）一、无穷的序列（seq）【问题描述】有一个无穷序列如下：110100100010000100000请你找出这个无穷序列中指定位置上的数字【输入】第一行一个正整数N，表示询问次数；接下来的N行每行一个正整数Ai，Ai表示在序列中的位置。【输出】N行，每行为0或1，表示序列第Ai位上的数字。【输入样例】 43 14 76【输出样例】 00 10【数据范围】对于100%的数据有N1500000，Ai109二、汤姆斯的天堂梦（par）【问题描述】汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣。每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。汤姆斯预先知道了从0等级星球去N等级星球的所有的航线和所需支付（或者可以得到）的金钱，他想找一条价格最低（甚至获得金钱最多）的航线。【输入】第一行第一个正整数N（N100），接下来的数据可分为N个段落。每段的第一行一个整数Ki（Ki100），表示等级为i的星球有Ki个。接下来的Ki中第Tij行依次表示与等级为i，编号为j的星球相连的等级为i-1的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过1000）。每行以0结束，每行的航线数100。【输出】输出所需（或所得）费用。正数表示支出，负数表示收益。【输入样例】 32 1 15 0 1 5 0 31-52 10 0 1 3 0 2 40 0 21 12 5 3 -5 0 2-19 3-20 0【输出样例】-1【数据范围】对于100%的数据N100 Ki100。【样例解释】如图3.13.22.11.10.11.22.32.25151040-20-5-551-19三、克鲁斯的加减法（plus）【问题描述】奶牛克鲁斯认为人类的加法算式太落后了。比如说有时候想要用加法计算+15*3.，只能写成+15+15+15。真是浪费精力啊！于是，克鲁斯决定开发出一种新的加法算式。当然新的算式也是建立在原本算式的基础上的，不同就在于上式可以直接写成+15，当然对于15*3这样的算式可以写成15。一段时间后，克鲁斯有被那无穷多个+号 到了，于是他又将这个算式改进了一下。比如+15*3又可以写成+(3)15，当然，15*3等价于(3)15.但是从上面可以看出，对于乘数较小的情况，如+15这样的表述还是很方便的，于是在新的算式中还是保留了这种丑陋的形式。对于算式还有做一点特殊的说明：+15*3转换成鲁克斯型算式时可以写成+15或+(3)15，但是不可以写成+(2)15这样的形式。对于算式23+15*32可以表示为以下几种形式：23+15223+(3)152+23+152+23+(3)152+(1)23+(3)15(1)2不会出现如下几种形式：(1)23+152+23+(2)15(1)223+152+(0)10023(3)152【输入】一行，一个克鲁斯型算式。【输出】一行，为运算结果。【输入样例】+(1)23+(3)15(1)2【输出样例】66【数据范围】对于20%的数据，输入长度不超过10；对于100%的数据，输入长度不超过200。四、小明搬家（box）小明要搬家了，大家都来帮忙。小明现在住在第N楼，总共K个人要把X个大箱子搬上N楼。最开始X个箱子都在1楼，但是经过一段混乱的搬运已经乱掉了。最后，大家发现这样混乱的搬运过程效率太低了，于是总结出了提高效率的方法。大家的速度都是每分钟上或下层楼。多余向上走的人手中都拿一个箱子，所有向下走的人手中都不拿箱子。到达第N层立刻放下箱子向下走，到达第1层立刻拿起箱子向上走。当一个人向上走，另一个人向下走而在楼道相遇时，向上走的人将手中的箱子交割另一个人，两人同时反向。即原来拿箱子向上走的人不拿箱子往下走。原来不拿箱子向下走的人现在拿着箱子向上走。求将所有箱子搬完所需的最短时间。【输入】第一行N（N109），K（K500000），M（M109），分别比表示楼层数、人数、还放在一楼地上的箱子数。接下来K行，每行两个数Ai，Bi。Ai表示第i人现所在的楼层数，Bi为0或1.，为0表示第i人正拿着箱子往上走，为1表示第i人不拿箱子向下走。输入满足没有任意两个人正在同一楼层，在第1层的人一定正拿着箱子向上走，在第N层的人一定正不拿着箱子向下走。【输出】仅包含一个整数，为