BZOJ2124: 等差子序列（树状数组&hash -> bitset 求是否存在长度为3的等差数列）

2023-01-08 09:00:37

2124: 等差子序列

Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 2354 Solved: 826
[Submit][Status][Discuss]

Description

给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，

使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

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

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

N<=10000，T<=7

Output

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

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

HINT

Source

思路：题目即是问有没有等于3的等差数列。最直观的解决就是从前往后扫，假设扫到X了，我们去看关于X对称的数，是否其出现的情况不相同，vis[X+i]!=vis[X-i]。

我们可以用两个hash来维护两个方向的01字符串，表示出现情况。这里野可以用bitset来解决。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

 int a[maxn],N;

bool check()

{

    bitset<maxn>s,t;

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

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

        t[a[i]]=;

        if(((s>>(-a[i]*))&t).any()) return true;

        s[-a[i]]=;

    }

    return false;

}

int main()

{

    int T; scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

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

        if(check()) puts("Y");

        else puts("N");

    }

    return ;

}

码农公寓