企业官网建设流程全解析

1. 从 Tomb Raider 这道题说起：字符串环上的公共子序列怎么找

如果你正在准备 ACM/ICPC 区域赛，或者刚打完北京站网络赛想复盘 B 题，那这道 Tomb Raider 大概率让你卡了一会儿。题目本身不复杂：给 n 个字符环，每个环上刻着一串小写字母，环可以任意选起点，要求找出所有环的公共子序列（LCS），长度优先，长度相同时取字典序最小的那个，找不到就输出 0。

我第一次读题的时候，脑子里第一反应是「两两求 LCS 再合并」，结果样例二直接把我打脸。样例二里五个环，正确答案是 acd，但如果你先拿前两个环求最长公共子序列，可能得到的是 ac 或者 ad，再往后配就丢了更优解。原因很简单：两两 LCS 可能有多个等长解，你随便选一个，后面就没法回退了。这道题的正确姿势是——只枚举第一个环的所有子序列，然后拿每个子序列去其他环里验证是否存在。因为 n ≤ 10，每个串长度 ≤ 8，第一个环最多 8 个字符，子序列总数 2^8 = 256，再乘上起点 8 种，总共也就 2048 种候选，完全扛得住。

这里的关键词是「二进制枚举」和「字典序」。二进制枚举负责把「选哪些位置的字符」这件事变成 0/1 位掩码，字典序比较则用 strcmp 直接搞定。整道题的核心就两件事：怎么把环展开成线性串，怎么用位运算枚举子序列。下面我会把这两块拆开讲，给出可以直接复制去交题的模板，再带你跑一遍样例验证。

这道题适合谁看？如果你刚学完子集枚举、对位运算还不太熟，或者每次遇到「环 + 子序列 + 字典序」的组合就发怵，那这篇就是给你写的。我会尽量把每一步为什么这么写讲清楚，而不是只丢一份 AC 代码让你自己悟。

2. 前置准备：二进制枚举与字符环展开的核心思路

在动手写代码之前，先把两个基础概念捋顺，不然后面看代码会晕。

2.1 二进制枚举子序列到底在枚举什么

假设第一个环展开后得到一个长度为 L 的字符串 t，我们想枚举它的所有子序列。所谓子序列，就是从 t 里挑若干个字符，保持它们在原串中的相对顺序。比如 t = "abc"，子序列有 ""、"a"、"b"、"c"、"ab"、"ac"、"bc"、"abc"。

用二进制怎么表示？给每个位置分配一个 bit，第 i 位为 1 表示「选第 i 个字符」，为 0 表示「不选」。那么从 1 枚举到 (1<<L)-1，每个整数就对应一种选择方案。代码里通常这么写：

