题面:

牛妹正在学习一种新的语言，在这种语言里，单词只有形容词（\(\texttt{A}\)），名词（\(\texttt{N}\)）和动词（\(\texttt{V}\)）三种词性。但是一个单词可以对应多种词性。

一个名词性词组（\(\texttt{NP}\)）可以由一个名词（\(\texttt{N}\)），或者一个形容词修饰一个子名词性词组（\(\texttt{A} + \texttt{NP}_1\)），或者两个子名词性词组（\(\texttt{NP}_1 + \texttt{NP}_2\)）组成。即：

一个句子（\(\texttt{S}\)）必须由一个名词性词组（\(\texttt{NP}_1\)）加一个动词（\(\texttt{V}\)）再加一个名词性词组（\(\texttt{NP}_2\)）组成，即：

牛妹用这个语言写下一个单词的序列，现在你想知道这个单词序列是否能通过适当安排序列里每个单词的词性使之成为一个句子（不同位置的相同的单词也可以安排不同的词性）。

为了简单起见，她把每个单词编码对应为一个小写拉丁字母，不同的单词对应不同的字母（这里我们假设序列里面不同的单词的总数不超过 \(26\) 个）。每个单词用 \(1(001_{(2)})\) 到 \(7(111_{(2)})\) 来表示这个单词的词性。数字的二进制第 \(1\) 位为 \(1\) 表示这个单词可以作为形容词（\(\texttt{A}\)），否则表示无法作为形容词；第 \(2\) 位为 \(1\) 表示这个单词可以作为名词（\(\texttt{N}\)），否则表示无法作为名词；第 \(3\) 位为 \(1\) 表示这个单词可以作为动词（\(\texttt{V}\)），否则表示无法作为动词。

具体的对应关系如下表所示：

题解：

$O(Tn)$做法 ($100$pts):

注意到一个句子中动词有且仅有一个，所以对于类型4单词数大于1的情况，直接输出NO即可

根据题意，只要是一个不包含动词且以名词结尾的字符串则一定可以视为一个名词词组(即$NP$)

发现动词前必须为名词类型，结尾必须为名词类型

所以枚举动词位置，判断动词前及句末是否有名词即可，若存在类型4且数量为一，则动词一定为类型4单词

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int w[26],a[N],n,cnt,pos;
string s1;
int main(){
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//  freopen("language.in","r",stdin);
//  freopen("language.out","w",stdout);
  int t;
  cin>>t;
  while(t--){
    cnt=0,pos=0;
    for(int i=0;i<26;i++)cin>>w[i];
    cin>>s1;
    n=s1.length();
    for(int i=1;i<=n;i++){
      a[i]=w[s1[i-1]-'a'];
      if(a[i]==4)cnt++,pos=i;//记录类型4单词数量 
    }
    if(a[n]==1||a[n]==4||a[n]==5||cnt>1){
      cout<<"No\n";
      continue;
    }
    if(cnt==1){
      if(a[pos-1]==0||a[pos-1]==1||a[pos-1]==5){
        cout<<"No\n";
        continue;
      }else {
        cout<<"Yes\n";
        continue;
      }
    }
    bool suc=1;
    for(int i=2;i<n;i++){
      if((a[i]==5||a[i]==6||a[i]==7)&&(a[i-1]==2||a[i-1]==3||a[i-1]==6||a[i-1]==7)){
        cout<<"Yes\n";//枚举动词位置 
        suc=0;
        break;
      }
    }
    if(suc)cout<<"No\n";
  }
  return 0;
}

题面：

牛牛有 \(n\) 种颜色的彩色小球（编号 \(1\) 到 \(n\)），每种颜色的小球他都有无限多个。他还有 \(n\) 个球桶（编号 \(1\) 到 \(n\)），球桶的内径与小球直径相当且高度是无限大的，因此能容纳无限多的小球。他想用这些小球和球桶玩游戏。

一开始这些球桶都是空的，紧接着他会依次做 \(m\) 个操作，每个操作都是以下 \(3\) 种操作中的一个：

1. push x y z，表示把 \(x\) 个颜色为 \(y\) 的彩色小球放到第 \(z\) 个桶的最上面；
2. pop x z，表示把最上面的 \(x\) 个小球从第 \(z\) 个桶内拿出来；
3. put u v，表示把第 \(u\) 个桶的所有小球依次从顶部拿出放入第 \(v\) 个桶内。

现在他已经确定好了这 \(m\) 个操作都是什么，但在他开始玩之前，他想知道每次他进行第二类操作取出的最后一个小球是什么颜色。