2004年省组队赛模拟试题
试题名称 区间算术 查找基因序列 可怜的蜘蛛 星际争霸
提交文件名 interval.exe sequence.exe spider.exe starwar.exe
输入文件名 Interval.in Sequence.in Spider.in Starwar.in
输出文件名 Interval.out sequence.out spider.out Starwar.out
满分 100 100 100 100
时限 1S 1S 1S 1S
第一题 区间算术
问题描述：
区间算术是数学的一个领域，其中进行运算的“数”不再是一个单独的，确定的数值，而是用一个有上下界的区间来表示。在普通算术里面，每个数就相当于数轴上的一个点，如3.25。而在区间算术里面，每个“数”相当于数轴上一条线段，如[3，5]。每个确定的数值，也可以认为是一个上界和下界相等的区间。
对两个区间进行算术运算，就是在两个区间里各任取一个点，进行普通的算术运算，这样得到的所有运算结果的集合可以形成一个新的区间，这个新的区间就是区间算术运算的结果。比如把[3，5]加到[-10，1]上得到[-7，6]。你的任务就是编写程序，对所给的区间算术表达式进行计算，运算包括取负和加减乘除四种基本的算术四则运算。例如：
取负： -[-3，5]=[-5，3]
加法： [3，5]+[-10，1]=[-7，6]
减法： [3，5]-[-10，1]=[2，15]
乘法： [3，5]*[-10，1]=[-50，5]
除法： [3，5]/[-10，-0.1]=[-50，-0.3]
输入格式：
输入文件包含若干个合法的区间算术运算表达式，每个表达式独占一行，其中可能含有区间（用[min，max]表示），括号，负号（-），二元运算符加号（+），减号（-），乘号（*）和除号（/）。括号可能进行嵌套。每一行都有可能包含空格，但是空格不会出现在区间表示形式（[min，max]）里面，也不会出现在负号后面。你的程序不需要处理幂运算。每一行均不超过200个字符。算术运算的先后次序是：
（） 括号
- 负号
*、/ 乘除法，从左往右
+、- 加减法，从左往右
输出格式：
对于输入的每一行，都相应地输出一行，输出的内容就是区间运算的最后结果，用[min，max]的形式表示，其中min不能大于max，输出结果精确到小数点后第三位（不进行四舍五入），区间形式中间不能有空格。但如果表达式里面有除法，而且作为除数的区间包含0，则输出“Division by zero”即可。
输入输出样例：
输入： 输出：
-[-3，5] [-5.000，3.000]
[3，5]+[-10，1] [-7.000，6.000]
[3，5]-[-10，1] [2.000，15.000]
[3，5]*[-10，1] [-50.000，5.000]
（（[3，5]/[-10，-0.1]）/-[2，2]） [0.150，25.000]
第二题 查找基因序列
问题描述：
分子生物学家经常要对基因序列进行比较，以发现它们的相似之处。在这个问题里面，我们只考虑由‘A’、‘T’、‘C’、‘G’四种符号组成的核酸序列。一般来说，这种比较的过程就是先把两个序列按照一定的方式进行配对，再逐对符号依次比较，从而确定它们之间的相似程度值。给定一个目标序列和存储在基因数据库里的若干序列，要求你编写程序，找出基因数据库中跟目标序列之间最相似的序列，也就是使相似程度值达到最大值的序列。
对于给定序列和一个数据库序列之间某种配对方式，其相似程度值就是在这种配对方式下各对符号的相似程度值之和。如果配对的两个符号相同，那么该对符号的相似程度值为5，如果配对两个符号不同，那么相似程度值就为-4。在配对的过程中，还可以忝加空隙，如果某一符号与空隙配对，则相应的相似程度值为-7，比如给定序列m=“GAAGCA”和一个数据库序列n=“GCAGAGCA”，如果按照下面的配对方式来进行配对，那么两序列的相似程度值为5+（-4）+5+5+（-7）+5+5+5=19。
序列m=“GAAG？GCA”
序列n =“GCAGAGCA”
注意在上面的配对方式中忝加的空隙是用？表示。
输入格式：
输入文件第一行为给定的目标序列，第二行为一个正整数n，即数据库序列的数目，其大小不超过1000，从第3行到第n+2行，每行为一个数据库序列。所有序列都是由A、T、C、G四种符号组成的字符串，全部字母均为大写，而且字符串长度不超过100。
输出格式：
输出文件包含两行，第一行输出最大相似程度值，第二行输出与给定目标序列最相似的数据库序列，如果有多个序满足，则输出按字典顺序排列最小的一个序列。
输入输出样例：
输入： 输出：
ACGGG 18
5 AACGGG
ACGGT
ACGGGG
TCCGGTT
AACGGG
第三题 可怜的蜘蛛
问题描述：
蜘蛛william经常居住在petro博士的化学实验室里，悠闲的william常常漫步于实验室的管道上，甚至有时还会光顾一下里面空空的管道。一天晚上，他逛得实在太累了，居然在管道中睡觉了。第二天早上，petro博士来到实验室，打开阀门往管道里注入热水，准备新的一天的实验室研究工作。就在这个千钧一发的时刻，william的好朋友小灰鼠Stanley意识到问题的严重性，拼命地往阀门跑去。然而Stanley的努力还是无法挽回好朋友william的生命。
可怜的蜘蛛william给烫死了，留给stanley只有痛苦的回忆。虽然Stanley尽了自己最大的努力，但他内心还是感觉很内疚。他想知道当时从petro博士打开阀门那一刻开始，他有多少时间支拯救好朋友。他的心情是如此的差，以至于无法自己计算，你能帮助他吗？
所有的管道都是直径1cm垂直放置的底部封闭开口向上的圆柱体。有些管道之间有水平的小细管相连。由于直径很细，任何时候流动在小细管中的水的体积可以忽略不计。水从一个管道上方以恒定的速度0.25πcm2/sec注入。管道中的水越来越多，当水位到达跟某管道相连的小细管时，该管道也开始注入水。根据基本的物理原理，我们知道对于两个相连的管道，如果水位已经超过连接他们的小细管的话，往其中任意一个管道注水，两个管道的水位都会保持一致。在这种情况下，其中一个管道的水增量只有注入水的总量的一半。例如，对于下面这种情况：
首先，水以全速注入左边管道最下2cm；然后水注入右连最下的3cm。接着两条管道水位同时以原先速度的一半上升。
输入你程序的数据包含仪器中各个管道和细管的位置，以及蜘蛛所处的管道和深度。你的程序应该返回在不淹没william之前，Stanley有多少时间去救他的朋友。上图的答案是9sec。
为了简化问题，题目假设水下降速度很快，从开口下降所用的时间忽略不计。蜘蛛所在的位置可以假定为描述深度稍微高一点点的地方。比如，蜘蛛处于上图左连管道深度为4的地方的时候，那么答案应该是5，而不是2。同时，如果水到达一个管道的出口的时候，水并不会立刻溢出。只有等所有跟其相连的管道低于该开口的空间都充满了水的时候，水才开始溢出。（不排除有小细管处于开口的垂直位置的情况）
输入格式：
我们用管道或小细管的左上方的坐标（X，Y）表示它们的位置。
（X轴坐标从左到右递增，Y轴坐标从上到下递增）。
所有的坐标都是从0到100的整数。（即0<=x<=100,0<=y<=100）。
文件的第一行是t，表示输入文件包含t个输入数据。（1<=t<=10）。
对于每个输入数据：
数据的第一部分第一行是管道的数目p（1<=p<=20），接着p行分别描述各个管道。每一个管道由三个整数（x,y,h）描述，表示管道的左上角坐标（x,y）和管道的深度h（1<=h<=20）。注意管道的直径恒为1cm。
数据的第二部分第一行是小细管的数目q（1<=q<=50），接着q行分别描述各个小细管，每一个小细管也是由三个整数（x,y,L）描述，表示小细管的左端点坐标（x,y）和小细管的长度（1<=L<=20）。假设小细管的宽度为0。
数据的最后一行有两个整数。第一个表示william所在管道在输入数据中的序号，第二个整数表示william所处的位置（用Y坐标表示）。William当时可能不在管道中。（可能伤心的Stanley把william所在的位置记错了）。
可以假定：
1、 水从第一个管道注入；
2、 没有小细管会穿过管道；
3、 任意两个小细管处于不同高度；
4、 任意两个管道的左上角坐标不同；
5、 任何小细管的端点跟管道相连。
输出格式：
输出文件应该包含t行输出数据，分别对应t个输入数据。如果可能的话，输出数据是一个整数，表示水到达william所在位置所用的时间，否则输出“No Solution”（这个时候水不可能到达william所在有位置）。
输入输出样例：
输入： 输出：
1 9
2
2 0 6
5 1 6
1
3 4 2
2 2
第四题 星际争霸
问题描述：
虫族已经消灭了神族。邪恶的虫族还想消灭人族，于是又向人族发起了战争。经过激烈的战斗，人族凭着团结的精神，视死如归的斗志把虫族打得落花流水。然而事情还没结束，虽知道虫族是天生邪恶的，一有机会它们便要消灭人族，我们先发制虫。正所谓斩草不除根，春风吹又生，为了人族子孙后代的幸福，人族不能放过余下的虫族，一只也不能放过！当时战斗的形势是：所有余下虫族集中在一个星球上，虫族也意识到它们不是玩抗的时候，逃跑是它们唯一的出路，而且为了能有所生还，它们会分散逃跑，但我们人族早有准备啦，军师派出多中探子，探出虫族逃跑的所有可能经过的路线，我们会派兵在其中若干条路上等待并消灭它们。
虫族所在的星球编号为0，另外还有N个星球，分别编号为1，2，……，N-1，N。建立一个原点在0号星球的三维坐标系，另N个星球的坐标为（Xi,Yi,Zi）i=1，2，……，N-1，N。虫族已经建立了在这（N+1）个星球之间的交通设备。具体的说，有某种不明交通工具M架，每架能且只能连接两个不同星球使虫族能从连接的两个星球中的任一个到达另一个。探子已经探出这M架交通工具连接的星球对。
军师要派兵在若干个虫族的通路中埋伏，要使所有虫都逃不了，但是要在某条通路中埋伏要派兵数目等于该通路连接的两个星球的距离的平方，军师希望用最少的兵力达到不让一只虫逃掉的目的。你要帮他算算最少用兵数目。军师指出，若有某一只虫能逃离星球0到达另一个星球i，并且星球i与星球0的距离大于R，则该虫算逃掉了，它这时能用某种不明方法离开到很远很远的地方，然后重新繁衍出虫族，再来消灭我们人族，这正是我们要避免的。注意人族可以派兵埋伏于与星球0距离大于R的地方。
输入格式：
N M R
X1 Y1 Z1
X2 Y2 Z2
……
Xn Yn Zn
T1a T1b
T2a T2b
……
Tma Tmb
以上的输入均为整数，同行整数用1个或多个空格隔开。
第一行：
N（1<=N<=50）为除星球0外的星球数，M（0<=M<=N*（N+1）/2）为虫族交通工具数目，R（1<=R<=10000）为虫族逃离界限，意义见上。
往下N行：
（Xi,Yi,Zi）分别描述星球i的坐标，i=1，2，……，N-1，N；
（-1000<=Xi,Yi,Zi<=1000）。
往下M行：
Tia ，Tib分别描述第i个交通工具连接的两个星球。0<=Tia,Tib<=N并且Tia不等于Tib，并且若Tia,Tib出现了，往下就不会再有Tia,Tib或Tib,Tia，既每对点最多出现一次。
输出格式：
仅一个整数，即所用的最少兵力。
输入输出样例：
输入： 输出：
1 1 2 0
1 1 1
0 1
输入： 输出：
1 1 1 3
1 1 1
0 1
