P1618 三连击（升级版）
题目描述
将 \(1, 2,\ldots, 9\) 共 \(9\) 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 \(A:B:C\)，试求出所有满足条件的三个三位数，若无解，输出 No!!!。
输入格式
三个数，\(A,B,C\)。
输出格式
若干行，每行 \(3\) 个数字。按照每行第一个数字升序排列。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
保证 \(0 \le A<B<C \le 999\)。
\(\text{upd 2022.8.3}\)：新增加二组 Hack 数据。
Tip
xurry的做法
我让ai给我加注释了，但是思路是我没有参考ai的情况下想出来的，想到用字符串处理纯粹是因为上一章大数加法给我的启发，以及java里to_string方法的重要作用
#include <iostream>
#include <string>
using namespace std;
// 检查是否恰好包含 1-9 这九个数字
bool is_full(string s) {
int vis[10] = { 0 };
for (auto x : s) {
if(x=='0') return false;// 1-9不包含0,这里也是剪枝的思想
int index = x - '0';
vis[index] = 1;
}
for (int i = 1;i <= 9;i++) {
if (!vis[i]) return false;// 每个数字必须出现且仅出现一次
}
return true;
}
int main() {
int A, B, C;
cin >> A >> B >> C;
// i 至少从 123 开始，因为三个数总共 9 位，每个数大概是三位数
for (int i = 123;i < 1000;i++) {
// 严格按照 A:B:C 比例计算，且避免浮点误差
if (i * B % A != 0 || i * C % A != 0) continue;
string s1 = to_string(i);
string s2 = to_string(i * B/A);
string s3 = to_string(i * C/A);
string s = s1 + s2 + s3;
//适当剪枝
if (s2.size() != 3 || s3.size() != 3) continue;
if (is_full(s))
cout << s1 << " " << s2 << " " << s3<<endl;
}
return 0;
}
Danger
这下面是Gemini给我的做法，我自己的做法我觉得思路上理解更简单，而且本题读题可以发现整体一共也就123~999种可能，所以可以暴力枚举；我的思路如上
📌 题目分析
给定数据：
要求用 1 到 9 这 \(9\) 个数字组合成三个三位数（每个数字恰好用一次），且满足 \(A:B:C\) 的比例。若无解输出 No!!!。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么可以直接暴力搜索
三个三位数，第一个数的范围最小也是 123，最大也就是 987。
最多只需要枚举 800 多次，就算对全排列进行暴力尝试，对于计算机来说也是降维打击，瞬间就能跑完。
2️⃣ 核心枚举逻辑
我们选择枚举第一个数 num1（范围 123 到 987）：
根据比例，可以算出另外两个数：
必须满足两个前置条件才能继续验证：
1. 能整除：num1 * B % A == 0 且 num1 * C % A == 0
2. 是合法三位数：num2 ≤ 987 且 num3 ≤ 987
3️⃣ 判断 1~9 是否各出现一次
写一个分解数字的独立函数：
每次把 num1, num2, num3 拆开，用一个桶（数组 cnt）记录每个数字出现的次数。
最终检查：
4️⃣ 时间复杂度
一层循环最多 800 次，内部只做几次简单的除法和取余操作。
极快，耗时几乎为 0 毫秒，绝对不超时。
💻 C++代码
#include <iostream>
using namespace std;
// 验证三个数是否刚好用完 1~9 各一次
bool check(int a, int b, int c) {
int cnt[10] = {0}; // 桶，用来记录 0~9 的出现次数
// 拆解 a
while (a > 0) { cnt[a % 10]++; a /= 10; }
// 拆解 b
while (b > 0) { cnt[b % 10]++; b /= 10; }
// 拆解 c
while (c > 0) { cnt[c % 10]++; c /= 10; }
// 规则：不能有 0
if (cnt[0] != 0) return false;
// 规则：1~9 必须各出现恰好 1 次
for (int i = 1; i <= 9; i++) {
if (cnt[i] != 1) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int A, B, C;
cin >> A >> B >> C;
// 特判：如果 A 是 0，则无法作为除数计算比例，必定无解
if (A == 0) {
cout << "No!!!\n";
return 0;
}
bool found = false; // 标记是否找到合法解
// 暴力枚举第一个三位数
for (int i = 123; i <= 987; i++) {
// 先保证能够整除，满足精确比例
if (i * B % A == 0 && i * C % A == 0) {
int j = i * B / A;
int k = i * C / A;
// 保证生成的另外两个数也是三位数
if (j >= 123 && j <= 987 && k >= 123 && k <= 987) {
// 最后验证是否刚好用完了 1~9
if (check(i, j, k)) {
cout << i << " " << j << " " << k << "\n";
found = true;
}
}
}
}
// 如果一个解都没找到，输出 No!!!
if (!found) {
cout << "No!!!\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 浮点数计算引起精度丢失或错误
千万不要写成 num1 * (B / A)。
在 C++ 整数运算下，如果 B < A，B / A 会直接变成 0。如果使用 double 去算，又可能会产生浮点数的精度误差。
正确做法：纯整数交叉相乘验证，先乘后除（即 num1 * B / A）。
❌ 2. 忘记特判 A = 0 的情况
比例中如果有 \(0\)，比如 \(0:1:2\)，除数 A 就会变成 \(0\) 导致程序运行崩溃（RE）。虽然正常数据少见，但做题必须严谨。
❌ 3. 无解情况大小写及标点错误
题目要求如果没有找到解，必须输出：
首字母大写，连着三个英文感叹号。用一个 bool found 标志位来判断最后是否需要输出这个字符串。错一个符号都会全盘 WA。
🚀 一句话总结
🔥 补充
关于另一种暴力（全排列 DFS）：
这道题也可以利用 <algorithm> 库里的 next_permutation 函数。把数组 {1, 2, 3, 4, 5, 6, 7, 8, 9} 进行 \(9!\) 次全排列。每次将前三个数字拼成 num1，中间三个拼成 num2，最后三个拼成 num3，然后验证比例 \(num1 \cdot B == num2 \cdot A\) 以及 \(num1 \cdot C == num3 \cdot A\)。这也是一种纯粹且暴力的解法，同样可以在时限内轻松 AC。