Bzoj2124(p5364): 等差子序列

题目描述

给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，

使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

输入

输入的第一行包含一个整数T，表示组数。

下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。

N<=10000，T<=7

输出

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

样例输入

样例输出

N

Y

考虑什么时候不存在等差数列
把出现过的数字对应位置赋成1，没出现过的为0
那么扫到i时，以a[i]为中心的串如果是回文，那么就不存在以a[i]为中心的等差数列
考虑用线段树维护正反两种hash值，详情看代码吧233
这题做的时候一次忘关调试信息了，然后删的时候还不小心删多了。。。(ノへ￣、)

 #include<cstdio>

 #include<cstring>

 #define ull unsigned long long

 using namespace std;

 int T,n,a[];

 ull sum1[],sum2[],hsh[];

 void add(int x,int l,int r,int q){

     if(l==q&&r==q){

         sum1[x]=sum2[x]=;

         return;

     }

     int mid=(l+r)/;

     if(q<=mid)add(x+x,l,mid,q);

     else add(x+x+,mid+,r,q);

     sum1[x]=sum1[x+x]*hsh[r-mid]+sum1[x+x+];

     sum2[x]=sum2[x+x]+sum2[x+x+]*hsh[mid-l+];

 }

 ull query(int x,int l,int r,int L,int R,int t){

     if(l==L&&r==R){

         if(t==)return sum1[x];

         else return sum2[x];

     }

     int mid=(l+r)/;

     if(R<=mid)return query(x+x,l,mid,L,R,t);

     else if(L>mid)return query(x+x+,mid+,r,L,R,t);

     else{

         if(t==)return query(x+x,l,mid,L,mid,t)*hsh[R-mid]+query(x+x+,mid+,r,mid+,R,t);

         else return query(x+x,l,mid,L,mid,t)+query(x+x+,mid+,r,mid+,R,t)*hsh[mid-L+];

     }

 }

 ull A,B;

 int main(){

     scanf("%d",&T);

     hsh[]=;

     for(int i=;i<=;i++)hsh[i]=hsh[i-]*;

     while(T--){

         bool ok=;

         scanf("%d",&n);

         for(int i=;i<=n;i++)scanf("%d",&a[i]);

         for(int i=;i<=n;i++){

             if(ok){

                 if(a[i]<=n/){

                     A=query(,,n,,*a[i]-,);

                     B=query(,,n,,*a[i]-,);

                 }

                 else{

                     A=query(,,n,*a[i]-n,n,);

                     B=query(,,n,*a[i]-n,n,);

                 }

                 if(A!=B)ok=;

                 add(,,n,a[i]);

             }

             else break;

         }

         if(ok)printf("N\n");

         else printf("Y\n");

         memset(sum1,,sizeof(sum1));

         memset(sum2,,sizeof(sum2));

     }

     return ;

 }

巴特西

Bzoj2124(p5364): 等差子序列

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章