本文主要是介绍BZOJ 2124: 等差子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
给一个1到N的排列{Ai}，询问是否存在1<=p1=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
Input
输入的第一行包含一个整数T，表示组数。下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。
Output
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。
Sample Input
2
3
1 3 2
3
3 2 1
Sample Output
N
Y
HINT
对于100%的数据，N<=10000，T<=7
观察到给出的数字是1~N的排列，这不止说明数字范围在1~N之内，还说明每个数出现且仅出现一次。
按输入顺序，枚举每个数字作为等差中项，建一个bool b数组，0表示该数字没有出现，1表示已出现。
等差序列可表示为k-x=k=k+x
枚举x，若b[k-x]!=b[k+x]，则是等差序列。
（↑上段文字并不是人话，请自行忽略）
举个栗子
5
1 4 2 5 3
枚举到2
b数组为
1 1 0 1 0
b[1]!=b[3]是等差序列。
时间复杂度为O(n^2)，有些慢，不过a了。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=10005;
int n,t,a[N];
bool flg,b[N];
int main()
{scanf("%d",&t);while(t--){flg=0;memset(b,0,sizeof(b));scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){b[a[i]]=1;int len=min(a[i]-1,n-a[i]);for(int j=1;j<=len;j++)if(b[a[i]-j]!=b[a[i]+j])flg=1;}if(flg)printf("Y\n");elseprintf("N\n");}return 0;
}这篇关于BZOJ 2124: 等差子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
