2026牛客暑期多校 8——M-KV 缓存 · znzryb
## 题目大意
### 题目:KV 缓存
### 题目描述
Soy 正在运行一个大型语言模型(LLM)服务。为了避免为不同的请求重复计算相同的前缀,该服务维护了一个持久化的 KV 缓存。
每个请求由一个由小写拉丁字母组成的字符串表示,其中每个字母代表一个 token。具有公共前缀的请求可以共享 KV 缓存条目。我们将缓存的当前内容建模为一棵字典树(Trie)。
最初,这棵字典树只包含根节点,没有任何边。
在处理请求字符串 $s$ 时,按顺序执行以下操作:
1. Soy 从左到右处理整个字符串,从字典树的根节点开始。
1. 如果下一个 token 对应的边已经存在,则无需任何代价即可复用其缓存结果。
1. 否则,Soy 必须计算相应的 KV 状态。这需要消耗 $1$ 个单位的计算代价,并且缺失的边会被添加到字典树中。
整个请求在任何缓存条目被删除之前会被完整地处理。特别地,请求中所有缺失的边会首先被添加,即使这会暂时使字典树包含超过 $m$ 条边。
在处理完整个请求后,Soy 会应用持久化缓存的大小限制。如果字典树包含超过 $m$ 条边,他必须不断地删除一个叶子节点以及连接它与其父节点的边,直到字典树恰好剩下 $m$ 条边。叶子节点是指在当前字典树中没有子节点的顶点。在处理当前请求时新添加的边也可以在此修剪步骤中被删除。
Soy 提前知道完整的 $n$ 个请求序列。在每次修剪步骤中,他可以选择删除哪些叶子节点的边。
请计算处理所有 $n$ 个请求所需的最小可能总计算代价。
> 字典树(Trie)是一种将一组字符串存储为有根树的数据结构。该树具有以下结构:树的每条边都标记有一个字母,同一个节点连出的边中,不存在两条标记相同字母的边。每个字符串可以通过沿着从根节点到某个顶点的路径来读取。
例如,我们可以为字符串 "`min`"、"`trie`"、"`task`" 和 "`mini`" 构建一棵字典树,它看起来像这样:

### 输入描述
每个测试用例的第一行包含两个整数 $n$ 和 $m$($1 \le n \le 10^6$,$1 \le m \le 10^9$)。
接下来的 $n$ 行中,第 $i$ 行包含一个字符串 $s_i$ —— 表示第 $i$ 个请求的 token 序列。保证 $s_i$ 仅由小写拉丁字母组成。保证所有字符串的长度之和 $\sum \vert{}s_i\vert{}$ 不超过 $10^6$。
### 输出描述
输出一个整数 —— 处理所有 $n$ 个请求的最小总计算代价。
### 样例
<!-- Notion block type: heading_4 -->
```
4 4
mini
trie
task
min
```
<!-- Notion block type: heading_4 -->
```
11
```
<!-- Notion block type: heading_4 -->

在本样例中,缓存的边数限制为 $m = 4$。一种最优的计算和修剪策略如下:
1. **处理第一个请求** **`mini`**:依次添加边 `m`、`i`、`n`、`i`。计算代价为 $4$。此时字典树有 $4$ 条边,未超过限制,无需修剪。
1. **处理第二个请求** **`trie`**:从根节点开始添加边 `t`、`r`、`i`、`e`。计算代价为 $4$。此时字典树包含 $8$ 条边,超出了 $m=4$ 的限制,需要修剪掉 $4$ 条边。我们可以选择删掉第一条链末尾的 `i` 以及第二条链后方的 `r-i-e`,只保留边 `m-i-n` 和 `t`(共计 $4$ 条边)。
1. **处理第三个请求** **`task`**:复用已有的边 `t`(代价为 $0$),然后依次添加边 `a`、`s`、`k`。计算代价为 $3$。处理后字典树包含 $7$ 条边,需要修剪掉 $3$ 条边。我们选择修剪掉刚增加的 `a-s-k`,继续保留 `m-i-n` 和 `t`(共计 $4$ 条边)。
1. **处理第四个请求** **`min`**:边 `m-i-n` 已经完整存在于字典树中,可以直接复用全部 token,因此无需新建任何边。计算代价为 $0$。此时树中有 $4$ 条边,无需修剪。
所有请求的总计算代价为 $4 + 4 + 3 + 0 = 11$。这也是在所有可能修剪策略中能达到的最小总计算代价。
## 思路讲解
问:题目相当于在每一次请求结束后,保留最多 $m$ 条边,如何将其转化为经典的缓存问题?
问:在**传统的离线场景下(已知所有未来的访问序列)**,**最优的缓存替换策略**是什么?
问:直接对字典树的节点使用 Belady 策略,是否会违反“保留子节点必须保留父节点”的树形修剪约束?
问:如何高效模拟这一带有深度优先约束的贪心淘汰过程?