for (int mask = 1; mask < (1 << L); mask++) { string sub; for (int i = 0; i < L; i++) { if (mask & (1 << i)) sub += t[i]; } // sub 就是一个子序列 }

注意这里从 1 开始枚举，因为空串没有意义（题目要求非空公共子序列，空串不算）。如果你从 0 开始，会多出一个空串，虽然不影响最终答案，但会浪费一次判断。

2.2 字符环怎么变成线性串

环的特点是「首尾相接」，任意一个字符都可以当起点。处理环最常用的技巧是「double 字符串」：把原串复制一份接在后面。比如 s = "abc"，double 之后变成 "abcabc"。这样从任意位置 f 开始，取长度为原串长度的连续子串，就等价于「以 f 为起点绕环一圈」得到的线性串。

char s[15][100]; int len[15]; // 读入后 strcpy(tmp, s[i]); strcat(s[i], tmp); // s[i] 变成两倍长

这样 s[i] 的前 len[i] 个字符是原串，后面 len[i] 个字符是复制品。枚举起点 f 从 0 到 len[i]-1，取 s[i]+f 开始的 len[i] 个字符，就得到了所有可能的「展开方式」。

2.3 为什么只枚举第一个环就够了

这是这道题最容易被忽略的优化点。公共子序列一定是第一个环的子序列，所以只要把第一个环的所有子序列枚举出来，逐个去其他环里验证「这个子序列是否存在」，就能覆盖所有可能的答案。不需要枚举所有环的子序列，那样复杂度会爆炸。

验证一个子序列 sub 是否存在于第 k 个环里，做法是：对第 k 个环的每个起点 f，从 f 开始逐位匹配 sub 的字符，如果 sub 的所有字符都能按顺序找到，就说明存在。这个判断函数就是代码里的 judge。

2.4 字典序比较为什么直接用 strcmp

题目要求「长度优先，长度相同取字典序最小」。C 语言的 strcmp 正好满足字典序比较：strcmp(a, b) > 0 表示 a 的字典序大于 b。所以当两个候选子序列长度相同时，直接 if (strcmp(ans, css) > 0) 就完成了「取更小」的操作。不需要自己写比较函数，省事又不容易出错。

把上面四点串起来，整道题的流程就是：读入 n 个串 → 每个串 double 成环 → 枚举第一个环的每个起点 → 对每个起点用二进制枚举子序列 → 对每个子序列验证其他环 → 维护最优答案 → 输出。

3. 可复制配置：完整 AC 代码与关键参数说明

这一节给出可以直接拿去提交的完整代码，路径和变量名都保持和原题解一致，方便你对照理解。代码用 C++ 写，编译命令和运行方式也会给出来。

3.1 完整代码

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int len[15], len_ans; char s[100 + 5][80 + 5], ans[80 + 5]; // 判断子串 ss 是否存在于第 k 个字符环中 bool judge(char* ss, int k) { for (int f = 0; f < len[k]; f++) { // 枚举环的起点 int pss = 0; for (int i = 0; i < len[k]; i++) { // 从起点开始逐位匹配 if (s[k][f + i] == ss[pss]) { pss++; if (ss[pss] == '\0') return true; // 全部匹配成功 } } } return false; } void check(int n) { char tss[20 + 5], css[20 + 5]; int u = 1 << len[0]; // 子集枚举上界 for (int f = 0; f < len[0]; f++) { // 枚举第一个环的起点 strncpy(tss, s[0] + f, len[0]); // 取出以 f 为起点的展开串 tss[len[0]] = '\0'; for (int k = 1; k < u; k++) { // 二进制枚举子序列 int p = 0; for (int i = 0; i < len[0]; i++) { if (!(k & (1 << i))) continue; css[p] = tss[i]; p++; } css[p] = '\0'; bool ok = true; for (int i = 1; i < n; i++) { // 验证其他环 if (!judge(css, i)) { ok = false; break; } } if (ok) { if (len_ans == -1) { strcpy(ans, css); len_ans = strlen(ans); } else { int lencss = strlen(css); if (lencss > len_ans) { strcpy(ans, css); len_ans = lencss; } else if (len_ans == lencss) { if (strcmp(ans, css) > 0) { strcpy(ans, css); } } } } } } } int main() { int N; char tmp[20 + 5]; while (~scanf("%d", &N)) { for (int i = 0; i < N; i++) { scanf("%s", s[i]); len[i] = strlen(s[i]); strcpy(tmp, s[i]); strcat(s[i], tmp); // double 成环 } len_ans = -1; check(N); if (len_ans == -1) puts("0"); else printf("%s\n", ans); } return 0; }

3.2 关键参数与变量说明

3.3 编译与运行

g++ -O2 -std=c++11 tomb_raider.cpp -o tomb_raider ./tomb_raider < input.txt

其中 input.txt 放样例输入：

2 abcdefg zaxcdkgb 5 abcdef kedajceu adbac abcdef abcdafc 2 abc def

预期输出：

acdg acd 0

3.4 复杂度估算

第一个环长度最多 8，起点 8 种，子集 256 种，所以候选子序列最多 8 × 256 = 2048 个。每个候选要验证 n-1 ≤ 9 个环，每个环验证时枚举起点 8 种、逐位匹配 8 次，单次验证约 64 次操作。总操作量约 2048 × 9 × 64 ≈ 118 万次，远低于 1000ms 的限制。内存方面，s 数组 100×85 字节，完全够用。

4. 验证请求与成功结果：跑一遍样例看输出

代码写完了，最关键的一步是验证。很多人代码看着对，一跑样例就挂，问题往往出在环展开或者字典序比较上。这一节带你逐个样例走一遍，确认输出和题目一致。

4.1 样例一：两个环求最长公共子序列

输入：

2 abcdefg zaxcdkgb

第一个环 "abcdefg" double 后是 "abcdefgabcdefg"。枚举起点和子序列后，候选里会出现 "acdg" 这个串。验证它在第二个环 "zaxcdkgb" 里是否存在：第二个环 double 后是 "zaxcdkgbzaxcdkgb"，从起点 'z' 开始匹配，z→a→x→c→d→k→g→b，能依次找到 a、c、d、g，所以 "acdg" 存在。其他候选要么更短，要么字典序更大，最终答案就是 "acdg"。

4.2 样例二：五个环的公共子序列

输入：

5 abcdef kedajceu adbac abcdef abcdafc

这个样例的答案是 "acd"。注意第一个环和第四个环都是 "abcdef"，它们 double 后一样。候选 "acd" 需要在这五个环里都存在。比如第三个环 "adbac" double 后是 "adbacadbac"，从 'a' 开始能匹配 a→d→b→a→c，其中 a、c、d 按顺序能找到，所以 "acd" 存在。而 "acdf" 这种更长的候选，在第三个环里找不到 f，所以被淘汰。最终 "acd" 胜出。

4.3 样例三：无公共子序列

输入：

2 abc def

两个环的字符集完全不重叠，任何非空子序列都无法同时存在于两个环里。len_ans 保持 -1，输出 0。这里要注意，题目说的是「没有 LCS 就输出 0」，不是输出空行，所以 puts("0") 是对的。

4.4 用调试输出确认中间结果

如果你跑出来的结果和预期不一致，可以在 check 函数里加一行调试输出，看看候选子序列都有哪些：

if (ok) { printf("candidate: %s, len=%d\n", css, (int)strlen(css)); // ... 原有逻辑 }

这样能看到哪些候选通过了验证，再对照预期答案，就能快速定位是枚举漏了还是验证错了。调试完记得把这行删掉，不然会输出多余内容导致判题失败。

4.5 多组测试用例的处理

题目说「不超过 10 个测试用例」，用 while (~scanf("%d", &N)) 循环读入即可。每次循环开始前要把 len_ans 重置为 -1，ans 不用清空，因为 len_ans 为 -1 时第一次找到候选会直接覆盖。s 数组也不用清空，因为每次都会重新读入并覆盖前 n 行。

5. 本篇常见错排查：从报错到定位

这道题虽然思路清晰，但实际写的时候有几个坑特别容易踩。下面按常见报错和现象逐个排查。

5.1 输出 0 但预期有答案

最常见的原因是环展开没做对。如果你忘了 strcat(s[i], tmp)，那么 judge 函数里 s[k][f+i] 在 f+i 超过原串长度时会读到未初始化内存，匹配结果随机。检查方法：在读入后打印 s[i]，确认长度是原来的两倍。

另一个原因是 judge 里的循环边界写错。正确写法是外层 f 从 0 到 len[k]-1，内层 i 从 0 到 len[k]-1，访问 s[k][f+i]。如果内层写成 i < len[k]-f，就会漏掉环末尾的部分。

5.2 答案长度对但字典序不对

这通常是字典序比较写反了。strcmp(ans, css) > 0 表示 ans 比 css 大，此时应该把 ans 替换成 css。如果你写成 < 0，就会保留字典序更大的那个。记住题目要的是「字典序最小」。

还有一种情况是长度相同时没有比较，直接跳过了。检查你的 else if 分支，确认 len_ans == lencss 时执行了 strcmp 比较。

5.3 子序列枚举漏解

如果你从 mask = 0 开始枚举，会多出一个空串，虽然不影响答案，但会浪费判断。如果你从 mask = 1 开始但上界写成 1<<len[0]-1，会漏掉全选的情况。正确上界是 1<<len[0]，即 mask < (1<<len[0])。

另外，strncpy(tss, s[0]+f, len[0]) 之后一定要手动加 '\0'，因为 strncpy 不保证结尾有终止符。漏了这步会导致 tss 后面跟着垃圾字符，枚举出的子序列长度不对。

5.4 多组数据答案串残留

如果第一组数据找到了答案，第二组数据没找到，但 ans 没清空，len_ans 重置为 -1 后，第二次找到候选时会覆盖 ans，所以一般不会出问题。但如果你在 check 里用了全局的 css 且没重置，可能会有残留。保险做法是每次 check 开始前把 ans 和 css 都清零。

5.5 数组越界导致 RE

s 数组第二维开的是 80+5，double 后最长 16，够用。但如果你把 len 数组开小了，或者 n 读入超过 10，就会越界。题目保证 n ≤ 10，但保险起见可以把数组开大一点，比如 s[15][100]。

5.6 时间超限

正常情况下不会超时，但如果你在 judge 里用了 string 的 find 或者 substr，常数会大很多。建议用 char 数组和下标访问，效率最高。另外，把 strlen 的结果存到变量里，不要在循环里反复调用。

5.7 对照真实报错定位

如果你在本地跑的时候遇到local proxy failed或者reading choices这类报错，那通常不是这道题本身的问题，而是你的编译环境或者输入重定向配置有问题。检查 g++ 版本是否支持 -std=c++11，检查 input.txt 路径是否正确。如果是 OAuth 相关的报错，那更和这道题无关，可能是你用的在线判题平台登录态失效，重新登录即可。

6. 把这道题的方法迁移到同类字符串枚举题

Tomb Raider 这道题的价值不只是一道 AC，它背后的「二进制枚举 + 环展开 + 字典序维护」是一类题的通解。你以后遇到「多个字符串找公共子序列」「环上找最优子串」「子集枚举后验证」这些场景，都可以套这个框架。

具体来说，第一步永远是确定枚举对象。这道题枚举的是第一个环的子序列，因为公共子序列必然是第一个环的子序列。如果题目改成「找所有环的最长公共子串」，那枚举对象就变成第一个环的所有子串，验证方式也变成直接匹配而非子序列匹配。第二步是处理环，double 字符串是万能解法，不管环上做什么操作，先 double 再说。第三步是维护最优解，长度优先还是字典序优先，取决于题目要求，用 strcmp 或者自定义比较函数都行。

如果你想继续练这类题，可以试试把 n 的范围改大、串长改长，看看你的代码还能不能扛住。也可以把「子序列」改成「子串」，把「字典序最小」改成「字典序最大」，自己改条件再跑一遍。这种主动变形的练习，比单纯刷题效果好得多。

如果你在准备 ICPC 区域赛，需要长期用 AI 辅助调试代码、生成测试用例，可以看看 TaoToken 的 Coding Plan，它支持 Claude Code 等编码工具的长上下文调用，适合这种需要反复迭代的算法题场景。想先验证模型对这道题的理解，可以直接在模型对话里贴代码让它帮你找 bug。接入文档里有完整的 Base URL、API Key 和 Model ID 配置说明，照着填就能用。