#CW64. 毒蛇越狱(snakes)
毒蛇越狱(snakes)
题目描述
共有 条蛇,编号为 。把编号写成恰好 位的二进制串,必要时在左侧补前导零。给定一个长度为 的数字字符串 ,其中第 个字符记录编号为 的蛇的毒性数值;字符是一个十进制数字,因此毒性取值在 到 之间。
每天会出现一个长度为 的模式串,只包含 0、1 和 ?。模式中的 0 或 1 要求对应二进制位必须相同,? 表示这一位可以是任意值。各个 ? 彼此独立,所以一个模式通常会匹配多条蛇。请计算所有匹配蛇的毒性之和。每个询问都独立使用同一条字符串 ,询问之间不修改任何毒性。
输入格式
从 snakes.in 文件中读入。
第一行给出 和询问数 。第二行给出长度恰为 的字符串 ;从左到右的字符依次对应蛇编号 到 。随后 行每行给出一个长度为 的模式串,且只含有 0、1 和 ?。
输出格式
从 snakes.out 文件中输出。
输出 行,按照询问顺序,每行一个整数,表示匹配该模式的所有蛇的毒性总和。
样例 1 输入
3 5
12345678
000
0??
1?0
?11
???
样例 1 输出
1
10
12
12
36
样例 1 解释
000只匹配编号 ,毒性为 ;0??匹配编号 ,毒性之和为 ;1?0匹配编号 和 ,毒性之和为 ;?11匹配编号 和 ,毒性之和为 ;???匹配全部编号,毒性之和为 。
样例 2 输入
4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????
样例 2 输出
9
18
38
30
14
15
20
80
数据范围
对全部数据,,, 的长度为 。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 5 | 且 | |
| 2 | 7 | ||
| 3 | 10 | ||
| 4 | 53 | ||
| 5 | 25 | 无额外限制 |