把串看成 trie 状态,纠缠即 Myhill-Nerode 右语言等价,用并查集合并状态并沿 10 条出边做同余闭包,查询时每步跳到代表元。
OJ: roj
题目 ID: 1703
难度:提高+/省选-
标签:字符串trie并查集自动机python
创建: 2026-10-07 17:19
更新: 2026-10-07 17:19
形式化题目
维护一个只增不减的数字串(字符集
1 s:把串加入 ; 2 s:询问与否,输出 / ; 3 a b:令与 互相纠缠。
"纠缠"是一个双向的后缀等价约束:对任意
两条其实互为同一命题的两半,合起来就是:对任意后缀
因此一次 3 操作会把满足该式的一切串立即纳入 1 操作同样可能连带引入无穷多个串。
约束:1 与 3 操作次数之和),
2 操作询问串的总长度),1 / 3 操作中数字串的长度上限)。
正解
思路
关键一步:把"集合"换成"状态"。 先看一个纯暴力:维护串的集合 1 直接插入,2 直接查找。它对 3 无能为力——一次纠缠要枚举并插入无穷多个串。
突破口在于看清纠缠的定义式:
于是"3 a b 这条操作,
用这个视角看就是一句朴素得多的指令:
把
与 归入同一个等价类。
但等价类不能随便并——要对出边取闭包。 设状态
所以
数据结构落地。 把每个串看成 trie 上的一个节点(根 = 空串,节点 1 操作 = 把 2 操作 =
沿 3 操作 = 合并两个末节点所在的类。
等价类用并查集维护,fa[u] 指向同类里的另一个节点。合并时把
出边表始终挂在代表元上,并且两类合并时把被合并者已有的出边"接"到代表元上—— 这样后面到达的串,哪怕前缀路径是"晚"才走出来的,也会自动共享整个类已积累的出边。
查询时必须每步跳代表元。 走 find_root:因为 3 操作里被并进别的类,直接读 ch[cur][c] 会读到陈旧的代表元。
这正是本题最容易写错的地方——等价类是动态的,trie 的父子关系不能静态看待。
"集合只增不减"的红利。 fin 只置真、不置假;等价类只合并、不拆分。
所以每一个被加入或被纠缠"传染"到的串,此后永远答
用题面样例追踪一遍:3 12 13 让状态 12 与 13 同类,于是在它们的出边闭包里
12 走 4 得到的 124 与 13 走 4 得到的 134 也同类;此后 1 124 把 124
的类打上标记,2 134 自然答 134 被连带进集合,
这就是纠缠"传染"的最小实例。
代码
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:19
# update_at: 2026-10-07 17:19
import sys
ROOT = 1 # 根状态(空串)的编号;状态 0 是"这条出边不存在"的哨兵
ch: list[list[int]] = [[0] * 10, [0] * 10] # ch[u][c]:状态 u 走字符 c 到哪个状态
fa: list[int] = [0, 1] # 并查集父指针,代表元满足 fa[u] == u
fin: list[bool] = [False, False] # 该状态所在等价类是否已进信息集
def find_root(x: int) -> int:
"""并查集找代表元,顺路把路径上的点都挂到根上。"""
r = x
while fa[r] != r:
r = fa[r]
while fa[x] != r:
fa[x], x = r, fa[x]
return r
def ensure_state(s: bytes) -> int:
"""沿串 s 走自动机(缺的边现场开点),返回末状态所在等价类的代表元。"""
cur = ROOT
for d in s:
c = d - 48
if ch[cur][c] == 0:
# 开点:ch / fa / fin 三个数组同步长一位,新状态自成一类
ch.append([0] * 10)
fa.append(len(fa))
fin.append(False)
ch[cur][c] = len(fa) - 1
cur = find_root(ch[cur][c])
return cur
def find_state(s: bytes) -> int:
"""询问串 s 落在哪个等价类;中途缺边说明 s 不在信息集,返回哨兵 0。"""
cur = ROOT
for d in s:
c = d - 48
nxt = ch[cur][c]
if nxt == 0:
return 0
cur = find_root(nxt)
return cur
def merge_state(p: int, q: int) -> None:
"""把 p、q 所在等价类并成一类,并对 10 条出边做同余闭包。
纠缠要求两个状态右语言相同,所以同类状态对每个字符的后继也必须同类;
后继合并又会引出新的状态对,用显式栈把闭包做到底(不递归,免爆栈)。
"""
stack = [(p, q)]
while stack:
x, y = stack.pop()
a, b = find_root(x), find_root(y)
if a == b: # 已经在同一类里
continue
fa[b] = a # b 并入 a 的类
fin[a] = fin[a] or fin[b] # 标记只置真不置假
for c in range(10):
u, v = ch[a][c], ch[b][c]
if v == 0: # b 这条出边是空的
continue
if u == 0:
ch[a][c] = v # a 缺的边直接接上 b 的
continue
need_merge = find_root(u) != find_root(v) # 两条后继还不在同一类
if need_merge:
stack.append((u, v))
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
m = int(next(data))
out: list[str] = []
added = False # 是否出现过操作 1;一次都没加过串时信息集恒空
for _ in range(m):
op = next(data)
if op == b'1':
fin[ensure_state(next(data))] = True
added = True
elif op == b'2':
s = next(data)
v = find_state(s) if added else 0 # 空集直接答 0,省一趟自动机
out.append('1' if v and fin[v] else '0')
else:
merge_state(ensure_state(next(data)), ensure_state(next(data)))
# 答案先攒进列表再一次写出,避免 10^5 次 print 的开销;末尾补换行收尾
if out:
sys.stdout.write('\n'.join(out) + '\n')
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:19
* update_at: 2026-10-07 17:19
*/
// 一本通 1703《量子纠缠》:trie 上的状态等价类合并(并查集 + 出边同余闭包)。
//
// 建模:把每个数字串看作 trie 上的一个状态,"串在信息集中"记在该状态上的 fin 标记。
// "纠缠 a b" 要求对任意后缀 X 都有 (a+X 在信息集) <=> (b+X 在信息集),
// 这正是 Myhill-Nerode 意义下"状态 a 与状态 b 右语言相同",两个状态必须并成一类。
// 合并两个等价类时,相同字符的出边也要成对合并,否则等价类不自洽;
// 而这些后继的等价类又可能被进一步合并,所以要用显式栈把闭包做到底。
// 出边只增不减地记在等价类代表元上,查询时每走一步先转到代表元,
// 于是同一类的所有串共享同一套后继 —— 晚到的 1 操作会自动"传染"整个类。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 状态数上界:操作 1 每条串 <= L 个点,操作 3 贡献两条串,故
// 点数 <= 1 + c*2*L = 1 + 2050*2*50 = 205001,这里取 25 万留余量
const int MAXNODE = 250005;
const int CHAR_SET = 10; // 数字串的字符集 0~9
// 状态:出边表 + 并查集父指针 + 是否在信息集中的标记
struct Node {
int ch[CHAR_SET]; // ch[c] = 走字符 c 到达的状态编号,0 表示没有这条出边
int fa; // 并查集父指针:指向同等价类的另一个状态
bool fin; // 该状态(等价类代表元)是否已经在信息集中
};
Node node[MAXNODE]; // node[u] 就是状态 u,状态 0 是"无出边"哨兵,根状态是 1
int node_cnt = 1; // 已创建的状态个数(根状态编号为 1)
bool has_added; // 是否发生过操作 1:fin 只置真不置假,没加过串时询问一律为 0
// 开一个新状态:出边全空,自己是独立等价类的代表元
int new_node() {
node_cnt++;
node[node_cnt].fa = node_cnt;
node[node_cnt].fin = false;
return node_cnt;
}
// 并查集找根 + 路径压缩,返回状态 x 所在等价类的代表元
int find_root(int x) {
int r = x;
while (node[r].fa != r) r = node[r].fa; // 第一遍:找到根
while (node[x].fa != x) { // 第二遍:把路径上的点直接挂到根
int p = node[x].fa;
node[x].fa = r;
x = p;
}
return r;
}
// 沿串 s 在自动机上走一遍,缺的边现场开点,返回末状态所在等价类的代表元
int ensure_state(const string& s) {
int cur = 1; // 根状态(空串)
ll n = s.size();
for (ll i = 0; i < n; i++) {
int c = s[i] - '0';
if (node[cur].ch[c] == 0) node[cur].ch[c] = new_node();
cur = find_root(node[cur].ch[c]);
}
return cur;
}
// 询问串 s 落在哪个等价类:走不通返回 0,否则返回代表元
int find_state(const string& s) {
int cur = 1;
ll n = s.size();
for (ll i = 0; i < n; i++) {
int c = s[i] - '0';
int nxt = node[cur].ch[c];
if (nxt == 0) return 0; // 前缀就不在 trie 里,串必然不在信息集中
cur = find_root(nxt);
}
return cur;
}
// 合并 p、q 所在的两个等价类,并沿 10 条出边做同余闭包(显式栈代替递归)
void merge_state(int p, int q) {
vector<pair<int, int> > stk; // 待合并的状态对
stk.push_back(make_pair(p, q));
while (!stk.empty()) {
int x = stk.back().first;
int y = stk.back().second;
stk.pop_back();
int a = find_root(x);
int b = find_root(y);
if (a == b) continue; // 已经在同一类里
node[b].fa = a; // b 并入 a 的等价类
node[a].fin = node[a].fin || node[b].fin;
for (int c = 0; c < CHAR_SET; c++) {
int u = node[a].ch[c];
int v = node[b].ch[c];
if (v == 0) continue; // b 这条出边是空的,没有要合并的后继
if (u == 0) {
node[a].ch[c] = v; // a 缺的边直接接上 b 的
} else if (find_root(u) != find_root(v)) {
stk.push_back(make_pair(u, v)); // 两个后继也要同余
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
node[1].fa = 1; // 根状态自己是代表元
ll m;
cin >> m;
string s, a, b;
for (ll i = 1; i <= m; i++) {
int op;
cin >> op;
if (op == 1) {
cin >> s; // 加入信息集的串
node[ensure_state(s)].fin = true;
has_added = true;
} else if (op == 2) {
cin >> s; // 询问串
// 一次 1 操作都没发生时信息集恒空,不必走自动机
int v = has_added ? find_state(s) : 0;
if (v != 0 && node[v].fin) {
cout << 1 << '\n';
} else {
cout << 0 << '\n';
}
} else {
cin >> a >> b; // 互相纠缠的两个串
merge_state(ensure_state(a), ensure_state(b));
}
}
return 0;
}复杂度
- 时空规模由
决定,与询问串长度无关:trie 只在 1/3操作中开点,1贡献条串、 3贡献条串,每条串至多 个新节点,故 (本仓库数据里最多的是 problem7,)。 - 时间:
1/2操作各为; 3操作的闭包代价可以用 "出边被搬运的总次数"来摊还——每条出边一旦被搬进某个代表元并永久留在那里, 且被合并的等价类不会再拆开,故闭包总代价为。 总计 ,其中 。 - 空间:
,即约 个状态格子; C++ 版实测峰值内存 MB(限时 MB)。 - I/O 才是本题的大头:
,输出可达 行。 C++ 版用 ios::sync_with_stdio(false)+'\n'逐行输出; Python 版把答案先收进列表再'\n'.join一次性写出,避免次 print。 - Python 实测:最重的两个点(
problem697946 次询问、problem997949 次询问) 各约s;即便是手工构造的"每个询问都走满 50 步再落空"的 极端输入,CPython 也只用 s, 远低于 ms 限时,本题对 Python 没有可预见的超时风险。 关键在于"按空白切分整块读入 + 一次写出",而不是逐行 input/print。
总结
- 纠缠 = 右语言等价,是本题的题眼。 想通 “
对一切 ” 就是 Myhill–Nerode 等价,无穷多个串的插入就神奇地退化成一次"合并两个状态"。 - 等价类对出边封闭。 合并
必须连 与 一起合并,且要闭包到底; 漏掉闭包会在"纠缠后再加入新串"的用例上错答。 - 查询每步跳代表元。 等价类动态变化,trie 的边不是静态父子指针, 任何"缓存的代表元"都可能过时。
- 加入操作是单向的。
fin只置真不置假,等价类只并不拆, 于是从始至终没有一行撤销代码——这一点直接源自题面"只增不减的集合"。 - 小心
2操作的串可以超出。 询问串长度只受 限制, trie 里走不通的前缀要立刻返回 ,不要为询问串开点,否则节点数会爆。
备注(关于本题素材)
本题素材源目录带数据生成脚本,data/ 是自造数据,content.md 的题面是按网络流传的
一本通《量子纠缠》重建的,出题意图与官方原题可能有偏差,需注意以下几点:
- 题面【提示】里的
中 未作任何解释;生成器按 " 测试点编号"解读,并对每个测试点令 点号 。 - 题面样例的期望输出末两行带多余制表符(
0\t/1\t), 应为排版残留,按逐行比对即可。 - 素材源的
std.cpp已在本机编译并与data/全部 10 个测试点的.out逐一比对, 10/10 逐字节一致,其"并查集 + trie 出边闭包"的建模与本文推导一致, 因此本文的main.cpp沿用同一建模(重写实现,未照抄源码)。