首页 > 代码库 > BZOJ 2124: 等差子序列
BZOJ 2124: 等差子序列
Sol
线段树+Hash.
首先暴力 等差子序列至少3项就可以了,就枚举中项,枚举公差就可以了,只需要一个数在中项前出现,另一个数在中项前没出现过就可以了.复杂度 \(O(n^2)\)
然后我想了一个虽然复杂度没变(因为我不会设计这个数据结构...) 但是好像有点用的算法,就是枚举中项,考虑从一个中项转移到另一个中项,那就是 \(\pm \Delta\) 就可以了...如果能够用数据结构维护这个操作,那就灰常好了.变换中项也就是变换折叠的位置吧.
标算呢...就是用线段树维护Hash,一个数字出现过,那就为1,没出现过就为0,维护一个正反序的01序列,如果一个数的 小于它正序01序列 和 大于它的反序01序列 异或值不为0那么就存在满足条件的等差序列.
01串太长了就可以用Hash来维护了...
PS:100000007不是质数...没开Long Long 直接见祖宗.
PS:我常数好大啊QAQ
Code
/************************************************************** Problem: 2124 User: BeiYu Language: C++ Result: Accepted Time:2348 ms Memory:8720 kb****************************************************************/ #include<cstdio>#include<cstring>#include<iostream>using namespace std; typedef long long LL;const int N = 100005;const LL p = 100000007;#define debug(a) cout<<#a<<"="<<a<<" "#define mid ((l+r)>>1)#define lc (o<<1)#define rc (o<<1|1) int T,n;int a[N];LL h1[N<<2],h2[N<<2],pow[N]; inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; } inline void Update(int x,int o,int l,int r){ if(l==r){ h1[o]=h2[o]=1;return; } if(x<=mid) Update(x,lc,l,mid); else Update(x,rc,mid+1,r); h1[o]=(h1[lc]+h1[rc]*pow[mid-l+1])%p; h2[o]=(h2[lc]*pow[r-mid]+h2[rc])%p;}inline LL Query1(int L,int R,int o,int l,int r){ if(L>R) return -1;// debug(L),debug(R),debug(l),debug(r)<<endl; if(L==l&&r==R) return h1[o]; if(L<=mid&&R>mid) return (Query1(L,mid,lc,l,mid)+Query1(mid+1,R,rc,mid+1,r)*pow[mid-L+1])%p; if(L<=mid) return Query1(L,R,lc,l,mid)%p; else return Query1(L,R,rc,mid+1,r)%p;// debug(res)<<endl;// return res;}inline LL Query2(int L,int R,int o,int l,int r){ if(L>R) return -1; if(L==l&&r==R) return h2[o]; if(L<=mid&&R>mid) return (Query2(L,mid,lc,l,mid)*pow[R-mid]+Query2(mid+1,R,rc,mid+1,r))%p; if(L<=mid) return Query2(L,R,lc,l,mid)%p; else return Query2(L,R,rc,mid+1,r)%p;// return res;}int main(){ pow[0]=1;for(int i=1;i<N;i++) pow[i]=(pow[i-1]<<1)%p; for(T=in();T--;){ n=in();for(int i=1;i<=n;i++) a[i]=in(); int f=0; memset(h1,0,sizeof(h1)),memset(h2,0,sizeof(h2)); for(int i=1;i<=n;i++){ int l=min(n-a[i],a[i]-1); int u=Query2(a[i]-l,a[i]-1,1,1,n); int v=Query1(a[i]+1,a[i]+l,1,1,n);// cout<<"*********"<<endl;// debug(i)<<endl;// debug(l),debug(a[i])<<endl;// debug(a[i]-l),debug(a[i]-1)<<endl;// debug(a[i]+1),debug(a[i]+l)<<endl;// cout<<u<<" "<<v<<endl; if(u!=v){ f=1;break; } Update(a[i],1,1,n); }if(f) puts("Y");else puts("N"); } return 0;}
BZOJ 2124: 等差子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。