旋律压缩

形式化题目

给定一个行程长度编码字符串 $s'$ ：由若干"小写字母 + 十进制正整数"段组成，第 $i$ 段 $(ch_i, cnt_i)$ 表示 $cnt_i$ 个连续音符 $ch_i$ ，解压得到原始旋律串 $S$ （长度为 $L$ ）。

求 $S[c \bmod L]$ ，即旋律无限循环播放时第 $c$ 个音符（从 0 开始编号），输出该小写字母。 $L$ 可能高达约 $1.4 \times 10^{16}$ ，不能显式构造 $S$ 。

思路

一句话本质：无限循环只是周期重复，任意大的 $c$ 先用 $k = c \bmod L$ 折回单周期；压缩串按"字母 + 连续数字"解析成段后，用前缀和区间定位 $k$ 落在哪一段，输出该段音符。

先看一个直接按题面展开的朴素解，它只适合小数据：

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/**
 * 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-08-28 21:26
 * update_at: 2026-08-28 21:26
 */
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 思路：按压缩规则把压缩串直接展开成完整的旋律字符串，
// 再按下标 c % len 直接取第 c 个音符。展开的长度受小数据限制。

string s;     // 压缩旋律串
long long c;  // 询问的第 c 个音符

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

    cin >> s >> c;

    // 展开：先读一个字母，再把后面连续的数字拼成次数。
    string melody;
    int n = (int)s.length();
    int i = 0;
    while (i < n) {
        char ch = s[i];
        i++;
        long long cnt = 0;
        while (i < n && s[i] >= '0' && s[i] <= '9') {
            cnt = cnt * 10 + (s[i] - '0');
            i++;
        }
        for (long long j = 0; j < cnt; j++) {
            melody.push_back(ch);
        }
    }

    // 无限循环 = 周期重复，取余后直接按下标取音符。
    long long k = c % (long long)melody.length();
    cout << melody[k] << '\n';

    return 0;
}

问题？ 压缩串里的每一段到底代表什么？

每段是"音符 + 连续出现次数"：a4b1c2d4 表示 4 个 a、1 个 b、2 个 c、4 个 d。解析时先读一个字母，再把后面连续的数字逐位拼成次数——次数可能占多位（d10 表示 10 个 d，不是 d 和 1 和 0）。这一步只是把输入翻译成 $(ch, cnt)$ 段，还没有碰到核心问题。

问题？ 无限循环播放时，第 $c$ 个音符落在哪里？

循环就是周期重复：旋律每 $L$ 个音符回到完全相同的状态。把 $c$ 写成 $c = qL + k$ ，前 $q$ 个完整周期不影响位置，所以第 $c$ 个音符 = 单周期内第 $k$ 个音符，其中 $k = c \bmod L$ 。这就是样例 2 的做法： $L = 17$ ， $100 \bmod 17 = 15$ ，只查单周期内第 15 个（0 基）音符。

问题？ 知道 $k$ 后，如何不展开旋律就找到对应音符？

给段做前缀和：第 $i$ 段覆盖区间 $[\text{pre}_i, \text{pre}_i + \text{cnt}_i)$ ，这些区间互不相交、并成 $[0, L)$ ，所以 $k$ 恰好落在唯一一段中。从左到右第一个满足 $\text{pre}_i + \text{cnt}_i > k$ 的段就是答案段。仍以样例 2 为例：a4 覆盖 $[0,4)$ ，b1 覆盖 $[4,5)$ ，c2 覆盖 $[5,7)$ ，d10 覆盖 $[7,17)$ ； $k = 15$ 落在 d 段，输出 d。

问题？ 为什么不能真的把旋律展开？

单周期长度最多约 $\frac{2 \times 10^5}{14} \times 10^{12} \approx 1.4 \times 10^{16}$ ，展开必然超时超内存。但压缩串本身只有 $2 \times 10^5$ 个字符，解析一遍、前缀和扫一遍都是 $O(|s'|)$ ，这就是压缩存在的意义。

代码

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/**
 * 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-08-28 21:26
 * update_at: 2026-08-28 21:26
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

string s;           // 压缩旋律串，只含小写字母和数字
long long c;        // 询问的第 c 个音符，从 0 开始编号
int m;              // 段的个数
char chs[MAXN];     // chs[i]：第 i 段的音符
long long cnts[MAXN]; // cnts[i]：第 i 段音符连续出现的次数
long long sum;      // 单周期总长度 L

// 把压缩串解析成 (音符, 次数) 段，并累加单周期长度。
void parse() {
    int n = (int)s.length();
    int i = 0;
    while (i < n) {
        chs[++m] = s[i]; // 当前位置一定是字母（音符）
        i++;
        long long cnt = 0;
        // 次数可能占多位数字，如 d10 表示 10 个 d，逐位拼出来。
        while (i < n && s[i] >= '0' && s[i] <= '9') {
            cnt = cnt * 10 + (s[i] - '0');
            i++;
        }
        cnts[m] = cnt;
        sum += cnt;
    }
}

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

    cin >> s >> c;

    parse();

    // 无限循环：第 c 个音符只取决于它在单周期内的位置 k = c mod L。
    c %= sum;

    // 前缀和定位：第 i 段覆盖区间 [pre, pre + cnts[i])，
    // 第一个 pre + cnts[i] > c 的段就是答案段。
    long long pre = 0;
    for (int i = 1; i <= m; i++) {
        if (pre + cnts[i] > c) {
            cout << chs[i] << '\n';
            return 0;
        }
        pre += cnts[i];
    }

    return 0;
}

复杂度

时间： $O(|s'|)$ ，解析一遍压缩串，前缀和定位一遍段数组；
空间： $O(|s'|)$ ，存储段数组 chs[] / cnts[]。

总结

循环 = 取模：周期性重复的问题，第一步总是把大下标折回单周期；
压缩串解析：行程长度编码的解析要小心多位数字次数，逐位拼数即可；
段粒度定位：把"字符下标"查询改成"段区间"查询，一次前缀和扫描完成，不需要真的展开字符串。

目录

形式化题目

思路

代码

复杂度

总结