打卡信奥刷题3036用C实现信奥题 P6509 [COCI2007-2008] JEDNAKOST第一次看到 P6509 的题名 JEDNAKOST我愣了一下——这是个克罗地亚语单词意思是“相等”。题目本身倒不复杂但它把“字符串切分”“回溯搜索”“等式校验”三个点揉在一起属于那种很典型的信奥入门到进阶之间的练手题。你需要在给定的一长串数字里插入加号和一个等号让式子成立然后输出所有可行等式。我当时刷完最大的感受是这题考的不是你会不会某个高级算法而是你能不能把“插入符号”这件事翻译成“给字符串分段”然后用 DFS 加剪枝老老实实枚举完所有可能。这篇文章我按自己实际做题的顺序来写先讲题意里最容易理解偏的地方再讲搜索思路是怎么一步步收敛的然后给出完整可跑的 C 代码最后把我在提交过程中踩过的几个坑单独拿出来说。适合正在刷 DFS、回溯、字符串处理题目的信奥党参考至少需要看得懂递归和 vector 的基本用法。1. 题意精读先搞清楚“插入加号和等号”到底在做什么1.1 原题在说什么题目输入是一个很长的数字串 S 和一个整数 K。要求你在 S 的数字之间插入若干加号并且插入一个等号最终让整个等式成立。举例来说如果 S 121K 13那么一种合法等式是12113这个例子里“12”和“1”都是由 S 中的连续数字段构成的它们之间插入了加号最后等号右边就是输入的 K。特别要注意S 里的每一位数字都必须被用到而且顺序不能改变。你不能把“121”重排成“112...”这种只能在相邻数字之间选择切或者不切。很多同学第一次看题会误解成“等号右边也要从 S 里截一段出来”于是跑去枚举等号的位置把简单问题复杂化。原题的意思是右边已经给了你一个明确的 K不用再从 S 里截。这一点想清楚后面所有思路都顺了。1.2 把“插入符号”翻译成“给字符串分段”这是整道题最关键的思维转换。你想象一下在长度为 n 的数字串里相邻两个数字之间有 n-1 个空隙。每个空隙你可以做两个决定之一放一个加号或者什么都不放。等号是放在整个表达式末尾的所以不用参与空隙枚举。于是问题变成了把数字串 S 从左到右切成若干连续段每一段作为一个整数这些整数用加号连接最后整体等于 K。举个例子S 1234你可以切成 1、23、4对应表达式 1234也可以切成 1234 一整段对应表达式 1234K。切分点选在哪里就相当于在哪里放加号。这个视角一旦建立DFS 的搜索对象就从“每个空隙放什么符号”变成了“每一段的右端点在哪个位置”代码写起来也舒服很多。1.3 一个必须刻在脑子里的前提K 是等号右边也是剪枝尺度因为等号右边永远是 K所以这题有一个非常强的约束任何一段的数值都不能超过 K。道理很简单如果某一段本身就是 137而 K 只有 100那这一项哪怕只有它自己也已经超过目标整个和只可能更大绝对不可能等于 K。这个约束意味着什么意味着每一段的长度其实被 K 的位数限制住了。如果 K 是一个三位数那么任何一段最多只能取三位因为四位数的数值肯定大于等于 1000超过所有三位数 K 的上限。这个观察直接决定了搜索的枚举范围也让 DFS 的剪枝有了坚实的依据。另外还有一条约束容易忽略每一段作为一个十进制数不能有前导零。也就是说单独的 0 是合法的数字但 00、01 这种形式不合法。别小看这个限制很多人漏掉它样例能过一交上去就错。2. 搜索思路的推导为什么 DFS 在这里是自然选择2.1 最朴素的想法枚举所有空隙假设 S 的长度是 n那么有 n-1 个空隙。每个空隙有“切/不切”两种选择所以暴力枚举所有切分方案的数量是 2^(n-1)。n2^(n-1)大概量级1516384一万多20524288五十多万2516777216一千六百多万30536870912五亿多可以看出n 在 20 左右时暴力枚举勉强可以接受一旦 n 到 30纯枚举就不是开玩笑的事了。这也是为什么这道题不能只写一个双层循环把所有切法检查一遍必须引入剪枝。但 DFS 的价值不仅是暴力枚举它真正的威力在于你可以一边生成切分方案一边检查当前已经形成的和一旦发现不可能立刻掉头不用等整棵树生成完。2.2 第一层剪枝任何一段都不能超过 K在 DFS 枚举右端点 r 的时候我们可以实时计算当前这一段 S[pos..r] 的数值 v。如果 v 已经大于 K那么这一刀切在这里肯定不合法因为光这一项就超了后面加什么都白搭。这里有个细节值得说v 是随着 r 往右移动而增大的。所以如果 v 已经大于 K那么继续把 r 往右移v 只会更大于是这一层循环可以立刻 break而不是 continue。很多初学同学在这里写 continue结果明明已经不可能了还在往后枚举白白浪费计算。这个剪枝实际上把最坏情况下的枚举次数降到了一个非常可控的范围。因为 K 通常是一个有限大小的整数当 K 比较小时每一段长度都短搜索树的分支数会明显减少。2.3 第二层剪枝边切边累计超过 K 就回头除了检查单个段值还要维护一个“当前累计和”sum。每切出一段 v就把它加到 sum 上然后继续递归。一旦 sum 超过 K就说明这条路已经不可能了哪怕后面的段全是 0和也只会保持在当前水平不会下降。这两层剪枝配合起来效果很显著。举个例子S 123456789K 100。第一个字符 1 可以作为第一段也可以把 12 作为第一段甚至 123 作为第一段但 1234 作为第一段就已经超过 K 了所以第一刀最多试到 123。递归到第二层类似地每一层可以尝试的右端点数量都非常有限。实际跑下来这个 DFS 加两层剪枝在 S 长度 30 以内基本是秒出结果。我后面在踩坑部分会专门说为什么看起来很小的 n 也可能超时——往往不是剪枝不够多而是某个边界条件写错了比如 continue 写成了 break或者漏了前导零判断。2.4 为什么不用 BFS 或动态规划直接扫一遍其实也能用动态规划做但输出所有方案这件事让 DP 变得很别扭。DP 适合求方案数、判断可行性、求最优解而本题要求把所有具体等式打印出来本质上是需要完整搜索路径的。DFS 天然擅长在递归过程中保存路径所以它是最自然的选择。不过当 S 很长时裸 DFS 会重复计算很多相同的状态。我在第 3 部分会说怎么用记忆化搜索把 DFS 升级成正解。3. 记忆化搜索当串变长怎么把 DFS 升级成正解3.1 状态设计dp[pos][sum] 还是 dp[pos][need]如果题目数据变大S 的长度超过 30甚至到几千裸 DFS 即使有剪枝也可能被卡。原因是大量子问题会被反复计算。比如你在递归中可能多次到达“从第 10 位开始当前累计和已经是 50”这个状态每次都要重新枚举它后面的所有情况。解决办法是记忆化。状态可以设为dp[pos][sum] 从第 pos 位开始已经累计的和为 sum之后还能不能凑出 K转移就是枚举下一段的右端点 r检查段值 v 合法然后看 dp[r1][sumv] 是否为真。还有一种写法是反向定义dp[pos][need] 从第 pos 位开始后面这些数字还需要凑出 need可行吗两种写法本质一样我写代码时习惯用 sum 版本因为和 DFS 的自然顺序更一致。但不管用哪种核心都是把二维状态压进数组从而让每个状态只被计算一次。3.2 用“可行性 DP”指导“方案打印”这里有一个很实用的套路先跑一遍 DP只记录每个状态可不可行再跑第二遍 DFS但 DFS 只沿着“可行”的分支走。为什么要分两步因为如果你直接在 DFS 里做记忆化会遇到一个麻烦记忆化表记的是“从某个状态出发可不可行”但你打印方案时需要完整路径不能只记 bool。你可以用一个数组记录转移到了哪个右端点等于做一个记忆化的回溯但代码复杂度会高很多。更稳妥、更好理解的做法是第一遍从后往前或从前往后计算 dp[pos][sum]得到所有可行状态。第二遍DFS 从 (0, 0) 出发枚举右端点 r 时先检查下一状态 dp[r1][sumv] 是否为 true如果为 true 才进入递归。这样做的好处是DFS 永远不会走进死胡同所有探索的分支最终都能到达答案剪枝效率极高。对于数据范围较大的版本这个优化是决定能不能过题的关键。3.3 什么情况下必须加记忆化我的经验判断是S 长度超过 25K 又相对较小比如一万以内裸 DFS 大概率会超时如果 K 很大二维数组开不下那就只能靠剪枝并期待数据范围本身不夸张。所以拿到题的第一步永远是看数据范围而不是直接写代码。我在刷题平台上看到的版本裸 DFS 加剪枝就能过因为 n 并不大。但如果你在别的 OJ 上遇到加强版数据一定要会这套“可行性 DP 方案 DFS”的组合方法。这也是为什么我在文章里把两种做法都写清楚。4. C 实现细节与逐段拆解4.1 输入处理string long long别用 int 读 K先给出完整代码然后我逐段讲关键点。#include bits/stdc.h using namespace std; string s; long long K; int n; vectorstring cur