Steven_MengのBlog

传送门
显然只用考虑长度为$3$的等差序列,
设$a_i,a_j,a_k$为连续的$3$项
发现$2*a_j=a_i+d+a_k-d=a_i+a_k$
考虑枚举$i,j$,判断存不存在$k$
开一个桶记录$a[i]$
然后你发现$O(n^2)$的暴力$A$了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int num[MAXN],cnt[MAXN];
int main(){
int t=read();
while (t--){
int n=read();
memset(cnt,0,sizeof(cnt));
memset(num,0,sizeof(num));
for (register int i=1;i<=n;++i){
num[i]=read();
cnt[num[i]]=i;
}
bool flag=false;
for (register int i=1;i<=n;++i){
for (register int j=i+1;j<=n;++j){
if (cnt[num[j]-num[i]+num[j]]>j){
flag=true;
break;
}
}
if (flag) break;
}
puts(flag?"Y":"N");
}
}

 评论