杭电校赛题面

1001 qw的字符串

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
qw是杭电ACM集训队实力非常强的一位选手,他喜欢思考各种各样的算法题。qw很喜欢"belt"这个单词,希望你能在下面这个问题帮帮他。
给定一个字符串(只包含大小写字母和空格),如果包含独立的单词 "belt"(不区分大小写,不能作为某个单词的子串),则输出 "Yes",否则输出 "No"。
 

Input
第一行一个正整数T,代表有T组数据。(1≤T≤100)
接下来T行,每行一个字符串,只包含大小写字母和空格,其中字符串长度不大于1000。
提示:单词间可能有多个空格,也可能存在首尾空格
 

Output
输出T行,代表T组数据的结果。
如果字符串包含独立的单词 "belt",输出 "Yes"。
否则输出 "No"
 

Sample Input
3
There iS A beLT 
A belt is over there
I will run mybelt
 

Sample Output
Yes
Yes
No

1002 s10的面试

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
s10曾经是一位ACM集训队的同学,实力强劲,秒天秒地。面临毕业的他正在找工作,最近有n个公司向s10发出了面试邀请!但s10每天只想参加一场面试。对于第i个公司的面试,会有一个最晚面试时间ti,s10心中对于这个公司也会有一个自己的打分si。

因为简历投的多,s10拥有大量的面试机会,现在s10希望通过合理安排面试,使得参与面试的公司总分最大,你能帮帮他吗?

提示:
1. 可以面试的最早时间为第1天,最晚时间为第n天。
2. 对于第i个公司,如果错过了最晚面试时间ti,即第ti+1天及以后,则不能再参加该公司的面试。
3. 每天最多只能选择参加一场面试,每场面试均能当天结束,不会影响后面天数的选择。
 

Input
多组数据

每组数据第一行一个正整数n (n≤1000)

接下来n行,每行2个正整数ti, si (1≤ti,si≤1000)
 

Output
每组数据输出占一行,输出s10的最大总分
 

Sample Input
7
4 20
2 60
4 70
3 40
1 30
4 50
6 10
 

Sample Output
230

1003 s10的游戏王卡牌

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
最近s10迷上了一款叫《游戏王》的卡牌游戏,简单的介绍一下这一款游戏的规则:
1. 卡牌分成魔法卡和怪兽卡两种

2. 魔法卡能直接摧毁对方场上的一只怪兽

3. 怪兽卡拥有攻击力A和星级S

4. 每回合玩家可以将手牌中的一只怪兽召唤到场上,召唤方式有三种:
4.1. 直接召唤一只4星级及以下的怪兽
4.2. 牺牲一只己方场上的怪兽,召唤一只5-6星级的怪兽
4.3. 牺牲两只己方场上的怪兽,召唤一只7-8星级的怪兽

5. 已经被召唤的怪兽将从手牌中扣除,被破坏/牺牲的场上怪兽将会被移出游戏

s10向卡牌大师qw发起了挑战,s10手中有n张怪兽卡,第i只怪兽的攻击力为Ai,星级为Si,而qw手中有m张魔法卡。qw对s10这个新手很不屑,并表示在前k回合里他都不会使用魔法卡。而在k回合后,qw会一口气用掉所有魔法卡,破坏掉s10场上攻击力最高的m个怪兽。

而s10的任务就是在前k回合合理召唤怪兽,使得qw用掉魔法卡后,己方场上剩余的怪兽中攻击力最高的那只的攻击力尽量大

请问如果s10足够聪明,那么那只剩余下来后攻击力最高的怪兽的攻击力是多少?(如果s10所有怪兽都会被破坏/牺牲,那么输出0)
 

Input
多组输入

每组数据第一行给定正整数n,m,k

接下来n行,每行两个整数Ai和Si

数据范围:
0≤Ai≤50000
1≤Si≤8
1≤n,m≤100
k≤120
 

Output
对于每个测试实例,请输出s10最后攻击力最高的怪兽的攻击力,每个实例的输出占一行。
 

Sample Input
6 2 10
500 1
500 1
1500 4
900 2
2000 5
3000 7
3 2 5
500 1
700 2
1900 5
3 2 2
500 1
700 2
700 3
3 1 2
500 1
700 2
700 3
 

Sample Output
1500
0
0
700

1004 s10的加号求和

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
给定一个长度为n的数字字符串,现在有m个加号需要被插入到这个字符串里,使其成为一个合法的表达式。

请求出所有的合法表达式的运算结果之和!因为数据量太大,最后结果只需要对1000000007取模输出就行。

合法表达式的规则如下:
1. 加号不能被放在开头或结尾。
2. 两个加号之间至少要有一个数字。

