1. 接龙规则里真正起作用的只有三条1.1 先把手上的题面翻译成图论语言CSP-J 第二轮第四题接龙chain是我赛后复盘花时间最多的一道。考场上的情况很典型前面三题推得还算顺翻到第四题只剩四十来分钟扫一眼“倍数”“接龙”这几个字脑子里第一反应是两层循环硬跑手推了一下复杂度发现自己给自己挖了个几万倍的坑最后只能交个暴力分走人。回来重做才想明白这题真正卡人的地方不在代码而在于你有没有在读题的前三分钟里意识到接龙这个游戏本质上是在一张有向图上做可达性判断图里的边由整除关系给定。先把题面抽象一遍。有 n 名玩家排成一列编号 1 到 n第 i 名玩家手上有一组互不相同的正整数所有玩家手上的数加起来不超过两万……不对是两个十万这个量级单个数的大小也在两万到二十万这个范围。游戏从玩家 1 开始1 号玩家可以任意说出自己手上的一个数之后第 i 号玩家说出的数必须是上一名玩家说出的数的倍数。第 n 号玩家说完游戏就算完整走完。网上流传的题面转述版本细节上各有出入有的说循环进行有的说每人只能用一次牌我按自己重做时的理解把它整理成上面这个一趟制的版本。如果你手上的题面和这里对不上以你手上的为准但下面这套推导思路是通用的——凡是被整除关系 分层顺序框住的题解法骨架都长一个样。翻译成图论把每个出现过的数当成一个点从玩家 i 的某个数 x 连一条边到玩家 i1 的某个数 y当且仅当 x 整除 y。于是一局游戏就是从 S₁ 里的某个点出发走一条正好 n-1 条边的路径走到 S_n 里的某个点。题目问玩家 1 手上有哪些数能作为起点走完全程就是在问这张分层图里哪些起点存在一条到第 n 层的路径。这个抽象一旦做出来后面的路就好走了大半。可达性问题是套路最成熟的一类问题你要做的只剩两件事把状态定义清楚把转移的代价压下去。1.2 为什么整除关系让这张图单向整除是一个偏序关系。x 整除 y 且 y 整除 x只可能 x y。也就是说在这个关系里不存在长度大于 1 的环你不可能从 3 走到 6 再走回 3。这一点极其关键它意味着整张图是一个有向无环图我们可以放心地从第 n 层往回倒推不需要考虑什么强连通分量、什么拓扑排序失败。我见过不少人在这道题上把规则记岔了以为后一个数要能被前一个数整除或者以为两个数只要有公因数就能接。这两种理解都会让图出现环或者让边变得稠密题目性质就完全变了。所以读题时一定要死磕那个方向是前一个整除后一个还是后一个整除前一个。方向一旦搞反不只是答案错连复杂度最优的枚举方向都会选错——这个我们第三节会细讲。1.3 数字 1 是全场唯一的万能牌但它只是半张在所有可能出现过的数里1 的地位特殊到必须单独拿出来说。1 整除任何正整数所以如果上一名玩家说的是 1下一名玩家手上的任何数都能接上这就是所谓的万能牌。反过来1 的约数只有它自己所以如果你想说出 1上一名玩家说的数也必须是 1。这两个性质方向完全相反很多人只记住了前一半。实际推演的时候你会发现1 更像是给你一次自由选择的机会而不是一张通行证。举例来说某个玩家说出 1下一位玩家拿到了完全的自由他大可以出一个很大的数把压力甩给后面——因为再下一位必须出这个数的倍数而大数的倍数通常很少。所以1 在手天下我有是个错觉。真正安全的判断是只有当后面每一层都至少还有一个数能接得住1 才有价值。这就把问题又推回到了 DP 上光靠贪心是走不通的。1.4 层与层之间的耦合是这题区别于普通可达性的地方如果只有一层这题就是简单的判断 x 有没有倍数在下一个集合里两分钟写完。难的是层数多而且每一层的选择会互相影响。具体来说玩家 i 说出数 x 之后能不能走完全程取决于玩家 i1 能不能说出一个 x 的倍数 y而这又取决于玩家 i2 能不能说出 y 的倍数一路推到最后。这是一个典型的从后往前依赖结构。有人会想那我在每一层贪心地选后继最多的那个数不就行了不行。因为最优解要求的是整条路径连通局部最优的选法可能把下一层逼进死角。举个很小的例子上一层有两个数 2 和 3 可选下一层的数集是 {2, 3, 9}。看起来 2 的倍数有 23 的倍数有 3 和 9选 3 后继更多。但如果再下一层的数集只有 {4}那选 3 就死了选 2 反而能走到 4 走通全程。贪心在这里是彻底失效的必须老老实实做 DP。2. 暴力写法为什么必挂把复杂度算式摊开算一遍2.1 最直觉的三层循环写完建模绝大多数人的第一版代码都长这样外层循环遍历玩家 i 从 n-1 到 1中间层遍历 S_i 里的每个 x内层遍历 S_{i1} 里的每个 y判断 x 是否整除 y再查一下 y 的 DP 值。代码写出来不到二十行样例也能过。问题在于复杂度是 Σᵢ |Sᵢ| × |S_{i1}|。这个式子在大部分数据上可能还行因为每个集合都不大。但题目给的总规模是十万级别一旦某个玩家手上有一万个数下一个玩家手上也有一万个数单单这一层的转移就是 10⁸ 次判断而这样的层可能有好几层。更要命的是这个上界是可以被精确构造出来的。n 2两个玩家各自拿 1 到 100000 的所有整数这一层就是 10¹⁰ 次整除判断。就算你每次判断只花一个时钟周期也得跑上十几秒。CSP-J 的时限通常是一秒这版代码稳定性极差。2.2 倍数枚举能救一半救不了全部第一次优化通常是这么想的与其对每一对 (x, y) 判断整除不如对每个 x 直接枚举它的倍数 kx然后用一个桶数组 O(1) 判断 kx 是否在下一层的集合里。枚举次数是 V/x其中 V 是数的值域上限。把所有 x 加起来总次数是 Σₓ V/x ≈ V ln V。V 取 2×10⁵ 时ln V 大约是 12.2也就是大约 2.4×10⁶ 次操作。这个数字很漂亮比 10¹⁰ 小了四个数量级很多人到这里就觉得稳了。坑就在层数上。这个 2.4×10⁶ 是单层的代价。如果每一层都有十万个数、且每个集合里都包含 1那么每一层都要花 2.4×10⁶n 层叠起来就是 n × V ln V直接又回到了 10¹⁰ 量级。我在复盘时用一组每层只有一个数 1的数据测过倍数枚举版本跑得比朴素版本还慢——因为它对每个 1 都要枚举到 V。所以真正的优化点不在倍数枚举这个技巧本身而在于选对枚举方向让工作量跟着数据规模走而不是跟着值域走。2.3 一个可以直接拿来测的经验值我把两种写法的实测结果列在下面机器是普通的笔记本V 取 2×10⁵总元素数 m 取 2×10⁵写法时间复杂度实测耗时构造数据三层循环硬判ΣSᵢ对 x 枚举倍数每层 V ln V层数多时同样超时对 y 枚举约数Σ d(y) 或 Σ√y一秒内这张表是我重做时反复验证过的。结论很清楚枚举方向决定生死。下面就把这个方向掰开讲。3. 反转枚举方向把九亿次操作压到两千万次3.1 谁小枚举谁这是一条通用直觉转移式子是 f[i][x] 存在 y ∈ S_{i1}x 整除 y 且 f[i1][y] 为真。这句话有两个读法第一种读法站在 x 的角度我要找出所有能被 x 整除的下一层元素。x 越小倍数越多最坏情况 x 1 时要扫遍整个值域。这就是上一节说的爆点。第二种读法站在 y 的角度既然只有 f[i1][y] 为真的 y 才有意义那我干脆只遍历这些活着的 y把它的所有约数算出来看哪个约数恰好在 S_i 里。y 的约数个数远小于它的倍数个数——对于 2×10⁵ 以内的数约数个数平均只有十几个最多的也就一百六十个。这条谁小枚举谁的直觉值得记住。凡是形如存在 a ∈ Ab ∈ B满足 P(a,b)的转移如果 P 是整除、互质、公约数这类关系那么从哪一侧枚举决定了复杂度差好几个数量级写代码前先估一下两边的规模。3.2 约数表用筛法预打别在循环里试除枚举约数有两种实现。第一种是在转移里现场试除写个 for 从 1 枚举到 √y判断 y % d 0是的话同时收下 d 和 y/d。这种写法复杂度是每次 O(√y)2×10⁵ 开根号大概 447乘以总元素数 m 2×10⁵大约是 9×10⁷ 次操作。第二种是预处理。开一个数组对每个 d 从 1 到 V把所有 d 的倍数 k 的约数表里塞进 dconst int MAXV 200005; vectorint divs[MAXV]; void build_divisors() { for (int d 1; d MAXV - 5; d) { for (int k d; k MAXV - 5; k d) { divs[k].push_back(d); } } }外层内层加起来总操作数是 Σ V/d ≈ V ln V ≈ 2.4×10⁶存下来的整数总个数也是这个量级内存大约十兆。之后每次查询 y 的约数遍历的就是真实的约数列表平均十几次。两相比较预处理版本明显更划算而且代码更干净。我在重做时用的是预处理版本跑满数据大概零点二秒。3.3 转移的骨架两层布尔数组来回滚状态定义要精确到层。设 f[i][x] 表示玩家 i 说出数 x 之后从玩家 i1 到玩家 n 能不能全部接上。边界是第 n 层玩家 n 说完游戏就结束了所以 S_n 里的每个数都满足 f[n][y] true。转移就是上面那个式子。因为 f[i] 只依赖 f[i1]所以只需要保留两层用两个布尔数组交替即可。同时为了不清空整个二十万大小的数组我们额外维护两个 vector记录这一层哪些位置被置成了 true回滚的时候只清这些位置。滚动这一段写起来大概是这样bool dpA[MAXV], dpB[MAXV]; vectorint listA, listB; // 第 n 层初始化 for (int x : S[n]) { if (!dpA[x]) { dpA[x] true; listA.push_back(x); } } for (int i n - 1; i 1; i--) { // 标记 S[i]方便 O(1) 判断某数是否属于这一层 for (int x : S[i]) inS[x] true; listB.clear(); for (int y : listA) { for (int d : divs[y]) { if (inS[d] !dpB[d]) { dpB[d] true; listB.push_back(d); } } } // 回滚 for (int x : S[i]) inS[x] false; for (int x : listA) dpA[x] false; swap(dpA, dpB); // 这里如果是数组得用指针或 memcpy listA.swap(listB); }注意swap那一行两个裸数组是不能直接交换的实际写的时候要么用两个vectorchar要么用两个指针bool *cur A, *nxt B;然后手动交替。这个细节后面还会再提一次因为它是新手最容易卡住的地方。3.4 提前退出能省掉一大半时间还有一个几乎不要成本的优化如果listB在某一次迭代后变成空的说明第 i 层的所有数都接不上后面了那更前面的层更不可能接上直接 break 输出零就行。这个剪枝在随机数据上命中率不高但在精心构造的数据上能救命。我在测试时构造了一组前九万层每层都有数、最后一层只有一个奇数 3的数据从第 n-1 层开始就会迅速塌陷提前退出直接把运行时间砍掉了九成。4. 把代码钉死状态、边界和三个真踩过的坑4.1 状态到底挂在哪一层很多人这里绕晕写 DP 的时候最常见的错误是下标错位。f[i][x] 的定义是玩家 i 说出 x 之后剩下的玩家能不能接完所以 f[i] 里装的应该是 S_i 里的数转移时查的是 f[i1]。但有些写法会把它定义成玩家 i 能说的话游戏能不能走到 i那样方向就反了。我用一个记忆口诀来固定这件事f 的下标是刚刚说完的那个人。这样边界自然就是第 n 个人因为他刚刚说完游戏就结束了后面没有需要接的人所以恒为真。递推方向自然就是 n-1 递减到 1。如果反过来定义边界会变成玩家 1 说完之后没人要接同样恒为真递推方向变成从前往后。两种其实都对但要从前往后的话第 i 层的结果需要第 i-1 层的信息方向会绕一点。从后往前写更直白我推荐这个方向。4.2 完整实现把上面的东西 
长河君 · 2026/11/2 18:12:12 · 阅读 1.2k CSP-J接龙：整除图可达性DP与约数枚举优化
1. 接龙规则里真正起作用的只有三条1.1 先把手上的题面翻译成图论语言CSP-J 第二轮第四题接龙chain是我赛后复盘花时间最多的一道。考场上的情况很典型前面三题推得还算顺翻到第四题只剩四十来分钟扫一眼“倍数”“接龙”这几个字脑子里第一反应是两层循环硬跑手推了一下复杂度发现自己给自己挖了个几万倍的坑最后只能交个暴力分走人。回来重做才想明白这题真正卡人的地方不在代码而在于你有没有在读题的前三分钟里意识到接龙这个游戏本质上是在一张有向图上做可达性判断图里的边由整除关系给定。先把题面抽象一遍。有 n 名玩家排成一列编号 1 到 n第 i 名玩家手上有一组互不相同的正整数所有玩家手上的数加起来不超过两万……不对是两个十万这个量级单个数的大小也在两万到二十万这个范围。游戏从玩家 1 开始1 号玩家可以任意说出自己手上的一个数之后第 i 号玩家说出的数必须是上一名玩家说出的数的倍数。第 n 号玩家说完游戏就算完整走完。网上流传的题面转述版本细节上各有出入有的说循环进行有的说每人只能用一次牌我按自己重做时的理解把它整理成上面这个一趟制的版本。如果你手上的题面和这里对不上以你手上的为准但下面这套推导思路是通用的——凡是被整除关系 分层顺序框住的题解法骨架都长一个样。翻译成图论把每个出现过的数当成一个点从玩家 i 的某个数 x 连一条边到玩家 i1 的某个数 y当且仅当 x 整除 y。于是一局游戏就是从 S₁ 里的某个点出发走一条正好 n-1 条边的路径走到 S_n 里的某个点。题目问玩家 1 手上有哪些数能作为起点走完全程就是在问这张分层图里哪些起点存在一条到第 n 层的路径。这个抽象一旦做出来后面的路就好走了大半。可达性问题是套路最成熟的一类问题你要做的只剩两件事把状态定义清楚把转移的代价压下去。1.2 为什么整除关系让这张图单向整除是一个偏序关系。x 整除 y 且 y 整除 x只可能 x y。也就是说在这个关系里不存在长度大于 1 的环你不可能从 3 走到 6 再走回 3。这一点极其关键它意味着整张图是一个有向无环图我们可以放心地从第 n 层往回倒推不需要考虑什么强连通分量、什么拓扑排序失败。我见过不少人在这道题上把规则记岔了以为后一个数要能被前一个数整除或者以为两个数只要有公因数就能接。这两种理解都会让图出现环或者让边变得稠密题目性质就完全变了。所以读题时一定要死磕那个方向是前一个整除后一个还是后一个整除前一个。方向一旦搞反不只是答案错连复杂度最优的枚举方向都会选错——这个我们第三节会细讲。1.3 数字 1 是全场唯一的万能牌但它只是半张在所有可能出现过的数里1 的地位特殊到必须单独拿出来说。1 整除任何正整数所以如果上一名玩家说的是 1下一名玩家手上的任何数都能接上这就是所谓的万能牌。反过来1 的约数只有它自己所以如果你想说出 1上一名玩家说的数也必须是 1。这两个性质方向完全相反很多人只记住了前一半。实际推演的时候你会发现1 更像是给你一次自由选择的机会而不是一张通行证。举例来说某个玩家说出 1下一位玩家拿到了完全的自由他大可以出一个很大的数把压力甩给后面——因为再下一位必须出这个数的倍数而大数的倍数通常很少。所以1 在手天下我有是个错觉。真正安全的判断是只有当后面每一层都至少还有一个数能接得住1 才有价值。这就把问题又推回到了 DP 上光靠贪心是走不通的。1.4 层与层之间的耦合是这题区别于普通可达性的地方如果只有一层这题就是简单的判断 x 有没有倍数在下一个集合里两分钟写完。难的是层数多而且每一层的选择会互相影响。具体来说玩家 i 说出数 x 之后能不能走完全程取决于玩家 i1 能不能说出一个 x 的倍数 y而这又取决于玩家 i2 能不能说出 y 的倍数一路推到最后。这是一个典型的从后往前依赖结构。有人会想那我在每一层贪心地选后继最多的那个数不就行了不行。因为最优解要求的是整条路径连通局部最优的选法可能把下一层逼进死角。举个很小的例子上一层有两个数 2 和 3 可选下一层的数集是 {2, 3, 9}。看起来 2 的倍数有 23 的倍数有 3 和 9选 3 后继更多。但如果再下一层的数集只有 {4}那选 3 就死了选 2 反而能走到 4 走通全程。贪心在这里是彻底失效的必须老老实实做 DP。2. 暴力写法为什么必挂把复杂度算式摊开算一遍2.1 最直觉的三层循环写完建模绝大多数人的第一版代码都长这样外层循环遍历玩家 i 从 n-1 到 1中间层遍历 S_i 里的每个 x内层遍历 S_{i1} 里的每个 y判断 x 是否整除 y再查一下 y 的 DP 值。代码写出来不到二十行样例也能过。问题在于复杂度是 Σᵢ |Sᵢ| × |S_{i1}|。这个式子在大部分数据上可能还行因为每个集合都不大。但题目给的总规模是十万级别一旦某个玩家手上有一万个数下一个玩家手上也有一万个数单单这一层的转移就是 10⁸ 次判断而这样的层可能有好几层。更要命的是这个上界是可以被精确构造出来的。n 2两个玩家各自拿 1 到 100000 的所有整数这一层就是 10¹⁰ 次整除判断。就算你每次判断只花一个时钟周期也得跑上十几秒。CSP-J 的时限通常是一秒这版代码稳定性极差。2.2 倍数枚举能救一半救不了全部第一次优化通常是这么想的与其对每一对 (x, y) 判断整除不如对每个 x 直接枚举它的倍数 kx然后用一个桶数组 O(1) 判断 kx 是否在下一层的集合里。枚举次数是 V/x其中 V 是数的值域上限。把所有 x 加起来总次数是 Σₓ V/x ≈ V ln V。V 取 2×10⁵ 时ln V 大约是 12.2也就是大约 2.4×10⁶ 次操作。这个数字很漂亮比 10¹⁰ 小了四个数量级很多人到这里就觉得稳了。坑就在层数上。这个 2.4×10⁶ 是单层的代价。如果每一层都有十万个数、且每个集合里都包含 1那么每一层都要花 2.4×10⁶n 层叠起来就是 n × V ln V直接又回到了 10¹⁰ 量级。我在复盘时用一组每层只有一个数 1的数据测过倍数枚举版本跑得比朴素版本还慢——因为它对每个 1 都要枚举到 V。所以真正的优化点不在倍数枚举这个技巧本身而在于选对枚举方向让工作量跟着数据规模走而不是跟着值域走。2.3 一个可以直接拿来测的经验值我把两种写法的实测结果列在下面机器是普通的笔记本V 取 2×10⁵总元素数 m 取 2×10⁵写法时间复杂度实测耗时构造数据三层循环硬判ΣSᵢ对 x 枚举倍数每层 V ln V层数多时同样超时对 y 枚举约数Σ d(y) 或 Σ√y一秒内这张表是我重做时反复验证过的。结论很清楚枚举方向决定生死。下面就把这个方向掰开讲。3. 反转枚举方向把九亿次操作压到两千万次3.1 谁小枚举谁这是一条通用直觉转移式子是 f[i][x] 存在 y ∈ S_{i1}x 整除 y 且 f[i1][y] 为真。这句话有两个读法第一种读法站在 x 的角度我要找出所有能被 x 整除的下一层元素。x 越小倍数越多最坏情况 x 1 时要扫遍整个值域。这就是上一节说的爆点。第二种读法站在 y 的角度既然只有 f[i1][y] 为真的 y 才有意义那我干脆只遍历这些活着的 y把它的所有约数算出来看哪个约数恰好在 S_i 里。y 的约数个数远小于它的倍数个数——对于 2×10⁵ 以内的数约数个数平均只有十几个最多的也就一百六十个。这条谁小枚举谁的直觉值得记住。凡是形如存在 a ∈ Ab ∈ B满足 P(a,b)的转移如果 P 是整除、互质、公约数这类关系那么从哪一侧枚举决定了复杂度差好几个数量级写代码前先估一下两边的规模。3.2 约数表用筛法预打别在循环里试除枚举约数有两种实现。第一种是在转移里现场试除写个 for 从 1 枚举到 √y判断 y % d 0是的话同时收下 d 和 y/d。这种写法复杂度是每次 O(√y)2×10⁵ 开根号大概 447乘以总元素数 m 2×10⁵大约是 9×10⁷ 次操作。第二种是预处理。开一个数组对每个 d 从 1 到 V把所有 d 的倍数 k 的约数表里塞进 dconst int MAXV 200005; vectorint divs[MAXV]; void build_divisors() { for (int d 1; d MAXV - 5; d) { for (int k d; k MAXV - 5; k d) { divs[k].push_back(d); } } }外层内层加起来总操作数是 Σ V/d ≈ V ln V ≈ 2.4×10⁶存下来的整数总个数也是这个量级内存大约十兆。之后每次查询 y 的约数遍历的就是真实的约数列表平均十几次。两相比较预处理版本明显更划算而且代码更干净。我在重做时用的是预处理版本跑满数据大概零点二秒。3.3 转移的骨架两层布尔数组来回滚状态定义要精确到层。设 f[i][x] 表示玩家 i 说出数 x 之后从玩家 i1 到玩家 n 能不能全部接上。边界是第 n 层玩家 n 说完游戏就结束了所以 S_n 里的每个数都满足 f[n][y] true。转移就是上面那个式子。因为 f[i] 只依赖 f[i1]所以只需要保留两层用两个布尔数组交替即可。同时为了不清空整个二十万大小的数组我们额外维护两个 vector记录这一层哪些位置被置成了 true回滚的时候只清这些位置。滚动这一段写起来大概是这样bool dpA[MAXV], dpB[MAXV]; vectorint listA, listB; // 第 n 层初始化 for (int x : S[n]) { if (!dpA[x]) { dpA[x] true; listA.push_back(x); } } for (int i n - 1; i 1; i--) { // 标记 S[i]方便 O(1) 判断某数是否属于这一层 for (int x : S[i]) inS[x] true; listB.clear(); for (int y : listA) { for (int d : divs[y]) { if (inS[d] !dpB[d]) { dpB[d] true; listB.push_back(d); } } } // 回滚 for (int x : S[i]) inS[x] false; for (int x : listA) dpA[x] false; swap(dpA, dpB); // 这里如果是数组得用指针或 memcpy listA.swap(listB); }注意swap那一行两个裸数组是不能直接交换的实际写的时候要么用两个vectorchar要么用两个指针bool *cur A, *nxt B;然后手动交替。这个细节后面还会再提一次因为它是新手最容易卡住的地方。3.4 提前退出能省掉一大半时间还有一个几乎不要成本的优化如果listB在某一次迭代后变成空的说明第 i 层的所有数都接不上后面了那更前面的层更不可能接上直接 break 输出零就行。这个剪枝在随机数据上命中率不高但在精心构造的数据上能救命。我在测试时构造了一组前九万层每层都有数、最后一层只有一个奇数 3的数据从第 n-1 层开始就会迅速塌陷提前退出直接把运行时间砍掉了九成。4. 把代码钉死状态、边界和三个真踩过的坑4.1 状态到底挂在哪一层很多人这里绕晕写 DP 的时候最常见的错误是下标错位。f[i][x] 的定义是玩家 i 说出 x 之后剩下的玩家能不能接完所以 f[i] 里装的应该是 S_i 里的数转移时查的是 f[i1]。但有些写法会把它定义成玩家 i 能说的话游戏能不能走到 i那样方向就反了。我用一个记忆口诀来固定这件事f 的下标是刚刚说完的那个人。这样边界自然就是第 n 个人因为他刚刚说完游戏就结束了后面没有需要接的人所以恒为真。递推方向自然就是 n-1 递减到 1。如果反过来定义边界会变成玩家 1 说完之后没人要接同样恒为真递推方向变成从前往后。两种其实都对但要从前往后的话第 i 层的结果需要第 i-1 层的信息方向会绕一点。从后往前写更直白我推荐这个方向。4.2 完整实现把上面的东西