BZOJ2119 股市的预测 字符串 SA ST表

原文链接https://www.cnblogs.com/zhouzhendong/p/9069171.html

题目传送门 - BZOJ2119

题意

　　给定一个股票连续$n$个时间点的价位，问有多少段股票走势在间隔$m$单位时间之后重现？

　　$n\leq 5\times 10^4,m\leq 10$

题解

　　和 http://www.cnblogs.com/zhouzhendong/p/9025092.html 此题十分类似。

　　这里稍微讲讲本题的不同之处。

　　首先相邻值求差，转换成字符串匹配。

　　然后，由于要间隔$m$个字符，所以我们在找关键点的对应点的时候要稍微改一改。

　　对于得到的$lcs$和$lcp$，在计算的时候有一点小小的注意点。

　　详见代码。

代码

#include 
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,a[N],tot=0;
map  mp;
int SA[N],rank[N],tmp[N],height[N],tax[N];
int ST[N][20];
void Sort(int n,int m){for (int i=0;i<=m;i++)tax[i]=0;for (int i=1;i<=n;i++)tax[rank[i]]++;for (int i=1;i<=m;i++)tax[i]+=tax[i-1];for (int i=n;i>=1;i--)SA[tax[rank[tmp[i]]]--]=tmp[i];
}
bool cmp(int rk[],int x,int y,int w){return rk[x]==rk[y]&&rk[x+w]==rk[y+w];
}
void Suffix_Array(int s[],int n){memset(SA,0,sizeof SA);memset(tmp,0,sizeof tmp);memset(rank,0,sizeof rank);memset(height,0,sizeof height);for (int i=1;i<=n;i++)rank[i]=s[i],tmp[i]=i;int m=tot+1;Sort(n,m);for (int w=1,p=0;pw)tmp[++p]=SA[i]-w;Sort(n,m);swap(rank,tmp);rank[SA[1]]=p=1;for (int i=2;i<=n;i++)rank[SA[i]]=cmp(tmp,SA[i],SA[i-1],w)?p:++p;}for (int i=1,j,k=0;i<=n;height[rank[i++]]=k)for (k=max(k-1,0),j=SA[rank[i]-1];s[i+k]==s[j+k];k++);height[1]=0;
}
void Get_ST(int n){memset(ST,0,sizeof ST);for (int i=1;i<=n;i++){ST[i][0]=height[i];for (int j=1;j<20;j++){ST[i][j]=ST[i][j-1];if (i-(1<<(j-1))>0)ST[i][j]=min(ST[i][j],ST[i-(1<<(j-1))][j-1]);}}
}
int Query(int L,int R){int val=floor(log(R-L+1)/log(2));return min(ST[L+(1<0&&lcs>0);ans+=max(len-L+1,0);}printf("%lld\n",ans);return 0;
}

转载于:https://www.cnblogs.com/zhouzhendong/p/9069171.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！