分数: 350 点
问题陈述
有 N 化学品类型 1,2,\dots,N。你的目标是创建一个所有这些都混合的状态。
给你一个字符串 S 长度 2^N-1 组成 0 和 1,代表以下信息:
- 一、定义状态 i (1 \le i \le 2^N-1)其中一种或多种化学品混合如下:
- 当 k第一位数字 (1 \le k \le N)从二进制表示的底部开始 i is 1,只有这样,化学 包括 k 。 二进制的
- 例如, 13 是 1101_{(2)},所以说明 13 代表化学品的状态 1,3,4 好坏参半。
- 当 i- 第一个字符 S is
0,状态 i is 安全. - 当 i- 第一个字符 S is
1,状态 i is 危险.
您可以使用以下操作混合化学品:
- 首先,准备一个空瓶子。
- 接下来,重复以下操作:
- 选择一种尚未倒入瓶中的化学品并将其倒入瓶中。
- 此时,瓶内混合的化学物质不得处于危险状态。
确定此操作是否可以创建所有化学品混合的状态。
你被给予 T 测试用例;解决它们中的每一个。
约束
- T 是介于 1 和 40000,包括在内。
- N 是介于 1 和 18,包括在内。
- S 是一个长度为的字符串 2^N-1 组成
0和1. - 总和 一个输入文件中的 |S| = 2^N-1 中每个输入不超过 5 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 代表 i- 第一个测试用例。 每个测试用例均按以下格式给出:
N S
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,如果可以创建所有化学品混合的状态,请打印 Yes;否则,打印 No.
示例输入 1
5 3 0010000 3 0010110 1 1 2 100 4 001110010101110
示例输出 1
Yes No No Yes Yes
此输入包含五个测试用例。
的 树的 1st案例如下:
- 化学品分为三种类型。
- 仅说明 3 哪里化学品 1,2 混合是危险的,其他状态是安全的。
- 例如,您可以通过以下过程创建所有化学品混合的状态:
- 一、倒化学品 2 放入瓶子中。仅化学 瓶子里混有 2 ,这是状态 2,所以它是安全的。
- 接下来,倒入化学品 3 放入瓶子中。化学品 2,3 混在瓶子里,这是状态 6,所以它是安全的。
- 最后,倒入化学物质 1 放入瓶子中。化学品 1,2,3 混在瓶子里,这是状态 7,所以它是安全的。
的 树的 2第一种情况如下:
- 化学品分为三种类型。
- 状态 3 哪里化学品 1,2 混杂,状态 5 哪里化学品 1,3 是混合的,并且状态 6 哪里化学品 2,3 混合状态是危险的,其他状态是安全的。
- 对于这种情况,不可能创建所有化学物质混合的状态。
的 树的 3rd案例如下:
- 有一种化学品。
- 自状态 1 仅化学物质 1 混合是危险的,不可能创造出所有化学品混合的状态。