ACM/ICPC 北京站网络赛 B Tomb Raider：用二进制枚举解字符串字典序问题

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 枚举到 (1L)-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 abcdouble 之后变成 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 关键参数与变量说明变量/参数含义取值范围n字符环个数0 n ≤ 10len[i]第 i 个环的原始长度≤ 8s[i]第 i 个环 double 后的字符串长度 ≤ 16u子集枚举上界 1len[0]≤ 256len_ans当前最优答案长度-1 表示未找到ans当前最优答案串长度 ≤ 83.3 编译与运行g -O2 -stdc11 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 03.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 重置为 -1ans 不用清空因为 len_ans 为 -1 时第一次找到候选会直接覆盖。s 数组也不用清空因为每次都会重新读入并覆盖前 n 行。5. 本篇常见错排查从报错到定位这道题虽然思路清晰但实际写的时候有几个坑特别容易踩。下面按常见报错和现象逐个排查。5.1 输出 0 但预期有答案最常见的原因是环展开没做对。如果你忘了 strcat(s[i], tmp)那么 judge 函数里 s[k][fi] 在 fi 超过原串长度时会读到未初始化内存匹配结果随机。检查方法在读入后打印 s[i]确认长度是原来的两倍。另一个原因是 judge 里的循环边界写错。正确写法是外层 f 从 0 到 len[k]-1内层 i 从 0 到 len[k]-1访问 s[k][fi]。如果内层写成 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 开始但上界写成 1len[0]-1会漏掉全选的情况。正确上界是 1len[0]即 mask (1len[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 数组越界导致 REs 数组第二维开的是 805double 后最长 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 版本是否支持 -stdc11检查 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 配置说明照着填就能用。