本题是一道全面探测 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://pst.iorinn.moe/archives/sol-usaco-theme.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