首页 > 代码库 > Codevs 1283 等差子序列
Codevs 1283 等差子序列
1283 等差子序列
2010年
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 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
2
3
1 3 2
3
3 2 1
样例输出 Sample Output
N
Y
数据范围及提示 Data Size & Hint
对于5%的数据，N<=100，对于30%的数据，N<=1000，对于100%的数据，N<=10000，T<=7
/* 从数列中O(n)找一个mid，枚举他前面的每个数，记录下差 再枚举mid后面的数，如果差记录过，则存在等差数列*/#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=10010;int T,n,a[maxn];int vis[maxn<<4];int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); bool flag=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=2;i<=n;i++){ for(int j=1;j<i;j++) vis[a[i]-a[j]+10010]=i; for(int j=i+1;j<=n;j++){ if(vis[a[j]-a[i]+10010]==i)flag=1; if(flag)break; } if(flag)break; } if(flag)printf("Y\n"); else printf("N\n"); }}
Codevs 1283 等差子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。