乐曲主题

形式化题目

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 。

寻找一个最大的整数 $L$ ，使得序列中存在两个长度为 $L$ 的连续子串 $A[i \dots i+L-1]$ 与 $A[j \dots j+L-1]$ ，满足：

长度下限： $L \ge 5$ ；
互不重叠： $j \ge i + L$ （不妨设 $i < j$ ）；
整体转调：存在整数 $c$ ，使得对任意 $0 \le k < L$ ，均有 $A_{j+k} - A_{i+k} = c$ 。

若存在这样的子串，输出最大长度 $L$ ；若不存在满足条件的子串，输出 $0$ 。

正解

思路

1. 转调的本质：相邻差分

题目中“转调”的定义是子串中的每一个音符都加上或减去同一个常数 $c$ 。

设两段子序列分别为 $A[i \dots i+L-1]$ 和 $A[j \dots j+L-1]$ 。条件 $A_{j+k} = A_{i+k} + c$ 对所有 $0 \le k < L$ 成立，等价于相邻两个音符的差值对应相等：

A_{j+k+1} - A_{j+k} = A_{i+k+1} - A_{i+k} \quad (0 \le k < L-1)

因此，构造原序列的相邻差分数组 $D$ ：

D_k = A_{k+1} - A_k \quad (1 \le k \le N-1)

那么原序列中长度为

L

的“转调主题”，在差分数组

D

中恰好对应长度为

k = L - 1

的完全相同的连续子数组。

2. 不重叠约束的转化

原序列中两段长度为 $L$ 的子串起点分别为 $i, j$ ( $i < j$ )，不重叠要求：

j \ge i + L

将差分串长度

k = L - 1

带入，即要求：

j - i \ge k + 1

这一步的细节至关重要：虽然差分串自身的长度是

k

，但原音符子串长度是

k+1

。若差分串起点之差仅为

k

，则原序列的两个子区间会恰好在端点处重叠

1

个音符。因此必须严格满足

j - i \ge k + 1

。

3. 二分答案 + 滚动哈希判定

显然，如果存在长度为 $k$ 的合法差分匹配，那么取其前缀也一定能构成合法的长度更小的差分匹配（条件 $j - i \ge k + 1 > k' + 1$ 天然满足）。因此合法长度具有二分单调性。

我们二分差分子串的长度 $k \in [4, \lfloor N/2 \rfloor]$ （对应原串主题长度 $L = k + 1 \ge 5$ ）：

取大素数模数 $MOD = 2^{61} - 1$ 与进制基数 $BASE = 2003$ ；
利用滚动哈希（Rolling Hash）维护长度为 $k$ 的滑动窗口哈希值；
用哈希表记录每个哈希值最早出现的起始下标 first_pos[hash]；
线性扫描差分数组，若当前窗口哈希值已存在且当前下标 $i - \text{first\_pos}[\text{hash}] \ge k + 1$ ，则说明找到了合法的不重叠重复串，返回 True；否则记录首次出现的位置。

单次判定只需 $O(N)$ ，二分总耗时 $O(N \log N)$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-10-04 11:53

import sys

# 大素数模数与进制基数，避免哈希冲突
MOD: int = (1 << 61) - 1
BASE: int = 2003


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    data = iter(map(int, tokens))
    if not tokens:
        return
    n = next(data)
    notes = [next(data) for _ in range(n)]

    # 音符差分数组：转调等价于相邻差分值完全一致
    # 长度为 L 的原主题对应长度为 L - 1 的差分序列
    diff = [notes[i] - notes[i - 1] + 100 for i in range(1, n)]
    m = len(diff)

    def check(k: int) -> bool:
        """判定差分数组中是否存在两个不重叠（原序列中间隔 >= k + 1）且长度为 k 的相同子串。"""
        power = pow(BASE, k, MOD)
        cur_hash = 0
        for i in range(k):
            cur_hash = (cur_hash * BASE + diff[i]) % MOD

        first_pos: dict[int, int] = {cur_hash: 0}
        for i in range(1, m - k + 1):
            cur_hash = (cur_hash * BASE + diff[i + k - 1] - diff[i - 1] * power) % MOD
            prev = first_pos.get(cur_hash)
            if prev is not None:
                # 差分串起点相差 >= k + 1，保证原音符子串互不重叠
                if i - prev >= k + 1:
                    return True
            else:
                first_pos[cur_hash] = i
        return False

    # 二分原音符主题长度 L（要求 L >= 5，对应差分串长度 k = L - 1 >= 4）
    low, high, ans = 4, n // 2, 0
    while low <= high:
        mid = (low + high) // 2
        if check(mid):
            ans = mid + 1
            low = mid + 1
        else:
            high = mid - 1

    print(ans if ans >= 5 else 0)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:59
 * update_at: 2026-10-06 12:00
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5005;
const ll MOD = (1LL << 61) - 1; // 梅森素数 2^61-1，作为滚动哈希模数
const ll BASE = 2003;           // 滚动哈希进制基数