举例:给定字符串"50050",加号数量为2,那么,"5+00+50", "50+0+50"等均合法的,但 "500++50", "+500+50", "500+50+"这些是非法的。
 

Input
多组数据。
每组数据有两行,第一行有两个整数n和m (0≤m<n≤105),第二行为长度为n的数字字符串。
 

Output
每组数据输出一行,输出所有的合法表达式的运算结果的总和。因为结果太大,只需要输出答案对1000000007取模输出即可。
 

Sample Input
3 1
108
3 2
108
5 3 
10008
3 0
100
 

Sample Output
27
9
45
100

1005 77姐的保研之路

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
77姐已经大三了,表示不能向菜鸡czy学习,要向杭电优秀学子dxh学习,保研清华。竞争保研资格需要计算每位同学的保研分数,择高录取,其计算方法为:

保研分数 = 平均学分绩点 * 100 + 专业课平均分 * 0.7 + 竞赛加分 * 0.2 + 综合素质分。

现在给定77姐每门课的情况(课程分数,课程学分,是否为专业课)、竞赛加分、综合素质分和今年的保研录取分数线,计算77的保研分数能否成功保研(保研分数大于等于录取线分数)?如果能,输出"Yes",否则输出"No"。

说明:
1. 专业课平均分为所有专业课的总分数除以专业课数量。

2. 平均学分绩点的计算方式为:将所有课程分数(百分制)转换为绩点(满绩点5.0),对所有课的绩点乘以其学分权重的乘积求和,再除以总学分。

举例:比如你一共修了两门课,一门是程序设计基础,绩点是4.5,学分是4。一门是体育课,绩点是3,学分是1。那么你的平均学分绩点是:(4.5*4+3*1)/(4+1)=4.2

其中课程分数与绩点的转换关系如下:
95-100分:5.0
60分及以上且94分及以下则计算方式为:假设分数为X,则绩点为(X - 45) / 10。例如:分数为94分,则绩点为(94-45)/10=4.9
 

Input
第一行给出一个正整数T,表示数据组数。
每组数据,第一行给出两个正整数n和K,分别表示77姐的课程的数量和保研录取分数线。
接下来n行,每行给出三个正整数x,y,z,分别表示课程分数,课程学分和是否是专业课(z=1表示当前课程是专业课程,z=0表示为普通课程)。
随后一行两个非负整数u,v,分别代表77姐的竞赛加分和综合素质分数。

专业核心课的数量保证至少为1,保证77姐无不及格的课程。
数据范围:
n≤100;K≤600;60≤x≤100;y≤5;u≤100,v≤10
z= 0或1
 

Output
对于每组数据,如果77姐能保研输出 "Yes",否则输出 "No"。
 

Sample Input
3
2 500
90 4 1
75 1 0
50 10
2 510
90 4 1
75 1 0
50 10
2 510
90 4 1
80 1 0
50 10
 

Sample Output
Yes
No
Yes

1006 s10的红黑树

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
众所周知,红黑树是一种优秀的数据结构,是每个节点都带有颜色属性(红色或者黑色)的二叉查找树。这道题也是关于树上的问题,但是与之不同的是,是每条边有颜色属性,其值为红色或者黑色。
现在有一棵树(无环的无向图),树上有n个节点,n−1条无向边,每条边是红色或者黑色。同时给定一个正整数k,我们定义序列 a1,a2,…,ak为 "s10序列"当且仅当其满足以下条件:我们从节点a1开始选择最短的路径到节点a2,再从节点a2开始选择最短的路径到节点a3,依次类推,直到我们从节点ak−1走到节点ak。如果我们走过的所有路径中经过的边,有至少一条黑色边的话, 那么就称其为”s10序列”。(注意其中对于序列中的不同ai的取值可以重复)

显然对于n个节点的树,给定正整数k,我们可以有nk个序列。我们现在需要统计其中有多少序列是“S10序列”。答案可能会很大,请输出答案对1000000007取模的结果。
 

Input
第一行给出一个正整数T,表示数据组数。
接下来对于每组数据,第一行给出两个正整数n和k,分别表示这棵树的节点个数和“S10序列”的长度。
接下来n−1行,每行给出三个正整数x,y,v,分别表示树中一条边的两个节点和边的颜色(0表示红色,1表示黑色)。

数据范围:
k≤n≤200000
1≤x,y≤n (x 不等于 y)
v= 0或1
 

Output
对于每组数据,输出“s10序列”的数量对1000000007取模的结果。
 

Sample Input
3
4 4
1 2 1
2 3 1
3 4 1
2 2
1 2 1
3 2
1 2 1
3 2 0
 

