Znzryb's Blog
0%

2026牛客暑期多校 8——M-KV 缓存

Posted on Edited on

题目大意

题目：KV 缓存

题目描述

Soy 正在运行一个大型语言模型（LLM）服务。为了避免为不同的请求重复计算相同的前缀，该服务维护了一个持久化的 KV 缓存。

每个请求由一个由小写拉丁字母组成的字符串表示，其中每个字母代表一个 token。具有公共前缀的请求可以共享 KV 缓存条目。我们将缓存的当前内容建模为一棵字典树（Trie）。

最初，这棵字典树只包含根节点，没有任何边。

在处理请求字符串 ss 时，按顺序执行以下操作：

  1. Soy 从左到右处理整个字符串，从字典树的根节点开始。

  2. 如果下一个 token 对应的边已经存在，则无需任何代价即可复用其缓存结果。

  3. 否则，Soy 必须计算相应的 KV 状态。这需要消耗 11 个单位的计算代价，并且缺失的边会被添加到字典树中。

整个请求在任何缓存条目被删除之前会被完整地处理。特别地，请求中所有缺失的边会首先被添加，即使这会暂时使字典树包含超过 mm 条边。

在处理完整个请求后，Soy 会应用持久化缓存的大小限制。如果字典树包含超过 mm 条边，他必须不断地删除一个叶子节点以及连接它与其父节点的边，直到字典树恰好剩下 mm 条边。叶子节点是指在当前字典树中没有子节点的顶点。在处理当前请求时新添加的边也可以在此修剪步骤中被删除。

Soy 提前知道完整的 nn 个请求序列。在每次修剪步骤中，他可以选择删除哪些叶子节点的边。

请计算处理所有 nn 个请求所需的最小可能总计算代价。

字典树（Trie）是一种将一组字符串存储为有根树的数据结构。该树具有以下结构：树的每条边都标记有一个字母，同一个节点连出的边中，不存在两条标记相同字母的边。每个字符串可以通过沿着从根节点到某个顶点的路径来读取。
例如，我们可以为字符串 “min”、“trie”、“task” 和 “mini” 构建一棵字典树，它看起来像这样：
image

输入描述

每个测试用例的第一行包含两个整数 nn 和 mm（1≤n≤1061 \le n \le 10^6，1≤m≤1091 \le m \le 10^9）。

接下来的 nn 行中，第 ii 行包含一个字符串 sis_i —— 表示第 ii 个请求的 token 序列。保证 sis_i 仅由小写拉丁字母组成。保证所有字符串的长度之和 ∑∣si∣\sum \vert{}s_i\vert{} 不超过 10610^6。

输出描述

输出一个整数 —— 处理所有 nn 个请求的最小总计算代价。

样例

1
2
3
4
5
4 4
mini
trie
task
min
1
11

image

在本样例中，缓存的边数限制为 m=4m = 4。一种最优的计算和修剪策略如下：

  1. 处理第一个请求 mini：依次添加边 m、i、n、i。计算代价为 44。此时字典树有 44 条边，未超过限制，无需修剪。

  2. 处理第二个请求 trie：从根节点开始添加边 t、r、i、e。计算代价为 44。此时字典树包含 88 条边，超出了 m=4m=4 的限制，需要修剪掉 44 条边。我们可以选择删掉第一条链末尾的 i 以及第二条链后方的 r-i-e，只保留边 m-i-n 和 t（共计 44 条边）。

  3. 处理第三个请求 task：复用已有的边 t（代价为 00），然后依次添加边 a、s、k。计算代价为 33。处理后字典树包含 77 条边，需要修剪掉 33 条边。我们选择修剪掉刚增加的 a-s-k，继续保留 m-i-n 和 t（共计 44 条边）。

  4. 处理第四个请求 min：边 m-i-n 已经完整存在于字典树中，可以直接复用全部 token，因此无需新建任何边。计算代价为 00。此时树中有 44 条边，无需修剪。

所有请求的总计算代价为 4+4+3+0=114 + 4 + 3 + 0 = 11。这也是在所有可能修剪策略中能达到的最小总计算代价。

思路讲解

问：题目相当于在每一次请求结束后，保留最多 mm 条边，如何将其转化为经典的缓存问题？

问：在传统的离线场景下（已知所有未来的访问序列），最优的缓存替换策略是什么？

问：直接对字典树的节点使用 Belady 策略，是否会违反“保留子节点必须保留父节点”的树形修剪约束？

问：如何高效模拟这一带有深度优先约束的贪心淘汰过程？

image

