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

Author Avatar
空気浮遊 2018年09月07日
  • 在其它设备中阅读本文章
  • 哈希
  • 二分
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

本题是一道全面探测 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 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material