【题解】\(TES-Intelligence\) \(Test\)

逼自己每天一道模拟题

传送：

【题目描述】

\(Byteotian\) 智力测试机构的一项工作是按照一定的规则删除一个序列的数字，得到一个确定的数列。\(Byteasar\) 很渴望成为 \(Byteotian\) 智力测试机构的主管，但是他在这个工作上做的并不好，但毕竟熟能生巧，他打算做大量的练习，所以他希望你写一个程序来快速判断是否正确。

【输入】

第一行一个整数 \(n\)，第二行 \(n\) 个整数\(a_i\)，表示最初的序列，第三行一个整数 \(T\)，表示 \(T\) 个 \(Byteasar\) 经过一系列删除得到的序列，每个序列两行，第一行给出长度 \(m\)，然后下一行为 \(m\) 个整数 \(b_i\)。

【输出】

共 \(m\) 行，如果 \(Byteasar\) 的序列是由最初的序列删除一些数后得到的，那么输出 \(TAK\)，否则输出 \(NIE\)。

【样例】

样例输入：71 5 4 5 7 8 6451 5 5 8 632 2 235 7 841 5 7 4样例输出：TAKNIETAKNIE

【数据范围】

\(100\%\) \(1 \leqslant n,T \leqslant 1e6\) \(,\) \(1 \leqslant a_i,b_i​ \leqslant 1e6\) \(,\) \(1 \leqslant m_i \leqslant n\)

---

【分析】

首先用一个 \(vector\) 将原数列中出现了的各数值所在的位置记录下来，然后每读一个序列进来，就扫一遍，对于每一个扫到的数，都在 \(vector\) 中进行一次二分，找到最靠前的那一个和它相同的数，然后将这个位置作为下一次二分查找的起点。

【Code】

#include
    
     #include
     
      #define Re register int#define F(a,b) for(Re i=a;i<=b;++i)const int N=1e6+5;std::vector
      
       a[N];int n,m,T,x,st,b[N];inline void in(Re &x){    int fu=0;x=0;char c=getchar();    while(c<'0'||c>'9')fu|=c=='-',c=getchar();    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();    x=fu?-x:x;}inline void sakura(Re &flag,Re now,Re l,Re r){//二分查找    while(l
       
        >1;        if(a[now][mid]>st)r=mid;        else l=mid+1;    }    flag|=a[now][l]>st,st=a[now][l];//最终判断。更新st。}inline int judge(){//判断这个序列是否合格    F(1,m){        Re flag=0,now=b[i],l=0,r=a[now].size();        if(!r)return 0;//原序列中没有这个数        --r;        sakura(flag,now,l,r);//二分        if(!flag)return 0;//二分的结果，看st后面是否存在当前扫到的这个数    }    return 1;}int main(){    in(n);F(1,n)in(x),a[x].push_back(i);    in(T);    while(T--){        in(m);st=0;        F(1,m)in(b[i]);        puts(judge()?"TAK":"NIE");    }}