Billchenchina 标签 联系 友链

BZOJ2083 [Poi2010]Intelligence test

Posted by Billchenchina on October 10, 2017
标签: 题解 BZOJ

HLSSYOJ 101

Description

霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字,得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管,但是他在这个工作上做的并不好,俗话说熟能生巧,他打算做很多练习,所以他希望你写一个程序来快速判断他的答案是否正确。

Input

第一行为一个整数m(1<=m<=1000000)第二行包括m个用空格分开的整数ai(1<=ai<=1000000),组成了最初的序列,第三行为一个整数n(1<=n<=1000000),表示n个Lyx经过一系列删除得到的序列,每个序列两行,第一行给出长度L(1<=L<=m),然后下一行为L个由空格分开的整数bi(1<=bi<=1000000)。

Output

共n行,如果Lyx的序列确实是由最初的序列删除一些数得到,就输出TAK,否则输出NIE。

Sample Input

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

Sample Output

TAK
NIE
TAK
NIE

感谢Candy99的题解。

浴谷金秋营的题,可惜是权限题。自己造了几组数据挂到自己校OJ上,假装A了

来补一发题解吧

这题。。。画风清奇

方法是对于原串的每个数字建立一个vector,vector中存的是每次这个数字出现的位置。

比如对于样例数据 1 5 4 5 7 8 6

vec[1]={1}
vec[2]={}
vec[3]={}
vec[4]={3}
vec[5]={2,4}
vec[6]={7}
vec[7]={5}
vec[8]={6}

然后对于每组查询,再在原串中对应的vec查询,保留之前最终的位置。

啊呀。。。好难文字表达啊。。。看代码实现吧

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000000+5

vector<int>vec[MAXN];

int main()
{
    int m;
    cin>>m;
    for(int i=1;i<=m;++i)
    {
        int x;
        cin>>x;
        vec[x].push_back(i);
    }
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int L;
        cin>>L;
        // 这个vector代表 upper_bound 之后在vec[bj]中的位置
        vector<int>::iterator iter;
        bool NO=false;
        // 再用这个end_pos记录下
        int end_pos=0;
        for(int j=0;j<L;++j)
        {
            int bj;
            cin>>bj;
            if(NO)continue;
            iter=upper_bound(vec[bj].begin(),vec[bj].end(),end_pos);
            if(iter==vec[bj].end())NO=true;
            else end_pos=*iter;
        }
        if(NO)
        {
            cout<<"NIE\n";
        }
        else
        {
            cout<<"TAK\n";
        }
    }
}