Sample Output
252
2
4
 

1007 77姐的子串

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
77姐特别喜欢字符串!而且特别喜欢数字"8"!作为新生班助,她要交给新生们一个任务,让他们在给定的数字串中,数一数有多少这个数字串的子串,满足条件:该子串所表示的数,是8的倍数。(小提示:8的倍数满足除以8的余数为0)
其中保证数字串不含数字 "0",只含数字 "1"~"9"。

注:子串指字符串中连续若干个字符组成的字符串。
如 "abc"的所有子串为"a","b","c","ab","bc","abc"。
而数字串的每一位都是一个数字。
 

Input
第一行给定一个整数T,表示有T组数据。
对于每组数据,给出一个数字字符串s。(仅包含数字1-9)

数据范围:
T≤10
|s|≤2000
|s|指字符串s的长度
 

Output
对于每组数据,输出一个整数,表示满足题目条件的该数字串的子串的数量。
 

Sample Input
4
1234
1888
8
88
 

Sample Output
0
7
1
3

1008 qw的粉丝

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
qw是全民K歌的知名歌手,在杭电有着众多的粉丝。某一天,qw想要正式成立自己的粉丝后援会,需要招收管理人员,于是他在杭电表白墙上发布了信息。一共有n个人报名面试。
面试必须按照报名的顺序依次进行。qw可以选择在面试完若干个粉丝以后,在所有已经面试过的粉丝中任意挑选,组建粉丝后援会管理团队。
但qw对于管理团队有着一个奇怪的要求,他希望组建的团队至少有m名粉丝,且这些粉丝的最高身高和最低身高之差不超过k个长度单位。
现在已知粉丝的身高信息,qw至少要面试多少个粉丝才能在已经面试过的粉丝中选出不少于m个人组建管理团队。
 

Input
第一行一个整数T,表示有T组输入数据。 (T≤10)
每组数据第一行3个整数n,m,k,意义见题面描述,其中 1≤m≤n≤1e5;0≤k≤1e5
第二行n个整数,第i个整数hi表示第i个报名面试的粉丝身高。1≤hi≤1e5
 

Output
如果可以选出管理团队,输出最少需要面试的人数。否则输出 "impossible"
 

Sample Input
1
6 3 5
170 169 175 171 180 175
 

Sample Output
4

1009 qw的异或游戏

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 7    Accepted Submission(s): 7


Problem Description
qw发明了一个有趣的异或游戏:

游戏会给定n个非负整数,第i个数的值为ai,另外给定一个非负整数m,如果能找到任意一个非负整数k,满足:
(a1 xor k)+(a2 xor k)+...+(an xor k)≤m

则称该异或游戏是完美的。

现在qw的问题是,对于一个异或游戏,如果它是完美的游戏,那么k最大可以为多少?如果不存在合法的k,则输出-1。

提示:异或是一种位运算,两个数异或,应先将两个数转成二进制,从低到高,按位运算,如果当前位两个数不同,则值为1,否则为0。
 

Input
第一行给定一个整数T,表示有T组数据。
每组数据有两行,第一行有两个整数n,m,意义见题目描述,第二行有n个整数,第i个整数的值为ai。

数据范围:
1≤T≤10
1≤N≤1000
0≤M≤1e6
0≤Ai≤1000
 

Output
对于每组数据,输出k的最大值,如果不存在合法的k,则输出-1
 

Sample Input
4
3 27
8 2 4
4 45
30 0 4 11
1 0
100
6 2
5 5 1 5 1 0
 

Sample Output
12
14
100
-1

1010 s10的卡片

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
s10现在有n张相同的卡片,卡片的值均为m (1≤m≤9) 。现在s10想用这些卡片拼成一个新的数(可以只取一部分),并希望这个数能被9整除。如果能,请输出最大可以拼成的数,否则输出"-1"。

举例:如果有8张值为6的卡片,可以:
1. 取3张拼成666,可以被9整除
2. 取6张拼成666666,可以被9整除
因为取6张的值大于取3张的值,故输出666666
 

Input
第一行,给出一个正整数T,表示数据组数。
接下来对于每组数据,给出两个正整数n 和 m ,分别表示卡片的张数和卡片上的数字。

取值范围:
1≤n≤1000
1≤m≤9
 

Output
对于每组数据,输出一个整数,表示用这些卡片最大可以拼成的被9整除的数。如果不能,则输出 “-1”。
 

Sample Input
4
9 5
1 2
10 2
4 3
 

Sample Output
555555555
-1
222222222
333

596382

上一篇:(HDOJ2017)--字符串统计


下一篇:有道建昆老师~Reading Comprehensive