/*
题意:用数字代表音节,寻找最长主旋律,要求:不少于五个数字,不能重复;并不要求两段子串完全相同,相加同一个数字后相同也可以
题解:我原来把字符串相加一个数字后做了一次拼接,结果超时。其实这道题,更好的解法是,另建一个数组存储前后数据之差,这样如果,
存在主旋律,则这段字符串必然相等。然后问题就可以解决了。不过需要注意,最后结果需要加1
这道题做了很久,最后AC,收获很大,①到④是曾经出现过的错误。这道题的数据有些弱,需要自己做好判断
*/
#include <iostream>
using namespace std;
const int nMax = 20010;
//const int mMax = 180;
int wa[nMax], wb[nMax];
int wz[nMax], wv[nMax];//①,wz[]下标最后会转变为排名,所以也需要定义为nMax
int sa[nMax], rank[nMax], height[nMax];
int N;
int A[nMax], AA[nMax];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) wz[i]=0;
for(i=0;i<n;i++) wz[x[i]=r[i]]++;
for(i=1;i<m;i++) wz[i]+=wz[i-1];
for(i=n-1;i>=0;i--) sa[--wz[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) wz[i]=0;
for(i=0;i<n;i++) wz[wv[i]]++;
for(i=1;i<m;i++) wz[i]+=wz[i-1];
for(i=n-1;i>=0;i--) sa[--wz[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
//int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)//height[]的有效范围[2,N - 1],因为height[1]永远是0,总共有N - 1个元素
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);//以前这里也是有错误,但是为什么呢?因为原来你的AA[N-1]中没有存数据
return;
}
int bsearch(int left, int right, int n)
{
int l = left,
r = right;
int max, min;
while(l + 1 < r)
{
int mid = (l + r) / 2;
//int max = 0, min = 90;
int i;
bool flag = 0;
max = min = sa[1];//②,需要搞清楚这里的处理关系
for(i = 2; i <= n; ++ i)//③,需要等于n,因为height[]的有效范围是[2,N - 1];
{
if(height[i] < mid)
{
if(max - min > mid)//这里需要推断一下
{
flag = 1;
break;
}
max = min = sa[i];//②
}
else
{
if(sa[i] > max) max = sa[i];
if(sa[i] < min) min = sa[i];
}
}
if(max - min > mid)
flag = 1;
if(flag == 1) l = mid;
else r = mid;
}
return l + 1;
}
int main()
{
//freopen("e://data.in", "r", stdin);
while(scanf("%d", &N) != EOF && N)
{
int i;
for(i = 0; i < N; ++ i)
{
scanf("%d", &A[i]);
if(i)
AA[i - 1] = A[i] - A[i - 1] + 88;
}
AA[N - 1] = 0;
da(AA, sa, N, 180);//④,这里的m只需要最大元素即可
calheight(AA, sa, N - 1);
int ans = bsearch(0, N - 1, N - 1);//最小值为0
if(ans >= 5)
printf("%d\n", ans);
else
printf("0\n");
}
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1744222
在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算...
poj上的题,音乐主题,首先需要对给定的数组差分,之后就是用后缀数组就行
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1747400
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
NULL 博文链接:https://128kj.iteye.com/blog/1745671
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告