那么我们所谓的这个每个节点的数组啊，其实就是这个代码中的 visits 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<string> s(n + 1);
for (int i = 1; i <= n; ++i) {
    cin >> s[i];
    int u = 1; 
    for (char c : s[i]) {
        int idx = c - 'a';
        if (!ch[u][idx]) {
            ch[u][idx] = ++tot;
            depth[tot] = depth[u] + 1;
        }
        u = ch[u][idx];
        // 记录该节点在第 i 个请求中被访问
        // 因为是从左到右处理字符串，所以每个节点在同一次请求中最多被记录一次
        visits[u].push_back(i);
    }
}

然后我们删节点的话也不用真的去删除啊，就用一个这个 in_cache 数组记一下在不在缓存中就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for (char c : s[i]) {
    int idx = c - 'a';
    u = ch[u][idx];

    // 如果该节点当前不在缓存中，需要计算 1 个单位代价并将其加入缓存
    if (!in_cache[u]) {
        total_cost++;
        in_cache[u] = true;
        cache_size++;
    }

    // 更新该节点的访问指针，定位到下一次被访问的时间
    // 比我们的二分聪明一点啊
    visit_ptr[u]++;
    int next_access = INF;
    // 如果大于的话，下一次访问时间就是 INF
    if (visit_ptr[u] < visits[u].size()) {
        next_access = visits[u][visit_ptr[u]];
    }

    // 记录该节点最新版本的下一次访问时间，并压入堆中
    cur_next[u] = next_access;
    pq.push({next_access, depth[u], u});
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 整个请求处理完毕后，开始应用缓存大小的限制
while (cache_size > m) {
    auto [na, d, v] = pq.top();
    pq.pop();

    // 延迟删除：如果堆顶元素记录的时间戳与最新状态不一致，说明是失效的旧记录，直接忽略
    // 这个是由于堆当中可能有多个这个版本的记录啊
    if (na != cur_next[v]) {
        continue;
    }

    // 万一节点已经被剔除出缓存，也直接忽略
    if (!in_cache[v]) {
        continue;
    }

    // 将该最不该保留的节点淘汰出缓存
    in_cache[v] = false;
    cache_size--;
}
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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>

using namespace std;

const int INF = 1e9;
const int MAXN = 1000005;

// 字典树相关
int ch[MAXN][26];
int depth[MAXN];
int tot = 1; // 1 表示根节点

vector<int> visits[MAXN]; // visits[u] 记录节点 u 被访问到的所有请求编号
int visit_ptr[MAXN];      // 用于遍历 visits[u] 的指针

bool in_cache[MAXN];      // 记录节点当前是否在 KV 缓存中
int cur_next[MAXN];       // 记录节点当前最新的“下一次访问时间”

int main() {
    // 优化标准输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<string> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        int u = 1; 
        for (char c : s[i]) {
            int idx = c - 'a';
            if (!ch[u][idx]) {
                ch[u][idx] = ++tot;
                depth[tot] = depth[u] + 1;
            }
            u = ch[u][idx];
            // 记录该节点在第 i 个请求中被访问
            // 因为是从左到右处理字符串，所以每个节点在同一次请求中最多被记录一次
            visits[u].push_back(i);
        }
    }

    long long total_cost = 0;
    int cache_size = 0;

    // 大根堆，用于模拟 Belady 最优缓存替换策略
    // 存储元组: (下一次访问时间, 节点深度, 节点ID)
    // C++ 默认的 max-heap 会优先弹出 下一次访问时间最大 的节点，
    // 若时间相同，则优先弹出 深度最大 的节点（即树的叶子），符合题意
    priority_queue<tuple<int, int, int>> pq;

    for (int i = 1; i <= n; ++i) {
        int u = 1;
        for (char c : s[i]) {
            int idx = c - 'a';
            u = ch[u][idx];

            // 如果该节点当前不在缓存中，需要计算 1 个单位代价并将其加入缓存
            if (!in_cache[u]) {
                total_cost++;
                in_cache[u] = true;
                cache_size++;
            }

            // 更新该节点的访问指针，定位到下一次被访问的时间
            visit_ptr[u]++;
            int next_access = INF;
            if (visit_ptr[u] < visits[u].size()) {
                next_access = visits[u][visit_ptr[u]];
            }

            // 记录该节点最新版本的下一次访问时间，并压入堆中
            cur_next[u] = next_access;
            pq.push({next_access, depth[u], u});
        }

        // 整个请求处理完毕后，开始应用缓存大小的限制
        while (cache_size > m) {
            auto [na, d, v] = pq.top();
            pq.pop();

            // 延迟删除：如果堆顶元素记录的时间戳与最新状态不一致，说明是失效的旧记录，直接忽略
            if (na != cur_next[v]) {
                continue;
            }

            // 万一节点已经被剔除出缓存，也直接忽略
            if (!in_cache[v]) {
                continue;
            }

            // 将该最不该保留的节点淘汰出缓存
            in_cache[v] = false;
            cache_size--;
        }
    }

    cout << total_cost << "\n";

    return 0;
}

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84468178

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84471363

心路历程（WA，TLE，MLE……）