[USACO5.1] Musical Themes [Hash/二分]

Author Avatar
ajcxsu 2018年09月07日
  • 68 次阅读

本题是一道全面探测hash技术的好题。

Problem

我们用N(1 <= N <=5000)个音符的序列来表示一首乐曲,每个音符都是1..88范围内的整数,每个数表示钢琴上的一个键。很不幸这种表示旋律的方法忽略了音符的时值,但这项编程任务是关于音高的,与时值无关。

许多作曲家围绕一个重复出现的“主题”来构建乐曲。在我们的乐曲表示法中,“主题”是整个音符序列的一个子串,它需要满足如下条件:

⒈长度至少为5个音符

⒉在乐曲中重复出现(可能经过转调,见下)

⒊重复出现的同一主题不能有公共部分。

“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。 给定一段乐曲,计算其中最长主题的长度(即音符数)。

Solution

显然是对差值hash。 $O(n^2)$暴力枚举。

然后遇到了以下几个问题:
单hash会碰撞
需要用到map而map效率过低

初步解决方案:
单hash改为双hash,所有hash类型改为int,只在乘法处转为long long
将map替换成unordered_map,由于双hash要用到pair,因此我们需要对unordered_map进行运算符重载

洛谷+O2 AC
USACO TLE

进一步的解决方案
将unordered_map转为gp_hash_table
仍然GG

然后去看了一下题解,发现可以二分 因为是$n^2$的范围促使我没有想$\log n$的算法,这点我需要反省

Code

/*
ID: a1162731
TASK: theme
LANG: C++11
*/

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
const int N=5010;
int arr[N], Dec[N];
int ha[2][N], p[2][N], mo[]={1000000007, 1000000009};
struct chash {
    unsigned int operator()(pair<int,int> x) const { return x.first* 31 + x.second; }
};

gp_hash_table<pair<int,int>, int, chash> s;
pair<int, int> gha(int l, int r) {
    return make_pair((ha[0][r]-1ll*ha[0][l-1]*p[0][r-l+1]%mo[0]+mo[0])%mo[0], (ha[1][r]-1ll*ha[1][l-1]*p[1][r-l+1]%mo[1]+mo[1])%mo[1]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i], Dec[i-1]=arr[i-1]-arr[i]+88;
    p[0][0]=p[1][0]=1;
    for(int j=0;j<2;j++)
        for(int i=1;i<n;i++)
            p[j][i]=1ll*p[j][i-1]*177%mo[j], ha[j][i]=(1ll*ha[j][i-1]*177+Dec[i])%mo[j];
    int ans=-1, l=4, r=n-1, mid;
    char ok;
    pair<int,int> nha;
    while(l<=r) {
        mid=(l+r)>>1, ok=0;
        assert(mid);
        s.clear();
        for(int i=1;i+mid-1<n;i++) {
            nha=gha(i, i+mid-1);
            if(s[nha]>0) { if(s[nha]<i-1) {ok=1; break;} }
            else s[nha]=i+mid-1;
        }
        if(ok) l=mid+1, ans=mid;
        else r=mid-1;
    }
    cout<<ans+1<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/sol-usaco-theme.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。