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

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 ;
}
上一篇:Windows DOS 窗口设置字体颜色


下一篇:[bzoj2124]等差子序列——线段树+字符串哈希