瓜瓜头条

NOIP模拟赛(10.17)：语言，色球，斐波，偶数

2024-10-19 10:25 由 LISOP 发表于 #其他

语言

题面:

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

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

\[\texttt{NP} ::= \texttt{N} \mid \texttt{A} + \texttt{NP}_1 \mid \texttt{NP}_1 + \texttt{NP}_2 \]

一个句子（\(\texttt{S}\)）必须由一个名词性词组（\(\texttt{NP}_1\)）加一个动词（\(\texttt{V}\)）再加一个名词性词组（\(\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}\)），否则表示无法作为动词。

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

编码 词性
\(1\) \(\texttt{A}\)
\(2\) \(\texttt{N}\)
\(3\) \(\texttt{A} \text{ or } \texttt{N}\)
\(4\) \(\texttt{V}\)
\(5\) \(\texttt{A} \text{ or } \texttt{V}\)
\(6\) \(\texttt{N} \text{ or } \texttt{V}\)
\(7\) \(\texttt{A} \text{ or } \texttt{N} \text{ or } \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\) 个操作都是什么，但在他开始玩之前，他想知道每次他进行第二类操作取出的最后一个小球是什么颜色。

题解：

$O(n \log n)$做法($100$pts):

fhq平衡树维护序列，代码难度较大(考场上写两个半小时，还是炸到70分)，序列翻转，删除，合并都是经典操作。文艺平衡树

Code:
点击查看代码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4002000;
int n,m,root[N],tot;
namespace treap{
    struct fhq_treap{
        int ls,rs,col,val,rev;
        ll sz,num;
    }tr[N];
    void init(){
        tr[0].ls=0;
        tr[0].rs=0;
        tr[0].val=0;
        tr[0].num=0;
        tr[0].sz=0;
        tr[0].col=0;
        tr[0].rev=0;
    }
    int newnode(int col,ll num){
        ++tot;
        tr[tot].val=rand()*rand();
        tr[tot].col=col,tr[tot].sz=tr[tot].num=num;
        tr[tot].ls=tr[tot].rs=0;
        tr[tot].rev=0;
        return tot;
    }
    void pushup(int rt){
        tr[rt].sz=tr[rt].num;
        if(tr[rt].ls){
            tr[rt].sz+=tr[tr[rt].ls].sz;
        }
        if(tr[rt].rs){
            tr[rt].sz+=tr[tr[rt].rs].sz;
        }
    }
    void pushdown(int rt){
        if(tr[rt].rev){
            if(tr[rt].ls){
                tr[tr[rt].ls].rev^=1,swap(tr[tr[rt].ls].ls,tr[tr[rt].ls].rs);
            }
            if(tr[rt].rs){
                tr[tr[rt].rs].rev^=1,swap(tr[tr[rt].rs].ls,tr[tr[rt].rs].rs);
            }
            tr[rt].rev=0;
        }
    }
    int merge(int x,int y){
        if((!x)||(!y)){
            return x|y;
        }
        pushdown(x),pushdown(y);
        int rt;
        if(tr[x].val<tr[y].val){
            rt=x;
            tr[rt].rs=merge(tr[x].rs,y);
        }
        else{
            rt=y;
            tr[rt].ls=merge(x,tr[y].ls);
        }
        pushup(rt);
        return rt;
    }
    void split(int rt,ll k,int &x,int &y,int &z){
        if(!rt){
            x=y=z=0;
            return;
        }
        pushdown(rt);
        if(tr[tr[rt].rs].sz>=k){
            x=rt;
            split(tr[rt].rs,k,tr[rt].rs,y,z);
        }
        else if(tr[tr[rt].rs].sz+tr[rt].num<k){
            z=rt;
            split(tr[rt].ls,k-tr[tr[rt].rs].sz-tr[rt].num,x,y,tr[rt].ls);
        }
        else{
            x=tr[rt].ls,z=tr[rt].rs;
            y=rt;
            tr[rt].ls=tr[rt].rs=0;
        }
        pushup(rt);
    }
    void pop_nd(int x,int k){
        int a,b,c;
        split(root[x],k,a,b,c);
        root[x]=merge(a,newnode(tr[b].col,tr[c].sz+tr[b].num-k));
        cout<<tr[b].col<<endl;
    }
}
using namespace treap;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    freopen("ball.in","r",stdin);
    freopen("ball.out","w",stdout);
    string s;
    cin>>n>>m;
    for(int cas=1;cas<=m;++cas){
        cin>>s;
        int x,y,z;
        if(s=="push"){
            cin>>x>>y>>z;
            root[z]=merge(root[z],newnode(y,x));
        }
        else if(s=="put"){
            cin>>x>>y;
            tr[root[x]].rev^=1;
            swap(tr[root[x]].ls,tr[root[x]].rs);
            root[y]=merge(root[y],root[x]);
            root[x]=0;
        }else{
            cin>>x>>y;
            pop_nd(y,x);
        }
        init();
    }
    return 0;
}

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

每个位置用双向链表顺序记录放的球的个数和颜色。
对于询问$1$，往位置$z$的链表上加一个结点$(𝑥,𝑦)$。
对于询问$2$，从位置$z$的链表头取，如果当前需要取$𝒙$个而当前结点拥有的球 $𝑥′<𝑥$个，则整个结点删掉，$𝑥$更新为$𝑥−𝑥′$。如果$𝑥′≥𝑥$，那么输出当前的颜色 $𝑦′$，并且把$𝑥′$更新为$𝑥′−𝑥$。
对于询问$3$，把位置$𝑢$的链表头直接拼接到位置$𝑣$的链表头上，位置$𝑢$的链表尾作为位置$𝑣$新的链表头。
代码难度相对较小。

Code:
点击查看代码