第二行n个正整数,为买的n件礼物的价格。
第三行m个正整数,第i个数代表想要送给第i个朋友的礼物的价格。
(价格都在231以内)
当n=m=0时输入结束。
输出
每一组数据输出一行,如果能则输出“YES”,否则输出“NO”。
样例输入
104
12345678910
23590
103
1234578332221
224
00
样例输出
NO
YES
提示
隐藏的BUAA
时间限制:
1000ms|内存限制:
65536KB
描述
给定一个字符矩阵,问里面隐藏了多少个BUAA。
对于矩阵中的任意一条4连通的路径,如果按这条路径依次经过的字符正好是“BUAA”,就算找到了一个隐藏的BUAA。
例如对于下面的4×4的字符矩阵:
AAUB
AABB
BBBB
BBBB
一共藏了4个BUAA:
(行号,列号)
(2,3)->(1,3)->(1,2)->(1,1)
(2,3)->(1,3)->(1,2)->(2,2)
(1,4)->(1,3)->(1,2)->(1,1)
(1,4)->(1,3)->(1,2)->(2,2)
输入
输入包含多组数据。
对于每组数据,第一行为两个整数n和m(1<=n,m<=50),接下来的n行每行m个大写字符,为给定的字符矩阵。
当n=m=0时,输入结束。
输出
每组数据输出一行,为隐藏的BUAA的个数。
样例输入
21
A
B
44
AAUB
AABB
BBBB
BBBB
00
样例输出
0
4
提示
来源
盒子工厂
时间限制:
1000ms|内存限制:
65536KB
描述
淘宝的生意越来越火,以至于包装用的盒子都供不应求。
现在一个盒子工厂的老板需要你编写一个控制程序,来帮助他们制造盒子。
这个程序所需要实现的功能很简单,读取一条指令,然后指挥机械臂去执行就可以了。
但是,如果指令不合法,应该把这条命令忽略掉。
初始时有n个盒子(编号0~n-1)顺次排列在一条流水线上。
有效命令包括:
moveaontob
a和b均为盒子编号,此命令作用是将a和b两个盒子之上的盒子全部放回初始位置以后,将a放于盒子b上;
moveaoverb
a和b均为盒子编号,此命令作用是在把所有在a盒子之上的盒子放回初始位置后,把a放于含有b盒子的堆上;
pileaontob
a和b均为盒子编号,此命令作用是先把放在b盒子上面的所有盒子放回初始位置,再把a及a盒子上面所有盒子移到b盒子所在堆上,移动时保持a及a以上盒子的堆放次序;
pileaoverb
a和b均为盒子编号,此命令作用是把a及a上面的所有盒子放在含有b盒子的堆上面;
quit
退出程序。
任何命令中,假设出现a=b或者a和b出现在同一堆盒子中,那么我们认为这条命令不合法。
所以你的控制程序需要知道任何时候流水线上的盒子堆叠状况。
输入
输入包含多组数据。
对于每组数据,第一行为一个整数n(1<=n<=25),为盒子的个数。
接下来为命令序列,每行一条有效命令,格式如上文描述,你的程序需要顺序执行这些命令。
命令序列以一条quit命令结束。
当n=0时输入结束。
输出
对于每组数据,输出n行,为控制程序退出后流水线上的盒子堆叠状况。
第i+1行为编号为i的盒子的初始位置所堆叠的盒子状况:
以i开头,后接":
",然后空格,然后最底层盒子编号,再空格,再是从下数第二个盒子的编号......
样例输入
10
move9onto1
move8over1
move7over1
move6over1
pile8over6
pile8over5
move2over1
move4over9
quit
0
样例输出
0:
0
1:
1924
2:
3:
3
4:
5:
5876
6:
7:
8:
9:
提示
第k大生成数
时间限制:
1000ms|内存限制:
65536KB
描述
我们把n个数字(每个数字在1~9范围内,可能有相同的)排成一行,根据排列方法的不同,会得到一系列n位整数。
问这些整数(相同的只算一个)中第k大的是哪个。
例如,设n=4个数字分别为1、1、2、3,则可以得到的4位整数有
3211
3121
3112
2311
2131
2113
1321
1312
1231
1213
1132
1123
这其中第6大的整数是2113
输入
输入包含多组数据。
对于每组数据,第一行为两个正整数k和n(0第二行是n个1到9的整数,表示要排的n个数字。
当k=n=0时,输入结束。
输出
每组数据输出一行,就一个整数,表示可以组成的第k大的数,如果不存在,则输出-1。
样例输入
64
1123
00
样例输出
2113
提示
来源
串门
时间限制:
3000ms|内存限制:
65536KB
描述
有一个长度为k的只由小写字母构成的字符串。
在这个字符串中,任何一个长度在1到10之间的子串都是一个居民,每个居民有自己的爱好(子串的内容)和地址(首字母位置)。
现在,这个字符串上的居民决定去串门,但是每个居民只会去和自己有着相同兴趣的另一个居民家串门(即这两个字串内容完全一样),并且若有多个的话,他只去离自己最近的(地址绝对值之差最小),如果最近的也不止一个的话,他会去地址较小的。
如果没有其他居民与他有相同兴趣,他就只能待在家里。
我们想知道对于某个居民他会去哪个居民家里串门。
如果有,请输出他去串门的那个居民的地址,否则输出-1。
输入
输入包含多组数据。
对于每组数据,第一行为两个正整数k和n(2<=k<100000,1<=n<10000),分别表示字符串长度和询问的组数。
第二行是一个长度为k的字符串s,为给定的字符串。
接下来n行,每行有两个正整数a和b(1<=b<=10,1<=a<=a+b-1<=k),表示要串门的这个居民所对应的子串的起始位置在a,长度为b。
当k=n=0时,输入结束。
输出
对于每组测试数据,输出n行,每行一个整数表示对应询问的回答。
样例输入
21
aa
11
84
abcaaabc
51
42
13
32
00
样例输出
2
4
5
6
-1
提示
周长最长
时间限制:
10000ms|内存限制:
65536KB
描述
给定平面上n个点,求一个简单多边形(简单多边形覆盖的是一个没有“洞”的块,两个只有一个公共点的块不能看做一个块),要求:
(1)这个简单多边形的所有端点在给定的这n个点当中;
(2)给定的n个点都在这个简单多边形内部或边上;
(3)这个简单多边形的周长最长。
输入
输入包含多组数据。
对于每组数据,第一行为一个整数n(3<=n<=11),接下来n行每行两个整数(绝对值小于等于1000),为给定的n个点的坐标。
当n=0时,输入结束。
输出
每组数据输出一行,为要求的简单多边形的周长,小数点后保留两位有效数字。
样例输入
3
00
11
10
4
00
01
10
11
5
00
11
20
31
40
5
00
12
21
32
40
0
样例输出
3.41
4.00
8.83
11.89
提示
来源
周长最短
时间限制:
1000ms|内存限制:
65536KB
描述
给定平面上n个点,求一个简单多边形(简单多边形覆盖的是一个没有“洞”的块,两个只有一个公共点的块不能看做一个块),要求:
(1)这个简单多边形的所有端点在给定的这n个点当中;
(2)给定的n个点都在这个简单多边形内部或边上;
(3)这个简单多边形的周长最短。
输入
输入包含多组数据。
对于每组数据,第一行为一个整数n(3<=n<=1000),接下来n行每行两个整数(绝对值小于等于100000),为给定的n个点的坐标。
当n=0时,输入结束。
输出
每组数据输出一行,为要求的简单多边形的周长,小数点后保留两位有效数字。
样例输入
3
00
11
10
4
00
01
10
11
5
00
11
20
31
40
5
00
12
21
32
40
0
样例输出
3.41
4.00
8.83
10.47
提示
北京一日游
时间限制:
1000ms|内存限制:
65536KB
描述
我们都知道,在北京乘车是很方便的。
如果我们乘地铁,只需要两元钱(无论有没有公交卡)就可以到达任何线路上的地铁站(并且换乘是免费的)。
对于公交车,票价一般是一元(当然有的线路要高一些,有的线路还可能分段计费),如果有普通公交卡可以打4折(即只需要支付40%),而如果有学生公交卡则可以打2折(即只需要支付20%)。
现在小管和若干同学想从北航出发到某处去玩,他们想办法弄到了若干普通公交卡和学生公交卡,还查到了一些相关的公交和地铁信息。
试问,他们最少要花多少路费。
为了简化问题,我们假设他们查到的所有公交车线路都是全程一元的,并且他们所有人总是一起行动。
输入
输入包含多组数据。
对于每组数据,第一行有三个数字X、Y、Z,分别表示一起去的人数、他们弄到的普通公交卡和学生公交卡的张数(0第二行有三个数字N、M和P(0我们设N个相关车站从1~N编号,北航为0号,目的地为N号。
接下来M行为他们查到的M条地铁线路。
首先是一个数字C(0<=C<=100),表示这条地铁线路中我们关心的有C站,接下来C个数表示各站的编号。
最后P行为他们查到的P条公交线路。
每行首先是一个数字D(0<=D<=100)表示该线路我们关心的有D站,接下来D个数表示各站的编号。
两组数据之间有一行空行。
当X=Y=Z=0时,输入结束。
输入保证一定有办法到达目的地。
输出
对于每组数据,输出一行“Itwillatleastcost#.##yuan.”,其中“#.##”表示最少要花的路费。
样例输入
100
101
201
311
541
201
41345
202
223
204
000
样例输出
Itwillatleastcost1.00yuan.
Itwillatleastcost6.00yuan.
提示
来源
第五届北航程序设计大赛-网络预赛
最小搜索代价
时间限制:
1000ms|内存限制:
65536KB
描述
对于一棵二叉树,如果其中所有节点都满足性质“其左子树中的所有节点的值都小于他自己的值,且其右子树中所有节点的值都大于他自己的值”,那么这棵二叉树就是一棵二叉搜索树。
对于一棵有n个节点的二叉搜索树,若树中n个节点的值分别为e1、e2、...、en(e1f(e1)*deep(e1)+f(e2)*deep(e2)+...+f(en)*deep(en)
其中deep(ei)为值为ei的节点在树中的深度(根节点的深度为0)。
显然,如果调整这棵二叉搜索树的结构(当然前提是要保持其满足二叉搜索树的结构性质),其搜索代价就会随之改变。
并且肯定可以通过一系列的调整,使这棵二叉搜索树的搜索代价达到最小值。
现在问题就是:
这个最小值是多少。
输入
输入包含多组数据。
每行一组数据,以数字n开头(0当n=0时输入结束。
输出
每组数据输出一行,为可以达到的最小搜索代价,保证在231以内。
样例输入
15
3101010
351020
0
样例输出
0
20
20
提示
来源
第五届北航程序设计大赛-网络预赛
聚会
时间限制:
1000ms|内存限制:
65536KB
描述
Jimmy在买完圣诞的礼物后,突然想到有这么多份礼物要送,那不是要累死了,所以他决定在自己家里举办一个聚会,把朋友们都邀请过来,然后在聚会上把礼物送给他们。
但有一个问题出现了,Jimmy的有些朋友可能在同一个项目中工作,如果一个朋友和他的直接leader同时出现在聚会上,那么他们两就不会很开心。
所以Jimmy决定如果邀请了一个朋友来,那么就不邀请他的直接leader。
每个朋友都有一个欢乐值。
现在Jimmy得到了一份名单,名单里写着每个人的直接leader,以及每个人的欢乐值。
Jimmy想要邀请一些朋友使参加聚会的朋友的欢乐值之和最大,你能帮帮Jimmy吗?
注意:
每个人最多只有一个直接leader,并且如果A是B的leader,那么B就不可能是A的直接或间接leader。
输入
输入包含多组数据。
对于每组数据,第一行为两个整数n和m(1<=n,m<=100000),表示Jimmy总共有n个朋友(编号为1~n),有m对直接leader关系。
第二行为n个正整数,依次给出了编号为1、2、3、...、n的朋友的欢乐值。
接下来的m行,每行有两个1~n的数x和y,表示x是y的直接leader。
当n=m=0时输入结束。
输出
每组数据输出一行,为最大的欢乐值(保证在231以内)。
样例输入
1514
111111111111111
12
23
34
25
16
17
78
19
910
911
912
113
1314
115
00
样例输出
9
提示
来源
第五届北航程序设计大赛-网络预赛
股票交易
时间限制:
1000ms|内存限制:
65535KB
描述
最近中国股市又开始慢慢热起来了,还有传言说2009年中国股市将重新进入牛市。
我们也来关注下股票交易的问题。
股票的定义是一个纯经济学问题,它实际上是代表了你对股份公司的所有权,可是广大的股民群众实际上都把它看作了商品的一种,只是这种商品不是通过生产活动产生的。
我们在这里也就随大流,把它看作商品吧。
既然是商品,就存在计量的问题,水果我们是按斤买的,电视机我们是按台买的,而股票我们是按“股”买的。
这里的股与电视机的台是类似的,也就是说,我们不能买半股,至少要买一股。
当然股票和水果、电视机还是有区别,除开用处不说,股票有个非常大的特点就是价格时时刻刻都在变,任何时候任何人都可以在交易市场上合法的买卖。
股票交易是要交手续费的,这个费用包括证券交易印花税(交这个税的意义就是政府承认你的这一次交易是合法的)、过户费、监管费等等,有些费率还与买卖的股票类别有关,计算比较复杂。
为了计算方便,我们把问题简化一下。
首先,忽略一天之内的价格变动,也就是说每天只有一个成交价,在这一天买卖都是这个价格。
然后,假定只在卖的时候要交手续费,费用是一个定值s。
比如说,如果交易的手续费是100元,第一天某支股票的价格是10元一股,我们有10000元,于是可以买入1000股,到了第二天,股票涨到了11元一股,我们再卖出全部的1000股,于是得到11000元,去掉100元手续费,于是赚了900元。
以上都和预赛的股票交易是一样的,但是这里问题稍有变化,不再限定只能买卖一次了,即随便你买卖多少次。
现在如果已知了一支股票n个交易日的成交价、手续费以及一开始的资金数,问在这n天中最多能赚多少钱?
输入
输入包含多组数据。
第一行为数据的组数t(0对于每组数据,第一行是3个整数n(1第二行是n个大于0的正实数(小数点后最多两位有效数字),按时间顺序给出了n个交易日每天的成交价。
输出
对于每组数据,输出一个数,为这n天内能赚的的最大钱数,保留2位小数。
输入保证结果不超过109。
样例输入
3
410100
10.001.0012.0010.00
310100
10.55.31.9
510100
41825
样例输出
1090.00
0.00
1865.00
提示
来源
第四届北航程序设计大赛-现场决赛
Vim的替换操作
时间限制:
1000ms|内存限制:
65535KB
描述
Vim是从vi发展出来的一个文本编辑器。
代码补完、编译及错误跳转等方便编程的功能特别丰富,在程序员中被广泛使用。
和Emacs并列成为类Unix系统用户最喜欢的编辑器。
作为一个风靡世界、粉丝众多的文本编辑器,Vim有着极为丰富的操作命令。
本题便是要求你编写一个程序,模拟Vim编辑器的替换命令。
Vim替换命令的格式一般为(方括号中的内容为可选项,花括号中的内容为必选项):
:
[range]s/{pattern}/{string}/[flag]
其中:
冒号':
'是这一类命令的开始;[range]表示命令的作用域,即命令起作用的行的范围;s是替换命令substitute的简写;{pattern}和{string}分别为待搜索的模式串和所要替换成的替换串;'/'用来界定{pattern}和{string}的起始;[flag]表示标志位,用来开启或关闭一些选项。
行范围[range]通常是两个整数,表示作用域起始行和结束行的行号,中间以一个逗号隔开。
如:
"4,8"表示第4行到第8行(包括第4行和第8行)。
文本的行号从1开始。
也可以用一个百分号'%'表示文档的所有行。
(除此之外,Vim还提供了更多灵活的表示方式。
如某个数省略不写则代表光标所在行,"$"代表文本的最后一行等等,这样",$"就表示光标所在的行到最后一行。
)
{pattern}和{string}都支持正则表达式(如果你不知道什么是正则表达式,比赛结束记得google一下~)。
如果{pattern}为空串,则使用上一条替换命令中的{pattern}作为模式串。
显然,{pattern}和{string}中不能包含分隔符,否则会产生歧义。
为此,要使用反斜杠'\'进行转义。
例如,要将全文中的"
"替换为"
",就不能写成
:
%s/
/
/g
而必须写成:
:
%s/
/
/g
如果这两个表达式中的斜杠非常多,比如"file:
///usr/share/man/man1/vim.1.gz",那么对每个斜杠进行转义就显得很麻烦。
为此人们想到了一个解决办法,就是可以使用其他字符作为分隔符(总是将作为替换命令代表的's'后的第一个字符作为分隔符)。
例如使用'+'做分隔符时,上述命令就可以写成这样:
:
%s+
+
+g
[flag]有多种,"g"表示替换[range]范围内每行中的所有匹配模式,而不写"g"时,只对每行第一次匹配