那么我们所谓的这个每个节点的数组啊,其实就是这个代码中的 visits 数组。
```cpp
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 数组记一下在不在缓存**中就可以了。
```cpp
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});
}
```
```cpp
// 整个请求处理完毕后,开始应用缓存大小的限制
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--;
}
```
```cpp
#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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84468178)
::: 源代码(AI)
```cpp
#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
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84471363](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84471363)
::: 我的代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define i128 __int128_t
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const ll MOD = 0, INF = 1e18;
const ll MAXN = (ll)1e6 + 10;
const char BASE = 'a';
struct Con {
ll u;
ll nxt;
ll dep;
bool operator<(const Con &o) const {
if (nxt != o.nxt)
return nxt < o.nxt;
return dep < o.dep;
}
};
void solve() {
ll n, m;
cin >> n >> m;
vector<string> S(n);
ll tot = 0;
ll acc_len = 0;
for (int i = 0; i < n; ++i) {
cin >> S[i];
acc_len += S[i].size();
}
vector<vector<int>> Trie(acc_len + 2, vector<int>(26));
vector<vector<int>> vis_tims(acc_len + 2);
auto insert = [&](const string &ls, ll tim) {
ll u = 0;
for (auto c : ls) {
if (Trie[u][c - BASE] == 0) {
++tot;
Trie[u][c - BASE] = tot;
u = tot;
vis_tims[u].push_back(tim);
} else {
u = Trie[u][c - BASE];
vis_tims[u].push_back(tim);
}
}
};
priority_queue<Con> pq;
for (int i = 0; i < n; ++i) {
insert(S[i], i);
}
vector<char> in_memo(tot + 2);
ll ans = 0;
ll curSZ = 0;
auto insert_memo = [&](const string &ls, ll tim) -> void {
ll u = 0;
ll dep = 0;
for (auto c : ls) {
ll to = Trie[u][c - BASE];
dep++;
if (!in_memo[to]) {
in_memo[to] = true;
curSZ++;
++ans;
}
auto it = upper_bound(all(vis_tims[to]), tim);
ll nxt = INF;
if (it != vis_tims[to].end()) {
nxt = *it;
}
pq.push({to, nxt, dep});
u = to;
}
};
auto pop_pq = [&](ll tim) {
auto [u, nxt1, sz] = pq.top();
pq.pop();
ll nxt2 = INF;
auto it = upper_bound(all(vis_tims[u]), tim);
if (it != vis_tims[u].end()) {
nxt2 = *it;
}
if (nxt1 == nxt2) {
in_memo[u] = false;
curSZ--;
}
};
// for (int i = 0; i <= tot; ++i) {
// cerr << i << ":";
// for (int j = 0; j < 26; ++j) {
// cerr << Trie[i][j] << " ";
// }
// cerr << "\n";
// }
for (int i = 0; i < n; ++i) {
insert_memo(S[i], i);
while (curSZ > m) {
pop_pq(i);
}
// cerr << "in_memo:";
// for (int i = 0; i <= tot; ++i) {
// cerr << (int)in_memo[i] << " ";
// }
// cerr << "\n";
}
cout << ans << "\n";
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
// ll t = 1;
// cin >> t;
// while (t--)
solve();
return 0;
}
/*
....................X/......................../X...............X/../X.............X/................
.................../X.........................X/............../X.../X.............//................
...................X/........................X/............../X/...X/............./X................
..................X/......................../X...............X/.../X............../X/...............
................./X/........................X/............../X..../X...............X/...............
.................X/......................../X...............X/....X/...............X/...............
................/X.........................X/............../X..../X/...............//...............
................X/......................../X.............../X..../X................/X...............
................X/......................./XX..//X/.........X/....X/................/X...............
.............../X....................../X//XXXX//........./X/....X/................/X...............
.............../XXX//////////////////XXXX/XX//............/X.....X/................/X...............
...............//./////XXXXXXXXXX/XXX/... //............../X..../X................./X...............
...............X/...............///.. //............../X..../X............../X.XX/..............
............../X/............////. .X............../X/...X/...............XX//X/.............
............../X..........////.. .X/..............X/...X/................XX..X.............
............../X......////.. //............../X../X................./XX./X............
..............X/./////... .X/............./X/./X.................X..XXXX...........
............//XX//.. .. ./X............../X./X................// ../XX//........
........../XXXXXXXXXX///..... ........///..............X///................X. .XXXX//.....
....../XXXXXXXXXXXXXXXXXXXXXXXX//... ..././/..............XX/...............// .X//XXXX///
....../////XXXXXX XXXXXXXXXXXXXXXXXXX//.. .. .//............./........//.....// ./....////
..........XXXXXXX .XXXX/ XXXXXXXXXXXXXXXXXXXX. .//................./////X./..// //.......
........./XXXXXXX .XXXX XXXXXXXXXXXXXXXXXXX/. ///..........//////.. .XXX//X. .X.......
........./XXXXXXXX X/ XXXXXXXXXXXXXXXXXXXXX. ..///////////... XX/.X/....... //......
..........XXXXXXXX XXXXXXXXXXXXXXXXXXXX... ....... ./XXX/X/... . .X/.....
..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX .XXXXXXXXXXXXX///.... /X.....
........../XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX. .XXX /XXXXXXXXXXXXXXXXXX//.///....
.........../XXXXXXXXXXXXXXXXXXXXXXXXXXXXX. /XXX XXXX XXXXXXXXXXXXXXXXXXX//.
.........../XXXXXXXXXXXXXXXXXXXXXXXXXXX/. /XXXX XXXX XXXXXXXXXXXXXXXXXXX/...
...........// .//XXXXXXXXXXXXXXXXXXXX. .XXXX XX XXXXXXXXXXXXXXXXXXXXX/..
...........// ......//XXXXX////..... /XXXXX XXXXXXXXXXXXXXXXXX/ /X/X/.
...........//...... .. .... .. .XXXXXXXXXXXXXXXXXXXXXXXXXXX .X/....
...........//................... .XXXXXXXXXXXXXXXXXXXXXXXXX/./XX/....
...........//.................... ./XXXXXXXXXXXXXXXXXXXXXXX/////X.....
...........//.................... .//////XXXXXXXXXXXXX/////..X/..../
...........// ................... ../XXX////XXX//..///..../X..//XX
.........../X/. .............. // .......... .//......X///X//X
.........../X///. ........ // ....... .. .... //......./X///../X
............X. .//.. //////////// ................. .//.............../X
............X/ ./XX.. ../. /////////// ..................X/................/X
.......//...XX////..//.... ./...X. ////. .............. ..//................./X
.......X/...// .....// .X . ............ .//...................X/
......./X/...X. .X.X. /. .... ....... ../X/.................../X/
......./X//..// XX // // ./...// ...///...................../X.
//////.// .///X. .X..X .X... /. ./ .......//////...............//...../X/.
....X/// ..// .X.X. //./.........//. .X.../X//////X/.............../////X....X/..
.. ... ///. ./ .........XX. /. //...//XX.............//////./X../X/...
... ./// .X........ .X. ./. .X.///./X.........///////.....X/////....
.... .X/ /. ..... ./. ./. //... .X////X//X/////......../X///......
. ./. /X ./......// ./. .// ..///.....................
*/
```
:::
## 心路历程(WA,TLE,MLE……)