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