2119: 股市的预测
2119: 股市的预测
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 463 Solved: 214
[ Submit][ Status][ Discuss]
Description
墨墨的妈妈热爱炒股，她要求墨墨为她编写一个软件，预测某只股票未来的走势。股票折线图是研究股票的必备工具，它通过一张时间与股票的价位的函数图像清晰地展示了股票的走势情况。经过长时间的观测，墨墨发现很多股票都有如下的规律：之前的走势很可能在短时间内重现！如图可以看到这只股票A部分的股价和C部分的股价的走势如出一辙。通过这个观测，墨墨认为他可能找到了一个预测股票未来走势的方法。进一步的研究可是难住了墨墨，他本想试图统计B部分的长度与发生这种情况的概率关系，不过由于数据量过于庞大，依赖人脑的力量难以完成，于是墨墨找到了善于编程的你，请你帮他找一找给定重现的间隔（B部分的长度），有多少个时间段满足首尾部分的走势完全相同呢？当然，首尾部分的长度不能为零。
Input
输入的第一行包含两个整数N、M，分别表示需要统计的总时间以及重现的间隔（B部分的长度）。接下来N行，每行一个整数，代表每一个时间点的股价。
Output
输出一个整数，表示满足条件的时间段的个数
Sample Input
12 41 2 3 4 8 9 1 2 3 4 8 9
Sample Output
6【样例说明】
6个时间段分别是：3-9、2-10、2-8、1-9、3-11、4-12。
题解： 后缀神题，将所有的股价差分，然后就是求有多少个ABA的串。 枚举A的长度，再枚举A的左端点。
#include
#include
#include
#include
using namespace std;
const int N=50010;
typedef long long ll;
int n,m,L,ans;
int Log[N],v[N];
struct node1
{int r[N],ra[N],ws[N],st[N],sa[N],f[N][20],h[N],rank[N];void getsa(){int i,j,k,p,*x=ra,*y=ws;for(i=0;i=0;i--) sa[--st[x[i]]]=i;for(j=p=1;p=j) y[p++]=sa[i]-j;for(i=0;i=0;i--) sa[--st[x[y[i]]]]=y[i];for(swap(x,y),x[sa[0]]=0,i=p=1;in||a<0) return 0;a=rank[a],b=rank[b];if(a>b) swap(a,b);a++;int k=Log[b-a+1];return min(f[a][k],f[b-(1<=siz) ans+=a+b+1-siz;}
}
int main()
{scanf("%d%d",&n,&L);scanf("%d",&v[0]);int i;for(i=1;iss[i-1].val) m++;A.r[ss[i].org-1]=m,B.r[n-ss[i].org-1]=m;}m++;for(i=2;i<=n;i++) Log[i]=Log[i>>1]+1;A.getsa(),B.getsa(),A.getf(),B.getf(),n--;for(i=1;i*2+L<=n;i++) solve(i);printf("%d",ans);return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！