记录编号	144140	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]等差子序列	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.773 s
提交时间	2014-12-20 17:10:31	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
const int SIZEN=10010;
int N;
int A[SIZEN];
bitset<SIZEN> pre,suf;
bool test(void){//只能检测递增的
	pre.reset();suf.reset();
	for(int i=1;i<=N;i++) suf[i]=1;
	static bitset<SIZEN> tmp;
	for(int i=1;i<=N;i++){
		suf[A[i]]=0;
		if(i>1) pre[N+1-A[i-1]]=1;
		tmp=(suf>>A[i])&(pre>>(N+1-A[i]));
		if(tmp.any()) return true;
	}
	return false;
}
void work(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
	if(test()){
		printf("Y\n");
		return;
	}
	reverse(A+1,A+1+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 0;
}