ll n;
ll note[MAXN];     // note[i] 表示第 i 个音符，取值 1..88
ll diff_arr[MAXN]; // diff_arr[i] = note[i+1] - note[i] + 100，转调后只需比较差分
ll m;              // 差分数组长度，等于 n - 1

// 计算 (a * b) mod (2^61-1)，用 __int128 承载中间乘积防止溢出。
ll mul_mod(ll a, ll b) {
    __int128 prod = (__int128)a * b;
    ll hi = prod >> 61;
    ll lo = prod & MOD;
    ll res = hi + lo;
    if (res >= MOD) {
        res -= MOD;
    }
    return res;
}

map<ll, ll> first_pos; // first_pos[h] = 哈希值 h 第一次出现的差分串起点

// 判定差分数组中是否存在两段长度 k 的相同子串，且起点差 >= k+1（原音符子串不重叠）。
bool check(ll k) {
    if (k <= 0 || 2 * k + 1 > m) {
        return false;
    }

    // power = BASE^k，用于滑窗时消去最高位。
    ll power = 1;
    for (ll i = 0; i < k; i++) {
        power = mul_mod(power, BASE);
    }

    ll cur = 0;
    for (ll i = 0; i < k; i++) {
        cur = (mul_mod(cur, BASE) + diff_arr[i]) % MOD;
    }

    first_pos.clear();
    first_pos[cur] = 0;
    for (ll i = 1; i + k - 1 < m; i++) {
        // 滑窗更新：整体左移一位，去掉最高位 diff_arr[i-1]，再在末尾加入 diff_arr[i+k-1]。
        cur = mul_mod(cur, BASE);
        cur = (cur - mul_mod(diff_arr[i - 1], power) + MOD) % MOD;
        cur = (cur + diff_arr[i + k - 1]) % MOD;

        map<ll, ll>::iterator it = first_pos.find(cur);
        if (it != first_pos.end()) {
            // 保留最早出现的起点，当前下标与其之差最大，最容易满足不重叠。
            if (i - it->second >= k + 1) {
                return true;
            }
        } else {
            first_pos[cur] = i;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> note[i];
    }
    m = n - 1;
    for (ll i = 1; i <= m; i++) {
        diff_arr[i - 1] = note[i + 1] - note[i] + 100;
    }

    // 二分差分串长度 k，原题要求原主题长度 L = k + 1 >= 5，故 k >= 4。
    ll low = 4;
    ll high = n / 2;
    ll ans_k = -1;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (check(mid)) {
            ans_k = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    if (ans_k >= 4) {
        cout << ans_k + 1 << "\n";
    } else {
        cout << 0 << "\n";
    }

    return 0;
}

复杂度

时间复杂度：计算差分耗时 $O(N)$ ；二分范围上界为 $N/2$ ，迭代次数为 $O(\log N)$ ；每次滑动窗口与哈希表查询耗时 $O(N)$ 。整体时间复杂度为 $O(N \log N)$ 。在 $N \le 5000$ 规模下几毫秒即可完成。
空间复杂度：存储差分数组及哈希表所需空间均为 $O(N)$ 。

总结

解决本题的关键在于两个核心转化：

转调 $\to$ 差分数组：将相对变化的加减常数转变为差分序列的绝对匹配；
原串不重叠 $\to$ 差分串间距 $\ge k + 1$ ：仔细推导端点索引，避免差分长度与原串长度混淆而导致的重叠漏洞。最后结合经典的二分答案 + 滚动哈希，在 $O(N \log N)$ 的优异复杂度下完成了全局最长公共不重叠子串的查找。

图示解析

以样例数据为例：原音符序列前一段末尾为 [45, 39, 34, 30, 26, 22]，后一段开头为 [82, 78, 74, 70, 66, 67]。

flowchart TD
    subgraph 原序列主题匹配
        A1["音符 A[15..19]: 39, 34, 30, 26, 22"]
        A2["音符 A[20..24]: 82, 78, 74, 70, 66"]
        A1 -- "每个音符 +44 (转调)" --> A2
    end
    subgraph 差分数组完全一致
        D1["差分 D[15..18]: -5, -4, -4, -4"]
        D2["差分 D[20..23]: -4, -4, -4, -4"]
        D1_sub["最长匹配长度 k=4: -4, -4, -4, -4"]
        D2_sub["最长匹配长度 k=4: -4, -4, -4, -4"]
    end

差分数组中两段起点分别为 $16$ 和 $21$ ，满足下标之差 $21 - 16 = 5 \ge 4 + 1$ ，对应原音符长度为 $4 + 1 = 5$ 的非重叠主题。

目录

形式化题目

正解

思路

1. 转调的本质：相邻差分

2. 不重叠约束的转化

3. 二分答案 + 滚动哈希判定

代码

复杂度

总结

图示解析