给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
思路：题目即是问有没有等于3的等差数列。 最直观的解决就是从前往后扫，假设扫到X了，我们去看关于X对称的数，是否其出现的情况不相同，vis[X+i]!=vis[X-i]。
我们可以用两个hash来维护两个方向的01字符串，表示出现情况。这里野可以用bitset来解决。
#include<bits/stdc++.h> using namespace std; const int maxn=20010; int a[maxn],N; bool check() { bitset<maxn>s,t; for(int i=1;i<=N;i++) t[i]=1; for(int i=1;i<=N;i++){ t[a[i]]=0; if(((s>>(20001-a[i]*2))&t).any()) return true; s[20001-a[i]]=1; } return false; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&a[i]); if(check()) puts("Y"); else puts("N"); } return 0; }
BZOJ2124: 等差子序列（树状数组&hash -> bitset 求是否存在长度为3的等差数列）
原文：https://www.cnblogs.com/hua-dong/p/10053574.html