luogu2743 [USACO5.1]乐曲主题Musical Themes

题目描述

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

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

⒈长度至少为5个音符

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

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

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

本题时限为1秒钟!

输入格式

输入文件的第一行包含整数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

分析

因为有转调这个设定,我们先把原串差分一下,则相同的主题对应的串就是相同的。

如果不考虑不能重叠这个限制,那么就是一个最长重复子串。先建出SAM,然后枚举每个状态,对于$rsiz(u)\ge 2$的状态用$mx(u)$更新答案。

考虑如何判断一个串是否有不重叠的两次出现,可以记录每个状态的right集合中最小数和最大数,就很容易判断了。

代码

#include <bits/stdc++.h>

const int N = 5050;

struct Sam {
    static const int SIZ = N << 1;
    int top, last;
    int ch[SIZ][200], fa[SIZ], mx[SIZ], rsiz[SIZ];
    int rmi[SIZ], rmx[SIZ];
    int buc[N], id[SIZ];

    Sam(): top(1), last(1) {
        memset(rmi, 0x3f, sizeof rmi);
    }

    void extend(int x, int pos) {
        int p = last;
        int np = last = ++top;
        mx[np] = mx[p] + 1;
        rsiz[np] = 1;
        rmi[np] = rmx[np] = pos;
        for (; p && !ch[p][x]; p = fa[p])
            ch[p][x] = np;
        if (!p) {
            fa[np] = 1;
            return;
        }
        int q = ch[p][x];
        if (mx[q] == mx[p] + 1) {
            fa[np] = q;
            return;
        }
        int nq = ++top;
        mx[nq] = mx[p] + 1;
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        memcpy(ch[nq], ch[q], sizeof ch[nq]);
        for (; ch[p][x] == q; p = fa[p])
            ch[p][x] = nq;
    }

    void sort() {
        for (int i = 1; i <= top; i++)
            buc[mx[i]]++;
        for (int i = 1; i <= mx[last]; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i <= top; i++)
            id[buc[mx[i]]--] = i;
    }

    void work() {
        sort();
        for (int i = top; i >= 2; i--) {
            int u = id[i];
            rsiz[fa[u]] += rsiz[u];
            rmi[fa[u]] = std::min(rmi[fa[u]], rmi[u]);
            rmx[fa[u]] = std::max(rmx[fa[u]], rmx[u]);
        }
    }
} sam;

int n, a[N];

int solve() {
    int ans = 0;
    for (int i = 1; i <= sam.top; i++) {
        int len = std::min(sam.mx[i], sam.rmx[i] - sam.rmi[i] - 1);
        if (sam.rsiz[i] >= 2 && len >= 4)
            ans = std::max(ans, len+1);
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (i > 0)
            sam.extend(a[i] - a[i-1] + 88, i);
    }
    sam.work();
    printf("%d\n", solve());
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论