蓝桥杯整数拼接问题 C++ 高效解法与常见陷阱

好的，这个问题是一个经典的“整数拼接”计数问题，来自蓝桥杯省赛。我们需要高效地统计所有不同顺序拼接后小于等于 K 的整数对的数量。 下面我将从**问题分析**、**算法思路**、**C++ 代码实现**以及**常见陷阱与优化建议**几个方面为你详细解答。 --- ## 📘 问题分析 给定一个数组 `A`，从中选出两个不同的数（顺序不同视为不同拼法）拼接成一个新的整数。问有多少种拼法，使得拼接后的整数 ≤ K。 **关键点**： 1. **顺序不同算不同**：即使 `Ai == Aj`，`Ai+Aj` 和 `Aj+Ai` 也算两种。 2. **拼接方式**：将两个整数直接前后连接，例如 `12` 和 `345` 可以拼成 `12345` 或 `34512`。 3. **数据规模**： - n 最大可达 1e5，所以 O(n^2) 的暴力解法不可行。 - K 最大 1e10，Ai 最大 1e9。 - 需要将时间复杂度控制在 O(n log n) 或 O(n log n log n) 级别。 --- ## 💡 核心算法思路 ### 1️⃣ 预处理每个数的位数 - 拼接时，`A_i` 与 `A_j` 拼接其实就是 `A_i * 10^{len(A_j)} + A_j`。 - 我们需要知道每个数的**位数（digit length）**。 ### 2️⃣ 分组存储 - 将所有数按照**位数**分组，例如 `digit_len[i]` 存储所有位数为 `i` 的整数。 - 每个分组内的数进行**排序**，方便二分查找。 ### 3️⃣ 枚举与二分查找 - 对于每个数 `A_i`，枚举所有可能的位数 `len_j`（1~10，因为 K ≤ 1e10，Ai ≤ 1e9）。 - 对于每一个 `len_j`，我们计算： ``` target = (K - A_j) / 10^{len_j} ``` 注意：这里我们假设 `A_i` 作为前半部分，`A_j` 作为后半部分。为了计算满足条件的 `A_i`，我们需要将 `K` 减去 `A_j` 后再除以 `10^{len_j}`。 - 实际上，更常见的做法是： - 固定 `A_i` 作为前半部分，`A_j` 作为后半部分。 - 条件：`A_i * 10^{len(A_j)} + A_j <= K` - 等价于：`A_i <= (K - A_j) / 10^{len(A_j)}`（注意使用整数除法向下取整） - 但是这样对于每个 `A_j` 我们都要二分查找满足条件的 `A_i` 数量。 **更优的对称做法**： - 枚举每个数作为**前半部分**，然后对**所有可能的位数**分组去二分查找后半部分。 - 由于两组组合数是一样的，我们可以只做一次方向，最后结果乘以 2，再减去 i==j 的情况（但题目允许 i==j 吗？**不允许！** i ≠ j）。 - 但为了避免重复和 i=j 的情况，更稳妥的做法是： 1. 对每个数 `A[i]`，将它作为前半部分，在**所有其他数**中二分查找满足条件的后半部分。 2. 或者：先对所有数按位数分组并排序，然后对每个数，在对应分组中二分查找满足条件的个数，最后减去自己与自己匹配的情况。 **推荐方案**： - 将数组 `A` 复制一份，并计算每个数的位数。 - 对于每一个数 `A[i]`，我们枚举其作为**前半部分**时，后半部分可能的位数。 - 在后半部分对应的位数分组中，二分查找有多少个数使得 `A[i] * 10^{len_j} + x <= K`。 - 累加结果。 - 最后减去 `i == j` 的情况（即自己拼自己），因为题目要求 i≠j。 ### 4️⃣ 复杂度分析 - 分组排序：O(n log n) - 枚举每个数，对每个可能的位数（最多 10 种）进行二分查找：O(n * 10 * log n) ≈ O(n log n) - 总复杂度：O(n log n)，可以处理 1e5 规模。 --- ## 💻 C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; ll K; cin >> n >> K; vector<ll> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } // 1. 按位数分组 vector<ll> groups[11]; // 位数 1~10 vector<int> len(n); for (int i = 0; i < n; ++i) { int d = 0; ll tmp = a[i]; while (tmp) { ++d; tmp /= 10; } len[i] = d; groups[d].push_back(a[i]); } // 2. 每个分组排序 for (int i = 1; i <= 10; ++i) { sort(groups[i].begin(), groups[i].end()); } // 3. 计算 10 的次幂 ll pow10[11]; pow10[0] = 1; for (int i = 1; i <= 10; ++i) { pow10[i] = pow10[i-1] * 10; } ll ans = 0; for (int i = 0; i < n; ++i) { // 枚举后半部分可能的位数 for (int d = 1; d <= 10; ++d) { ll need = K - a[i]; ll limit = need / pow10[d]; // 在 groups[d] 中二分查找 <= limit 的元素个数 int cnt = upper_bound(groups[d].begin(), groups[d].end(), limit) - groups[d].begin(); ans += cnt; } // 减掉自己拼自己的情况（后半部分等于 a[i] 且位数相同） // 注意：这里减去的条件是后半部分也等于 a[i]，且位数也是 len[i] // 由于我们在二分时可能会把 a[i] 自己也算进去，需要减去 1 // 但只当 a[i] 在它自己的位数分组中且 a[i] <= limit 时才需要减 for (int d = 1; d <= 10; ++d) { ll need = K - a[i]; ll limit = need / pow10[d]; if (d == len[i] && a[i] <= limit) { ans -= 1; } } } cout << ans << '\n'; return 0; } ``` --- ## ⚠️ 常见陷阱与优化建议 ### 🔹 陷阱 1：整数溢出 - 当 `A_i` 为 1e9，乘以 10^10 会远超过 64 位整数范围。 - 但在本解法中，我们并未直接计算 `A_i * 10^d`，而是将不等式转化为 `A_i <= (K - A_j) / 10^d`，有效避免了溢出。 ### 🔹 陷阱 2：自己拼自己 - 题目要求 i ≠ j，所以对于每个 `A_i`，当我们在分组中找到它自己时，需要减去一次。 - 但注意：如果数组中有重复的元素，`A_i` 可能在分组中出现多次，我们只减一次（对应 i==j 的那一个）。其他重复的合法拼接是允许的。 ### 🔹 陷阱 3：位数计算 - 当 `A_i = 0` 时，位数问题？题目中 Ai ≥ 1，所以无需考虑。 - 对于 K 最多 1e10，最大位数为 11，但 A_i 最大为 1e9（10 位），所以后半部分位数最多为 10。 ### 🔹 优化建议 - **使用 `upper_bound` 而不是手写二分**，C++ STL 已高度优化。 - **预处理 10 的次幂**，避免重复计算。 - **分组后排序**可以大幅减少二分查找范围。 --- ## 📈 开发建议 1. **先写对，再写快**：先实现 O(n^2) 小规模验证，再优化到 O(n log n)。 2. **边界测试**：建议测试 n=1 的情况（答案是 0），以及 K 非常小或非常大的极端情况。 3. **使用 `long long`**：K 最大 1e10，计算过程中可能出现超过 int 范围的值。 4. **代码复用**：可以将“计算位数”、“二分计数”等写成辅助函数，提高可读性。 --- ## 📚 推荐学习资源 - **C++ 标准库算法**：`sort`、`upper_bound`、`lower_bound` 的用法。 - **数论基础**：十进制位运算与拼接原理。 - **蓝桥杯真题解析**：类似题目“整数拼接”在蓝桥杯中多次出现。 --- ######[AI写代码神器 | 2103点数解答 | 2026-06-07 15:25:15]