3639: 语言(第四轮01)
题目描述
牛妹正在学习一种新的语言，在这种语言里，单词只有形容词(A)，名词(N)和动 词(V)三种词性。但是一个单词可以对应多种词性。一个名词性词组(NP)可以由 一个名词(N)，或者一个形容词修饰一个子名词性词组(A+NP1)，或者两个子名
词性词组(NP1+NP2)组成。即
NP : : = N ∣ A + NP1 ∣ NP1 + NP2
一个句子(S)必须由一个名词性词组(NP1)加一个动词(V)再加一个名词性词组
(NP2)组成，即
S: : = NP1 + V + NP2
牛妹用这个语言写下一个单词的序列，现在你想知道这个单词序列是否能通过 适当安排序列里每个单词的词性使之成为一个句子（不同位置的相同的单词也 可以安排不同的词性）。
为了简单起见，她把每个单词编码对应为一个小写拉丁字母，不同的单词对应不 同的字母（这里我们假设序列里面不同的单词的总数不超过 26 个）。每个单词用 1(001)到7(111)来表示这个单词的词性。数字的二进制第 1 位为 1 表示是 A（形 容词）， 否则表示不是 A；第 2 位为 1 表示是 N（名词）， 否则表示不是 N；第 3 位为 1 表示是 V（动词），否则表示不是 V。
输入
第一行T，代表测试样例的个数。
对于每个测试样例， 一行， 26 个正整数 wa, wb, . . . , wz，表示每个单词的词性。 接下来一行， 一个字符串S，表示单词序列，保证S中只包含小写字母。
输出
对于每组样例，如果能构成一个句子，输出“Yes”；否则输出“No”。
样例输入 复制
1
7 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
bcaa样例输出 复制
Yes提示
【样例 1 输入】
1
7 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
bcaa
【样例 1 输出】
Yes
【样例 1 说明】
首先 a 可以是 A 或 N 或 V； b 只能是 A； c 只能是 N。
当 b 是 A， c 是 N， bc 构成 NP；前面一个 a 是 V；后面一个 a 是 N，单独构成 NP，符号 NP+V+NP 的结构，因此可以是一个句子。
【样例 2 输入】
1
7 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
abca
【样例 2 输出】
No
【样例 2 说明】
可以验证，不管怎么给单词安排词性，都无法构成 NP+V+NP 的结构，所以不可 能是一个句子。
【数据范围】
对于 30%数据，满足 1 ≤∣ S ∣≤ 1000
对于 100%数据，满足 T = 10, 1 ≤∣ S ∣≤ 100000, 1 ≤ wX ≤ 7, X ∈ {a, b, . . . , Z}。