P3339 整数小拼接问题代码修正与优化

我看到您的代码思路是正确的，但存在几个关键问题导致结果错误。让我帮您分析并修正： ## 🔍 问题分析 您的代码主要有以下问题： 1. **整数拼接逻辑错误**：当 `a[i]` 作为前半部分时，拼接后的数应该是 `a[i] * pow10[后半部分位数] + 后半部分` 2. **重复计数问题**：原始代码的计数方式和减去自身的方式存在问题 3. **边界条件处理**：需要对每个元素分别处理作为前半部分和后半部分的情况 ## ✅ 修正后的代码 ```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]; if (tmp == 0) { d = 1; // 处理 a[i] = 0 的情况 } else { 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) { // 拼接公式：a[i] * 10^d + x <= K // 即：x <= (K - a[i] * 10^d) if (a[i] > K / pow10[d]) continue; // 避免溢出 ll limit = K - a[i] * pow10[d]; if (limit < 0) continue; // 在 groups[d] 中二分查找 <= limit 的元素个数 int cnt = upper_bound(groups[d].begin(), groups[d].end(), limit) - groups[d].begin(); // 计数时排除自身（i == j 的情况） if (d == len[i] && a[i] <= limit) { cnt--; } ans += max(0, cnt); } } cout << ans << '\n'; return 0; } ``` ## 🎯 关键修改说明 ### 1. 修正拼接公式 - **原代码**：`need = K - a[i]` ❌ - **修正后**：`limit = K - a[i] * pow10[d]` ✅ - 因为拼接后的数 = `a[i] * 10^d + 后半部分` ### 2. 溢出处理 - 添加了 `if (a[i] > K / pow10[d]) continue;` 防止乘法溢出 - 添加了 `if (limit < 0) continue;` 处理负数情况 ### 3. 去重逻辑优化 - 在计数时直接排除自身（当位数匹配且值在范围内时减1） - 使用 `max(0, cnt)` 确保计数不为负数 ### 4. 处理0的情况 - 添加了对 `a[i] == 0` 的位数判断 ## 💡 开发建议 1. **使用更大的数据类型**：考虑使用 `__int128` 或 `unsigned long long` 提高上限 2. **前缀和优化**：对于大量重复查询，可以预先计算前缀和加速 3. **并行计算**：如果数据量特别大，可以考虑并行化处理 4. **边界测试**：特别注意 K 很小或很大的边界情况 ## ⚡ 性能优化 如果还要进一步优化，可以考虑： - 使用 `unordered_map` 缓存计算结果 - 对分组进行前缀和预处理 - 使用二分查找的一次性扫描替代嵌套循环 ######[AI写代码神器 | 1059点数解答 | 2026-06-07 15:27:29]