每天的字符串集合是前缀封闭的,恰为一棵 Trie 的结点集;编辑距离就是树上距离。三天答案化为子树大小、换根距离和与一次 LCA 配对 DP。
OJ: roj
题目 ID: 1704
难度:提高+/省选-
标签:字符串Trie树形DP换根DPpython
创建: 2026-10-07 17:18
更新: 2026-10-07 17:18
形式化题目
键盘只有两种操作:敲一个字符(追加到串尾)、按退格(删除串尾一个字符)。三天各给出
一串按键(
其中
第 1 天:求
第 2 天:选定特殊串
第 3 天:选定
求
输出三行,每行两个整数(该天的最小值与最大值)。
以样例 1 为例,三天按键分别是 97、97、97 8 97 8,于是
a、退格、再敲 a,集合没有新增元素)。
第 1 天 10 10。
正解
思路
关键观察一:集合就是 Trie 的结点集。 光标永远在串尾,敲字符 = 从当前结点走一个孩子,
退格 = 回父结点。所以"屏幕出现过的串"就是走出来的所有结点,
正是树上距离。记
关键观察二:跨集合的那
其中
同理第 3 天的三项分别是
把固定项合起来,第 3 天的总距离为
最小值把三个
(用一个恒等式可以自检:取
关键观察三:三个基础统计量都是一次 DFS。 设结点数
——每条边 恰好被 "一侧在子树内、一侧在子树外"的点对跨过; ,换根 (从父结点走进子树,子树内 个点里有 个近了 ,其余 个远了 ); 、 扫一遍即可。
最大值里的配对项。 唯一麻烦的是第 3 天最大值的最后一项
代入
就得到
:值 ; - 一端是
、另一端在某个孩子子树 内: , 其中 , 同理对 ; - 两端分别在两个不同的孩子子树里:边合并边记"已合并子树的最值"
(
与 ), 这样天然保证两端来自不同子树, 正好是 。
三种情况都算完再减去
实现上的两个简化。 一是建 Trie 时按创建顺序给结点编号,父结点的编号一定小于子结点,
于是"按编号倒序扫一遍"就是子树大小的拓扑序,"正序扫一遍"就是换根 DP 的拓扑序,
连显式 DFS 都不用写。二是孩子查找:把
关于数据。 本题素材目录里带 data.py(生成器),说明 data/ 是自造的,
题面也是网络重建版本,出题意图与官方原题可能存在偏差。第 10 个点是 long long。
代码
Python 版:
#!/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-10-07 17:18
# update_at: 2026-10-07 17:18
import sys
NEG = -(1 << 62) # 配对 DP 里的"不存在"哨兵,比任何合法权值都小
def build_tree(keys: list[int]) -> tuple[list[int], list[int], list[int]]:
"""按键序列建 Trie(退格 8 表示回父结点),返回 (父结点, 深度, 子树大小)。
集合 S 恰好是这棵 Trie 的结点集:光标在串尾,走一步就是一个孩子,
退格就是回父结点。字符键用 父结点*256 + ASCII 编码,同一个 (结点, 字符) 只会开一个点。
"""
parent, depth, size = [-1], [0], [1] # 结点 0 = 空串 = 根
child: dict[int, int] = {}
cur = 0
for k in keys:
if k == 8:
cur = parent[cur] if cur else 0
else:
key = cur * 256 + k
nxt = child.get(key, -1)
if nxt < 0: # 这个字符还没出现过,现场开点
nxt = len(parent)
child[key] = nxt
parent.append(cur)
depth.append(depth[cur] + 1)
size.append(1)
cur = nxt
for v in range(len(parent) - 1, 0, -1): # 结点编号即拓扑序,父结点编号一定更小
size[parent[v]] += size[v]
return parent, depth, size
def day_stat(parent: list[int], depth: list[int], size: list[int]) -> tuple[int, int, int, int, list[int]]:
"""算一天的统计量:返回 (结点数, 两两距离和 W, min D, max D, 每点到全集合的距离和 D)。"""
n = len(parent)
# 每条边 (parent[v], v) 被两侧点的每一对跨过:一侧 size[v] 个点,另一侧 n - size[v] 个
W = sum(size[v] * (n - size[v]) for v in range(1, n))
D = [sum(depth)] + [0] * (n - 1) # 根(空串)到所有点的距离和 = 所有点的深度和
for v in range(1, n): # 换根:从父结点走进子树,子树内的点都近 1,其余点都远 1
D[v] = D[parent[v]] + n - 2 * size[v]
return n, W, min(D), max(D), D
def best_pair(parent: list[int], depth: list[int], D: list[int], coef_a: int, coef_c: int) -> int:
"""在 B 上求 max[nA*D[x] + nC*D[y] + L*d(x,y)],L = nA*nC(第 3 天最大值的那一项)。
用 d(x,y) = depth[x] + depth[y] - 2*depth(lca) 拆开,改成对每个结点 v 只统计
"lca 恰好是 v"的配对:倒序扫编号,孩子子树先并入 v 的候选(孩子编号一定更大)。
"""
n = len(parent)
L = coef_a * coef_c
F = [coef_a * D[v] + L * depth[v] for v in range(n)] # x 取 v 时的权值
G = [coef_c * D[v] + L * depth[v] for v in range(n)] # y 取 v 时的权值
cross = [F[v] + G[v] for v in range(n)] # lca = v 的候选答案(先放 x = y = v)
best0, best1 = F[:], G[:] # 子树内 max F / max G,初始含 v 自身
ans = NEG
for v in range(n - 1, -1, -1):
ans = max(ans, cross[v] - 2 * L * depth[v]) # 扣掉 lca 以上多算的两段深度
p = parent[v]
if p >= 0: # 把孩子子树并入父结点:父结点已并入的部分与 v 的子树一定不相交
cross[p] = max(cross[p], best0[p] + best1[v], best1[p] + best0[v])
best0[p] = max(best0[p], best0[v])
best1[p] = max(best1[p], best1[v])
return ans
def solve() -> None:
# 一天恰好一行,空行表示该天只按过退格(集合只有空串),所以不能过滤空行;
# 退格 8 与字符含义不同、必须按行分组,这也是这里按行读入而不是 next() 顺序消费的原因
raw = sys.stdin.buffer.read().split(b'\n')
days = [(raw[i] if i < len(raw) else b'') for i in range(3)]
keys = [[int(x) for x in ln.split()] for ln in days]
info = [day_stat(*build_tree(k)) for k in keys]
(nA, WA, dAmin, dAmax, DA), (nB, WB, dBmin, dBmax, DB), (nC, WC, dCmin, dCmax, DC) = info
parB, depB, _ = build_tree(keys[1])
# 第 1 天:A 内部两两距离之和
day1 = WA
# 第 2 天:A×B 的对距离为 d(P,A0)+1+d(B0,Q),展开后 A0 的系数是 nB,B0 的系数是 nA
day2min = WA + WB + nA * nB + nB * dAmin + nA * dBmin
day2max = WA + WB + nA * nB + nB * dAmax + nA * dBmax
# 第 3 天:A×C 的对多走一趟 B0→B1,故 A0 系数 nB+nC、C0 系数 nA+nB,B0/B1 分别带 nA/nC
base = WA + WB + WC + nA * nB + nB * nC + 2 * nA * nC
day3min = base + (nB + nC) * dAmin + (nA + nB) * dCmin + (nA + nC) * dBmin
day3max = base + (nB + nC) * dAmax + (nA + nB) * dCmax + best_pair(parB, depB, DB, nA, nC)
print(f"{day1} {day1}")
print(f"{day2min} {day2max}")
print(f"{day3min} {day3max}")
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-07 17:18
* update_at: 2026-10-07 17:18
*/
// main.cpp:奇特的猫(一本通 1704)。
// 每天按键产生的所有屏幕字符串(含空串)构成一个前缀封闭集合 S,恰好是一棵 Trie 的结点集,
// 串间编辑距离 d(P,Q)=|P|+|Q|-2*LCP(P,Q) 正是这棵 Trie 上的树距。
// 于是三天的答案都归结为 Trie 上的统计:子树大小、换根距离和、以及一次自底向上的配对 DP。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXNODE = 1000005; // 单天 Trie 的结点数上限:|S| ≤ 10^6,再加一个根
const int HASH_BITS = 22; // 孩子查找哈希表大小 2^22,装载因子 ≤ 1/4
const int HASH_SIZE = 1 << HASH_BITS;
const int HASH_MASK = HASH_SIZE - 1;
const ll NEG_INF = -(1LL << 62); // DP 里的"不存在"哨兵
struct Node {
int parent; // 父结点编号,根(空串)为 -1
int depth; // 深度 = 该结点代表的字符串长度
int firstChild; // 孩子链表的头,-1 表示叶子
int nextSibling; // 兄弟链表的后继
int subSize; // 子树结点个数
int ch; // 从父结点下来的那个字符(ASCII 值;用 int 免去字符与键之间的转换)
ll distSum; // 到本集合内所有结点的距离之和
};
Node trie[MAXNODE]; // 结点 v 就是 trie[v],编号按创建顺序分配,父结点编号一定小于子结点
int nodeCnt; // 已经创建的结点个数(编号 0..nodeCnt-1)
// 孩子哈希表:键 = 父结点编号 * 256 + 字符。键与 (结点, 字符) 一一对应,
// 因此不存在"两个不同的孩子落到同一个键"的情况,只需处理桶下标冲突。
// 0xFFFFFFFF 是空槽标记(真实键最大只有 1e6*256 ≈ 2.6e8)。
unsigned hashKey[HASH_SIZE];
int hashVal[HASH_SIZE];
ll bestB0[MAXNODE]; // bestB0[v] = 子树 v 内 max(nA*D[x] + L*depth[x]),供第 3 天取 b0 用
ll bestB1[MAXNODE]; // bestB1[v] = 子树 v 内 max(nC*D[x] + L*depth[x]),供第 3 天取 b1 用
ll dayN[3]; // 三天的 |S|
ll dayW[3]; // 三天的集合内两两距离之和
ll dayDmin[3]; // 三天里 min_v (v 到集合内所有点的距离和)
ll dayDmax[3]; // 三天里 max_v (v 到集合内所有点的距离和)
vector<char> inBuf; // 一次性读入的全部输入,避免逐字符读入的开销
size_t dayBegin[3]; // 三天按键行在 inBuf 里的起始下标
size_t inPos; // 当前解析位置
// 把整份输入读进内存,并在末尾补一个换行,解析时不必单独处理文件尾。
void readInput() {
char tmp[1 << 20];
size_t got;
while ((got = fread(tmp, 1, sizeof(tmp), stdin)) > 0)
inBuf.insert(inBuf.end(), tmp, tmp + got);
inBuf.push_back('\n');
}
// 定位三行输入在缓冲里的起点:一天恰好一行,空行也是一天(该天只有空串)。
// 读入时已在末尾补了换行,所以最后一行的行尾也一定能找到。
void splitLines() {
size_t p = 0;
for (int d = 0; d < 3; ++d) {
dayBegin[d] = p;
while (p < inBuf.size() && inBuf[p] != '\n')
++p;
++p; // 跳过行尾换行,下一行的起点
}
}
// 动态化静态开点:新建一个结点并返回编号。
int newNode(int par, int c) {
int id = nodeCnt++;
trie[id].parent = par;
trie[id].depth = (par == -1 ? 0 : trie[par].depth + 1);
trie[id].firstChild = -1;
trie[id].nextSibling = -1;
trie[id].subSize = 1;
trie[id].ch = c;
trie[id].distSum = 0;
return id;
}
// 乘法散列:把键摊到 2^22 个桶上,装载因子低,线性探测足够快。
unsigned hashPos(unsigned key) {
return (key * 2654435761u) >> (32 - HASH_BITS);
}
// 结点 u 沿字符 c 向下走一步:没有对应孩子就现场新建一个。
int walkChild(int u, int c) {
unsigned key = u * 256 + c;
unsigned pos = hashPos(key);
while (hashKey[pos] != 0xFFFFFFFFu && hashKey[pos] != key)
pos = (pos + 1) & HASH_MASK;
if (hashKey[pos] == key)
return hashVal[pos];
int id = newNode(u, c);
trie[id].nextSibling = trie[u].firstChild; // 头插进父结点的孩子链表
trie[u].firstChild = id;
hashKey[pos] = key;
hashVal[pos] = id;
return id;
}
// 建好一天的 Trie 后统计这一天的三个量。
// 关键性质:结点编号就是拓扑序(父结点编号一定小于子结点编号),
// 所以倒着扫一遍能累加子树大小,正着扫一遍能由父结点推出子结点的距离和。
void calcDay(int d) {
for (int v = nodeCnt - 1; v >= 1; --v)
trie[trie[v].parent].subSize += trie[v].subSize; // 孩子编号更大,此时子树大小已完整
dayN[d] = nodeCnt;
dayW[d] = 0;
for (int v = 1; v < nodeCnt; ++v) {
ll s = trie[v].subSize; // 边 (parent,v) 一侧有 s 个点,另一侧有 n-s 个点
dayW[d] += s * (dayN[d] - s);
}
ll d0 = 0; // 根(空串)到所有结点的距离和 = 所有结点的深度和
for (int v = 0; v < nodeCnt; ++v)
d0 += trie[v].depth;
trie[0].distSum = d0;
for (int v = 1; v < nodeCnt; ++v) { // 换根:从父结点走到子结点,子树内的点都近 1,其余点都远 1
int p = trie[v].parent;
trie[v].distSum = trie[p].distSum + dayN[d] - 2 * trie[v].subSize;
}
dayDmin[d] = trie[0].distSum;
dayDmax[d] = trie[0].distSum;
for (int v = 1; v < nodeCnt; ++v) {
dayDmin[d] = min(dayDmin[d], trie[v].distSum);
dayDmax[d] = max(dayDmax[d], trie[v].distSum);
}
}
// 读入第 d 天的按键序列并建 Trie(退格 8 = 回父结点),然后统计该天。
void buildDay(int d) {
memset(hashKey, 0xFF, sizeof(hashKey)); // 清空孩子哈希表
nodeCnt = 0;
newNode(-1, 0); // 根 = 空串
inPos = dayBegin[d];
int cur = 0;
while (inPos < inBuf.size() && inBuf[inPos] != '\n') {
char c = inBuf[inPos];
if (c == ' ' || c == '\r' || c == '\t') {
++inPos;
continue;
}
int val = 0;
while (inPos < inBuf.size() && inBuf[inPos] >= '0' && inBuf[inPos] <= '9') {
val = val * 10 + (inBuf[inPos] - '0');
++inPos;
}
if (val == 8) { // 退格:光标回退,串变成父结点代表的串
if (cur != 0)
cur = trie[cur].parent;
} else {
cur = walkChild(cur, val);
}
}
calcDay(d);
}
// 第 3 天最大值里唯一需要配对优化的部分:
// max over b0,b1 in B of [ nA*D[b0] + nC*D[b1] + L*d(b0,b1) ],L = nA*nC。
// 用 d(b0,b1) = depth(b0) + depth(b1) - 2*depth(lca) 拆开,就变成
// max over b0,b1 of [ f[b0] + g[b1] - 2*L*depth(lca(b0,b1)) ],
// 再按 lca 分类:对每个结点 v 枚举"lca 恰好是 v"的配对(两端都是 v / 一端是 v 另一端在某个孩子子树 /
// 两端在两个不同的孩子子树),倒序编号保证孩子先算好。
ll maxPairInB(ll coefA, ll coefC) {
ll L = coefA * coefC;
ll best = NEG_INF;
for (int v = nodeCnt - 1; v >= 0; --v) {
ll f = coefA * trie[v].distSum + L * trie[v].depth; // 取 b0 = v 时的权值
ll g = coefC * trie[v].distSum + L * trie[v].depth; // 取 b1 = v 时的权值
ll cur = f + g; // b0 = b1 = v
ll sub0 = f, sub1 = g; // 子树内 max f / max g
ll other0 = NEG_INF, other1 = NEG_INF; // 已处理过的孩子子树里 max f / max g
for (int c = trie[v].firstChild; c != -1; c = trie[c].nextSibling) {
cur = max(cur, f + bestB1[c]); // 一端是 v,另一端在子树 c
cur = max(cur, bestB0[c] + g);
if (other0 != NEG_INF)
cur = max(cur, other0 + bestB1[c]); // 两端分别在两个不同的孩子子树
if (other1 != NEG_INF)
cur = max(cur, other1 + bestB0[c]);
other0 = max(other0, bestB0[c]);
other1 = max(other1, bestB1[c]);
sub0 = max(sub0, bestB0[c]);
sub1 = max(sub1, bestB1[c]);
}
bestB0[v] = sub0;
bestB1[v] = sub1;
cur -= 2 * L * trie[v].depth; // lca 恰好是 v,扣掉多算的两段 depth
best = max(best, cur);
}
return best;
}
int main() {
readInput();
splitLines();
buildDay(0);
buildDay(1);
buildDay(2);
ll nA = dayN[0], nB = dayN[1], nC = dayN[2];
// 第 1 天:集合 A 内所有字符串对的距离之和。
ll day1 = dayW[0];
// 第 2 天:把 A、B 并成一个整体,A0、B0 固定后所有对的距离之和
// = W(A) + W(B) + [A×B 的对:nA*nB + nB*D_A[A0] + nA*D_B[B0]]。
ll day2min = dayW[0] + dayW[1] + nA * nB + nB * dayDmin[0] + nA * dayDmin[1];
ll day2max = dayW[0] + dayW[1] + nA * nB + nB * dayDmax[0] + nA * dayDmax[1];
// 第 3 天:A、B、C 三个集合并成一个整体,A0、B0、B1、C0 固定后所有对的距离之和
// = W(A)+W(B)+W(C) + [A×B 的对] + [B×C 的对] + [A×C 的对],
// 其中 A×C 的距离是 d(P,A0)+1+d(B0,B1)+1+d(C0,Q),展开后系数为:
// base 部分 (nA*nB + nB*nC + 2*nA*nC) 固定,
// A0 的系数是 nB+nC,C0 的系数是 nA+nB,B0/B1 的系数分别是 nA/nC 且带 d(B0,B1) 一项。
ll base = dayW[0] + dayW[1] + dayW[2] + nA * nB + nB * nC + 2 * nA * nC;
ll day3min = base + (nB + nC) * dayDmin[0] + (nA + nB) * dayDmin[2] + (nA + nC) * dayDmin[1];
// 最小值取 B0 = B1 同为 D_B 最小的点即可(d ≥ 0);
// 最大值要在 B 上重新建树做配对 DP,所以重读一次第 2 天的按键。
buildDay(1);
ll maxPair = maxPairInB(nA, nC);
ll day3max = base + (nB + nC) * dayDmax[0] + (nA + nB) * dayDmax[2] + maxPair;
cout << day1 << " " << day1 << "\n";
cout << day2min << " " << day2max << "\n";
cout << day3min << " " << day3max << "\n";
return 0;
}复杂度
- 时间:每个按键摊到
,一天的处理是 。 生成器给的最坏点是三天的 都是 ,按键数各为 ,总操作量约 ,实测 C++ 在限时 1000 ms 内轻松通过。第 3 天的配对 DP 只对 做一次, 。 - 空间:单天 Trie 的结点数上界
,结点用 struct 数组存,配 的开放寻址哈希表(装载因子 ),再加两个 long long的 DP 数组, 峰值约 80 MB,限时内存 256 MB。 - 与 C++ 解法的关系:
main.py用同一套公式和同一套 Trie,只是把"孩子哈希表" 换成 Python 的dict(键同样是u * 256 + c),把换根 DP 与配对 DP 写成倒序扫编号的for循环。Python 侧的主要风险是那一点会 TLE / MLE( dict与三个 长度为的 list 开销都在数百 MB 量级),算法本身与 C++ 同阶。
总结
- 把操作序列翻译成树:光标在串尾 + 退格回退,等价于在 Trie 上走一条路径, "出现过的所有串"就是访问过的结点集合。这一步之后,字符串的编辑距离问题 就完全变成了树上距离问题。
- 前缀封闭是关键结构:
是 Trie 的结点集而非任意字符串集合, 所以 可以直接当结点数用,子树大小也有明确含义。 - 跨集合的那
个单位可摊分: 拆开后, 只有三个"距离和" 参与优化,其余都是与选择无关的固定项, 于是最小/最大只需在 / 上取值。 才带来真正的难度:最大值里出现 , 用 拆项后变成"在每个结点上合并两棵不同子树的最值", 这是典型的树形 DP 合并套路。 - 编号即拓扑序:按创建顺序给 Trie 结点编号,父结点编号恒小于子结点, 于是子树大小与换根 DP 都退化成一次数组扫描,省掉显式 DFS 和递归栈。