bzoj2119 股市的预测

感觉智商莫名其妙的就变低了……写这题的时候死活想不出来……

做法其实不难……

题目要求形如ABA的串的个数，我们可以枚举A的长度，利用标记关键点的方法统计答案。设枚举到的答案为k，每k个点标记一个关键点，显然每个A只会恰好包含一个关键点，那么我们枚举每个关键点$i$，求一下它和$i+m+l$前后各能匹配到哪儿，显然答案应该加上能匹配的长度。注意为了防止重复计算需要把LCP和LCS(最长公共后缀)对$k$取min。

求LCP和LCS我是用hash写的，一开始base选的2147483647然后WA了，换成123456789和233333333倒是都能过……什么鬼……

 /**************************************************************

     Problem: 2119

     User: hzoier

     Language: C++

     Result: Accepted

     Time:3664 ms

     Memory:1800 kb

 ****************************************************************/

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 const unsigned long long base=233333333ll;

 unsigned long long gethash(int,int);

 int LCP(int,int);

 int LCS(int,int);

 unsigned long long h[maxn],pw[maxn];

 long long ans=;

 int n,m,a[maxn];

 int main(){

     scanf("%d%d",&n,&m);

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

     for(int i=n;i;i--)a[i]-=a[i-];

     n--;

     for(int i=n;i;i--)h[i]=h[i+]*base+a[i]+base+1ull;

     pw[]=;

     for(int i=;i<=n;i++)pw[i]=pw[i-]*base;

     for(int l=;m+(l<<)<=n;l++){

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

             int tmpa=min(LCS(i,i+m+l),l),tmpb=min(LCP(i,i+m+l),l);

             if(tmpa+tmpb>l)ans+=tmpa+tmpb-l;

         }

     }

     printf("%lld",ans);

     return ;

 }

 inline unsigned long long gethash(int x,int l){return h[x]-h[x+l]*pw[l];}

 int LCP(int x,int y){

     if(x>y)swap(x,y);

     int L=,R=n-y+;

     while(L<=R){

         int M=(L+R)>>;

         if(gethash(x,M)==gethash(y,M))L=M+;

         else R=M-;

     }

     return R;

 }

 int LCS(int x,int y){

     if(x>y)swap(x,y);

     int L=,R=x;

     while(L<=R){

         int M=(L+R)>>;

         if(gethash(x-M+,M)==gethash(y-M+,M))L=M+;

         else R=M-;

     }

     return R;

 }

巴特西

bzoj2119 股市的预测

最新文章

热门文章