bzoj 2124 等差子序列

bzoj 2124 等差子序列

Description

给一个1到N的排列{Ai}，询问是否存在1<=p1< p2< p3< p4< p5< …< pLen<=N (Len>=3)， 使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

输入的第一行包含一个整数T，表示组数。 下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。 N<=10000，T<=7

Output

对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。

Sample Input

2 3 1 3 2 3 3 2 1 Sample Output

N Y HINT

Source

利用一个i性质 因为是排列 所以 每个数字只会出现一次 因为要求长度>=3即可 所以我们直接求一下长度=3是否存在即可 我们一边做一边检查是否左右两边是回文串 就是检查数值的两边即可

一旦遇到不是回文串了说明肯定就可以满足条件了 毕竟我们i只需要三个 我枚举中间的点 然后算两边即可 具体hash可以用树状数组维护 看代码即可

#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;const int g=11117;const int mod=1e9+7;int n,a[N],T,p[N];inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}struct node{ int s[N]; inline void clear(){memset(s,0,sizeof(s));} inline void add(int x){ for (int i=x;i<=n;i+=i&-i) s[i]=inc(s[i],p[i-x]); } inline int qs(int x){ static int tmp;tmp=0; for (int i=x;i;i-=i&-i) tmp=inc(tmp,(ll)s[i]*p[x-i]%mod);return tmp; } inline int qr(int x,int y){ int t1=qs(x-1),t2=qs(y); return dec(t2,(ll)t1*p[y-x+1]%mod); }}t1,t2;int main(){// freopen("bzoj2124.in","r",stdin); T=read();p[0]=1; for (int i=1;i<=1e5;++i) p[i]=(ll)p[i-1]*g%mod; while(T--){ t1.clear();t2.clear();bool flag=0;n=read(); for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i<=n;++i){ int mn=min(a[i]-1,n-a[i]); if (mn&&t1.qr(a[i]-mn,a[i]-1)!=t2.qr(n-a[i]-mn+1,n-a[i])) {flag=1;break;} t1.add(a[i]);t2.add(n-a[i]+1); } if (flag) puts("Y");else puts("N"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。