1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件：nt2011_sequence.in   输出文件：nt2011_sequence.out   简单对比
时间限制：0.3 s   内存限制：512 MB

【试题来源】

2011中国国家集训队命题答辩

【问题描述】

给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N（Len>=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

【输入格式】

输入的第一行包含一个整数T，表示组数。
下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。

【输出格式】

对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。

【样例输入】

2
3
1 3 2
3
3 2 1

【样例输出】

N
Y

【数据说明】

对于5%的数据，N<=100
对于30%的数据，N<=1000
对于100%的数据，N<=10000，T<=7
对于100%的数据，时间限制为0.3s。

 

 

思路比较好想，以一个数为中心，

判断一下这个数的对称的两侧，

如果一侧的数出现了但是另一侧的没出现。

那么一定存在一个可行方案

但是。

感觉自己见鬼了，

用bitset超时的题居然改成bool类型就A了，。

而且还开着o2优化。。。。

在codevs上bool比bitset快5000+ms。。。。。。。。。。。

顺便提一下，

这道题的正解是线段树/树状数组+hash

 

 

一份不能A的bitset：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<bitset>

using namespace std;

using std::bitset;

const int MAXN=;

bitset<MAXN>bit;

int a;

inline void read(int &n)

{

    char c='+';int x=;bool flag=;

    while(c<''||c>''){c=getchar();if(c=='-')flag=;}

    while(c>=''&&c<=''){x=x*+(c-);c=getchar();}

    n=flag==?-x:x;

}

int main()

{

    freopen("nt2011_sequence.in","r",stdin);

    freopen("nt2011_sequence.out","w",stdout);

    int T;

    read(T);

    while(T--)

    {

        bit.reset();

        int n;

        read(n);

        bool flag=;

        for(int i=;i<=n;i++)

        {

            read(a);

            if(flag)continue;

            bit.set(a);

            for(int j=a-;j!=;j--)

            {

                int k=a*-j;

                if(k>n)continue;

                if(bit.test(j)^bit.test(k))

                {

                    flag=;

                    break;

                }

            }

        }

        flag==?printf("Y\n"):printf("N\n");

    }

    return ;

}

　　

一份可以A的bitset

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<bitset>

using namespace std;

const int SIZEN=;

int N;

int A[SIZEN];

bitset<SIZEN> pre,suf;

bool test(void){//只能检测递增的

    pre.reset();suf.reset();

    for(int i=;i<=N;i++) suf[i]=;

    static bitset<SIZEN> tmp;

    for(int i=;i<=N;i++){

        suf[A[i]]=;

        if(i>) pre[N+-A[i-]]=;

        tmp=(suf>>A[i])&(pre>>(N+-A[i]));

        if(tmp.any()) return true;

    }

    return false;

}

void work(void){

    scanf("%d",&N);

    for(int i=;i<=N;i++) scanf("%d",&A[i]);

    if(test()){

        printf("Y\n");

        return;

    }

    reverse(A+,A++N);

    if(test()){

        printf("Y\n");

        return;

    }

    printf("N\n");

}

int main(){

    freopen("nt2011_sequence.in","r",stdin);

    freopen("nt2011_sequence.out","w",stdout);

    int T;

    scanf("%d",&T);

    while(T--) work();

    return ;

}

一份可以A的bool

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<bitset>

using namespace std;

using std::bitset;

const int MAXN=;

bool bit[MAXN];

int a;

inline void read(int &n)

{

    char c='+';int x=;bool flag=;

    while(c<''||c>''){c=getchar();if(c=='-')flag=;}

    while(c>=''&&c<=''){x=x*+(c-);c=getchar();}

    n=flag==?-x:x;

}

int main()

{

    freopen("nt2011_sequence.in","r",stdin);

    freopen("nt2011_sequence.out","w",stdout);

    int T;

    read(T);

    while(T--)

    {

        memset(bit,,sizeof(bit));

        //bit.reset();

        int n;

        read(n);

        bool flag=;

        for(int i=;i<=n;i++)

        {

            read(a);

            if(flag)continue;

            bit[a]=;

            for(int j=a-;j!=;j--)

            {

                int k=a*-j;

                if(k>n)continue;

                if(bit[j]^bit[k])

                {

                    flag=;

                    break;

                }

            }

        }

        flag==?printf("Y\n"):printf("N\n");

    }

    return ;

}