P1006 小核桃与切割数字：DFS求解不同求和结果

好的，这是一个典型的 **数字切割与求和** 问题。由于数据范围很大（最大可达 \(10^{18}\)），我们需要一种高效的算法来枚举所有可能的切割方案，并统计不同的求和结果。 下面我将为你详细分析并提供 C++ 的解题思路与代码实现。 ## 🧩 问题分析 给定一个数字字符串 \(n\)，我们可以在任意两个数字之间选择**切或不切**。切割后，会得到若干段数字，将这些段对应的整数相加，求能得到多少种**不同的和**。 ### 核心要点： - 数字长度 \(len\) 最大为 19（因为 \(10^{18}\) 是 19 位数）。 - 切割位置共有 \(len-1\) 个，每个位置有两种选择（切 / 不切），总共 \(2^{len-1}\) 种方案。 - 当 \(len=19\) 时，方案数约 \(2^{18}=262144\)，在可接受范围内。 - 但是直接暴力枚举所有方案，并计算每种方案的和，会超时吗？**不会**，262k 种方案，对于 1000ms 和 O(方案数) 的算法是可行的。 ## 🚀 解题思路 我们可以采用 **深度优先搜索 (DFS)** 或 **二进制枚举** 来模拟切割： 1. **将数字视为字符串**，方便处理每一位。 2. 从第一个字符开始，递归地决定是否在这里切割。 - 如果切割，则当前段结束，记录当前段的值，开始新一段。 - 如果不切割，则继续累加当前段的数字。 3. 当遍历到字符串末尾时，将当前段的值加到总和中，并记录这个和到集合（`set`）中。 4. 最后输出集合的大小。 ### 💡 算法效率 - 时间复杂度：\(O(2^{len} \times len)\)，当 \(len=19\) 时约 500 万次操作，安全。 - 空间复杂度：\(O(2^{len})\) 用于存储不同的和，实际远小于此。 ## 💻 C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; string s; int len; unordered_set<long long> sums; // 去重存储 void dfs(int pos, long long curSegment, long long totalSum) { if (pos == len) { // 到达末尾，将最后一段的和加入 totalSum += curSegment; sums.insert(totalSum); return; } int digit = s[pos] - '0'; // 1. 不切割：当前段继续累加 dfs(pos + 1, curSegment * 10 + digit, totalSum); // 2. 切割：当前段结束，开始新一段 dfs(pos + 1, digit, totalSum + curSegment); } int main() { cin >> s; len = s.length(); // 从第一个数字开始，当前段值为 s[0]，总和为 0 dfs(1, s[0] - '0', 0); cout << sums.size() << endl; return 0; } ``` ## ⚠️ 代码详解 - **`dfs(pos, curSegment, totalSum)`** - `pos`：当前处理到的位置索引。 - `curSegment`：当前未切割段累积的数值。 - `totalSum`：已切割完成的各段之和（不包括当前段）。 - **边界条件**：当 `pos == len` 时，将 `curSegment` 加到总和，并存入集合。 - **两种递归分支**： - **不切割**：延续当前段，`curSegment` 乘 10 再加当前数字。 - **切割**：将当前段值加到 `totalSum` 中，新段从当前数字开始。 ## 🧪 样例验证 输入 `123`： - 不切：123 → 和 123 - 1|23 → 1+23=24 - 12|3 → 12+3=15 - 1|2|3 → 1+2+3=6 输出：4 ✅ 输入 `111`： - 不切：111 - 1|11 → 1+11=12 - 11|1 → 11+1=12 （相同） - 1|1|1 → 1+1+1=3 去重后：{111, 12, 3} → 输出 3 ✅ ## 📈 进阶优化与建议 1. **使用 `long long`**：由于最大和可达 \(10^{18}\) 级别的数，32 位 int 会溢出。 2. **使用 `unordered_set`** 而非 `set`：平均 O(1) 插入，避免排序开销。 3. **DFS 剪枝**：本题不需要剪枝，因为方案数不多，但若长度再大，可考虑记忆化搜索或 DP。 4. **动态规划思想**：其实这题也可以用线性 DP 来做： - `dp[i][sum]` 表示前 i 位能否凑出总和 sum，但状态空间较大，不如 DFS 直观。 ## 📚 相关知识学习 - **DFS（深度优先搜索）**：回溯法的基础，常用于排列组合、切割问题。 - **二进制枚举**：也可用 `for mask in 0..(1<<(len-1))` 枚举所有切割方案，但需要处理进位，DFS 更自然。 - **字符串处理**：将数字转为字符串便于逐位操作。 ## 💡 开发建议 - **先理解题意，再动手编码**：画一画递归树，理清切割逻辑。 - **测试边界情况**： - 数字只有一位（如 5）：只有一种结果。 - 数字各位相同（如 111）：注意去重。 - 大数字（\(10^{18}\) 级别）：确保使用 `long long`。 - **小规模数据可用 `set`，大规模用 `unordered_set`** 提高性能。 ######[AI写代码神器 | 1351点数解答 | 2026-07-04 08:20:48]