codevs 1283 等差子序列

http://codevs.cn/problem/1283/

题目描述 Description

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

输入描述 Input Description

输入的第一行包含一个整数 T，表示组数。

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

输出描述 Output Description

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

样例输入 Sample Input

1 3 2

3 2 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于5%的数据，N<=100，对于30%的数据，N<=1000，对于100%的数据，N<=10000，T<=7

线段树+hash

首先要注意的是这个排列是1到n的排列

然后当然是找3个数形成等差子序列

暴力：枚举中间的数，枚举左边的数，枚举右边的数，看是否满足 2*mid=l+r

O（n³）

继续想，因为保证排列是1到n

所以对于一个数x，若以x为mid能形成等差子序列，那么另外两个数一定在x两侧

即从左往右枚举，当枚举到mid时，能早就枚举到了l，不能枚举到r

可以用0,1表示这个数是否被枚举到

举个例子：

3 6 1 2 4 5

当枚举到第5个数4时，0 1序列为

1 1 1 1 0 1

4的左边分别是1和0，说明枚举到4时，3已经被枚举到了，5还没有被枚举

但这样仍然要枚举，没有减少时间复杂度

如何去掉枚举的过程？

继续想，发现我们要比较的是mid左右的两个对称区间

举个例子:

1 8 3 6 5 7 4 2

当枚举到3时，0 1序列为：

1 0 1 0 0 0 0 1

我们实际需要的是判断2和4的01序列是否相等，1和5的01序列是否相等

因为是对称的

可以转化为判断区间[1,2]和区间[5,4]（注意这里是[5,4]，不是[4,5]）是否相等

线段树维护区间正序哈希值和倒序哈希值，即可log判断

总复杂度：O（nlogn）

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 10001

#define LL unsigned long long

using namespace std;

int T,n,x,len;

bool ok;

LL bit[N],hash[N*],anti_hash[N*],r1,r2;

struct TREE

{

    public:

        void up(int k,int l,int r)

        {

            hash[k]=hash[k<<]*bit[r-(l+r>>)]+hash[k<<|];

            anti_hash[k]=anti_hash[k<<|]*bit[(l+r>>)-l+]+anti_hash[k<<];

        }

        void change(int k,int l,int r,int pos)

        {

            if(l==r)

            {

                anti_hash[k]=hash[k]=;

                return;

            }

            int mid=l+r>>;

            if(pos<=mid) change(k<<,l,mid,pos);

            else change(k<<|,mid+,r,pos);

            up(k,l,r);

        }

        LL query(int k,int l,int r,int opl,int opr,int w)

        {

            if(l>=opl&&r<=opr) return w== ? hash[k]:anti_hash[k];

            int mid=l+r>>;

            if(opr<=mid) return query(k<<,l,mid,opl,opr,w);

            else if(opl>mid) return query(k<<|,mid+,r,opl,opr,w);

            else if(w==) return query(k<<,l,mid,opl,mid,w)*bit[opr-mid]+query(k<<|,mid+,r,mid+,opr,w);

            else return query(k<<|,mid+,r,mid+,opr,w)*bit[mid-opl+]+query(k<<,l,mid,opl,mid,w);

        }

        void solve(int i)

        {

            len=min(i-,n-i);

            r1=query(,,n,i-len,i-,);

            r2=query(,,n,i+,i+len,);

            if(r1!=r2) ok=true;

        }

}tree;

int main()

{

    bit[]=; for(int i=;i<N;i++) bit[i]=bit[i-]*;

    scanf("%d",&T);

    while(T--)

    {

        memset(hash,,sizeof(hash));

        memset(anti_hash,,sizeof(anti_hash));

        scanf("%d",&n);

        ok=false;

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

        {

            scanf("%d",&x);

            if(!ok)

            {

                tree.change(,,n,x);

                if(x!=&&x!=n) tree.solve(x);

            }

        }

        if(ok) puts("Y");

        else puts("N");

    }

}

巴特西

codevs 1283 等差子序列

最新文章

热门文章