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

逼自己每天一道模拟题

传送：\(TES-Intelligence\) \(Test\) \([POI2010]\) \([P3500]\)

【题目描述】

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

【输入】

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

【输出】

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

【样例】

样例输入：

7

1 5 4 5 7 8 6

4

5

1 5 5 8 6

3

2 2 2

3

5 7 8

4

1 5 7 4

样例输出：

TAK

NIE

TAK

NIE

【数据范围】

\(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<vector>

#include<cstdio>

#define Re register int

#define F(a,b) for(Re i=a;i<=b;++i)

const int N=1e6+5;

std::vector<int>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<r){

        Re mid=l+r>>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");

    }

}

巴特西

【题解】TES-Intelligence Test

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

【题目描述】

【分析】

【Code】

最新文章

热门文章