5.1.3 Musical Themes 乐曲主题

5.1.3 Musical Themes 乐曲主题

时间: 1ms        内存:64M

描述:

我们用N(1 <= N <=5000)个音符的序列来表示一首乐曲,每个音符都是1..88范围内的整数,每个数表示钢琴上的一个键。很不幸这种表示旋律的方法忽略了音符的时值,但这项编程任务是关于音高的,与时值无关。 许多作曲家围绕一个重复出现的“主题”来构建乐曲。在我们的乐曲表示法中,“主题”是整个音符序列的一个子序列,它需要满足如下条件: 长度至少为5个音符 在乐曲中重复出现(可能经过转调,见下) 重复出现的同一主题不能重叠 “转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。 给定一段乐曲,计算其中最长主题的长度(即音符数)。

输入:

输出文件的第一行包含整数N。下面的每一行(最后一行可能除外)包含20个整数,表示音符序列。最后一行可能少于20个音符。

输出:

输出文件应只含一个整数,即最长主题的长度。如果乐曲中没有主题,那么输出0。

示例输入:

30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80

示例输出:

5

提示:

参考答案(内存最优[1428]):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 20005
int r[N],wa[N],wb[N],wv[N],ws[N],rank[N],sa[N],height[N];

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++)	ws[i]=0;
	for(i=0;i<n;i++)	ws[x[i]=r[i]]++;
	for(i=1;i<m;i++)	ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)	sa[--ws[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++)	ws[i]=0;
		for(i=0;i<n;i++)	ws[wv[i]]++;
		for(i=1;i<m;i++)	ws[i]+=ws[i-1];
		for(i=n-1;i>=0;i--)	sa[--ws[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;
}

void callheight(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)
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);	
}

int check(int *sa,int n,int k)
{
	int i,min=sa[1],max=sa[i];
	for(i=2;i<=n;i++)
	{
		if(height[i]<k)	min=max=sa[i];
		else
		{
			if(sa[i]>max)	max=sa[i];	
			if(sa[i]<min)	min=sa[i];
			if(max-min>k)	return 1;
		}
	}
	return 0;
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)	scanf("%d",&r[i]);
		for(int i=n-1;i>0;i--)	r[i]=r[i]-r[i-1]+100;
		r[n+1]=0;
		da(r,sa,n+1,200);
		callheight(r,sa,n);
		int l=1,r=n/2;
		while(l<=r)
		{
			int m=(l+r)>>1;
			if(check(sa,n,m))	l=m+1;
			else	r=m-1;
		}
		if(r>=4)	printf("%d\n",r+1);
		else	printf("0\n");
	}
}

参考答案(时间最优[24]):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 20005
int r[N],wa[N],wb[N],wv[N],ws[N],rank[N],sa[N],height[N];

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++)	ws[i]=0;
	for(i=0;i<n;i++)	ws[x[i]=r[i]]++;
	for(i=1;i<m;i++)	ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)	sa[--ws[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++)	ws[i]=0;
		for(i=0;i<n;i++)	ws[wv[i]]++;
		for(i=1;i<m;i++)	ws[i]+=ws[i-1];
		for(i=n-1;i>=0;i--)	sa[--ws[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;
}

void callheight(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)
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);	
}

int check(int *sa,int n,int k)
{
	int i,min=sa[1],max=sa[i];
	for(i=2;i<=n;i++)
	{
		if(height[i]<k)	min=max=sa[i];
		else
		{
			if(sa[i]>max)	max=sa[i];	
			if(sa[i]<min)	min=sa[i];
			if(max-min>k)	return 1;
		}
	}
	return 0;
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)	scanf("%d",&r[i]);
		for(int i=n-1;i>0;i--)	r[i]=r[i]-r[i-1]+100;
		r[n+1]=0;
		da(r,sa,n+1,200);
		callheight(r,sa,n);
		int l=1,r=n/2;
		while(l<=r)
		{
			int m=(l+r)>>1;
			if(check(sa,n,m))	l=m+1;
			else	r=m-1;
		}
		if(r>=4)	printf("%d\n",r+1);
		else	printf("0\n");
	}
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注