首页 > 代码库 > POJ 1743 Musical Theme Hash+二分

POJ 1743 Musical Theme Hash+二分

2024-07-26 21:21:06   224人阅读

题目大意：有一段优美的旋律，他们是由一些不超过88的音调组成的。若把五个音调算作一小节，问是否有超过一小节的韵律相同（差相同，且两个相同的韵律之间不能有重叠），并求这个最长的长度。


思路：这个题是男人八题之一，正解是后缀自动机，可是我不会。但是某神犇说过：“Hash大法好”。于是这个题Hash+二分也可以解决。分析时间复杂度，2w个点，二分logn，hash挂链判断O(kn)，总复杂度O(knlogn)，解决。
将原数组两两做差，然后按照这个数组hash。二分枚举最长的相同的韵律长度，枚举每一个开始的时间，然后判断两个韵律是否重叠，这个都放在hash表里就行了。


CODE：


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define BASE 177
#define MAX 20010
using namespace std;

struct HashSet{
	static const int mo = 9997;
	int head[mo + 100],total;
	int next[MAX],pos[MAX];
	unsigned long long true_hash[MAX];
	
	void Clear() {
		memset(head,0,sizeof(head));
		total = 0;
	}
	bool Insert(unsigned long long hash,int _pos,int ans) {
		int x = hash % mo;
		for(int i = head[x];i;i = next[i])
			if(true_hash[i] == hash && _pos - pos[i] > ans)
				return true;
		next[++total] = head[x];
		true_hash[total] = hash;
		pos[total] = _pos;
		head[x] = total;
		return false;
	}
}map;

unsigned long long p[MAX];
unsigned long long hash[MAX];
int cnt;
int _src[MAX],src[MAX];

void Pretreatment();
inline bool Judge(int ans);

int main()
{
	Pretreatment();
	while(scanf("%d",&cnt),cnt) {
		for(int i = 1;i <= cnt; ++i)
			scanf("%d",&_src[i]);
		for(int i = 1;i < cnt; ++i)
			src[i] = _src[i + 1] - _src[i] + 88;
		hash[0] = 0;
		for(int i = 1;i < cnt; ++i)
			hash[i] = hash[i - 1] * BASE + src[i];
		int l = 0,r = cnt,ans = 0;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(Judge(mid))
				l = mid + 1,ans = mid;
			else	r = mid - 1;
		}
		ans++;
		if(ans < 5)	ans = 0;
		printf("%d\n",ans);
	}
	return 0;
}

void Pretreatment()
{
	p[0] = 1;
	for(int i = 1;i < MAX; ++i)
		p[i] = p[i - 1] * BASE;
}

inline bool Judge(int ans)
{
	map.Clear();
	for(int i = ans;i < cnt; ++i)
		if(map.Insert((unsigned long long)hash[i] - hash[i - ans] * p[ans],i,ans))
			return true;
	return false;
}


POJ 1743 Musical Theme Hash+二分


联系
我们