【NOIP】1998真题解析 luogu-P1008 三连击 | GESP三、四级以上可练习
NOIP 1998 普及组真题，主要考察枚举算法与数位分离。题目要求将 $1 \sim 9$ 这些数字进行组合，寻找符合特定比例的三位数。这是一个很经典的暴力枚举题。GESP三、四级以上可练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。
luogu-P1008 [NOIP 1998 普及组] 三连击
题目要求
题目背景
本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。
题目描述
将 $1, 2, \ldots , 9$ 共 $9$ 个数分成 $3$ 组，分别组成 $3$ 个三位数，且使这 $3$ 个三位数构成 $1 : 2 : 3$ 的比例，试求出所有满足条件的 $3$ 个三位数。
输入格式
无
输出格式
若干行，每行 $3$ 个数字。按照每行第 $1$ 个数字升序排列。
输入输出样例 #1
输入 #1
1
无
输出 #1
1
2
3
4
5
6
192 384 576
* * *
...
* * *
（剩余部分不予展示）
说明/提示
NOIP1998 普及组 第一题
题目分析
这道题考察了基础的枚举算法，由于要用 $1 \sim 9$ 组成三个三位数且不出现重复，因此可以利用比例关系确定枚举边界，再对组成的数字进行合法性验证。
1. 确定枚举范围
根据题意，三个三位数的比例是 $1:2:3$。因此，只要确定了第一个（最小的）三位数，另外两个数就能被直接计算出来。
- 最小值限定：组成的三位数各数位不能重复且不能包含 $0$，因此最小可取的合法数字是 $123$。
- 最大值限定：题目要求最大的那个数必须是三位数，也就是乘以 $3$ 后不能超过 $999$。推算得知，最小的数最大不能超过 $999 \div 3 = 333$。 所以，外层循环控制第一个数字 $i$ 的范围从 $123$ 遍历到 $333$ 即可，极大地缩减了枚举次数，提升了效率。
2. 判断数字的合法性
对于在范围内枚举出来的数字 $i$，计算出它的两倍 $s = i \times 2$ 以及三倍 $t = i \times 3$。然后，需要验证 $i, s, t$ 的这 $9$ 个数位是否恰好使用了 $1 \sim 9$ 这 $9$ 个数字各一次。
- 可以使用一个大小为 $10$ 的计数数组
n[10]来统计每一个数字出现的次数。 - 编写判定函数
checkNum，通过不断取模%和整除/将三位数的百位、十位和个位分离出来。 - 如果分离出的数位包含 $0$，或者该数字已经被统计过了（记录次数 $> 1$），就说明含有重复或不合法的数字。
- 将 $i, s, t$ 三个数结合起来统计，如果三者都依次通过了合法性校验，就说明它们符合条件，输出这组答案。验证完毕后使用
memset将统计数组清零，方便进行下一次循环判定。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstring>
#include <iostream>
// 全局数组，用于统计数字 1~9 在分离出的数位中出现的次数
int n[10];
// 校验一个三位数 x 的每一位是否合法（不能有 0 且不能与已有数字重复）
bool checkNum(int x) {
int a = x / 100; // 取百位
int b = (x / 10) % 10; // 取十位
int c = x % 10; // 取个位
// 题目要求由 1~9 组成，不包含 0
if (a == 0 || b == 0 || c == 0) {
return false;
}
// 对应数字记录出现次数加一次
n[a]++;
n[b]++;
n[c]++;
// 如果任何一个数字出现的次数大于 1，说明有重复，不符合题意
// 注意：这里的 n 数组是全局共享的，所以也会和另外两个数字一起累计校验
if (n[a] > 1 || n[b] > 1 || n[c] > 1) {
return false;
}
// 验证通过
return true;
}
int main() {
// 最小合法数字为 123，最大的数乘 3 不能超过三位数所以上限是 999 / 3 = 333
// 在这个范围内进行暴力枚举最小的三位数
for (int i = 123; i <= 333; i++) {
int s = i * 2; // 按比例 1:2 计算出第二个三位数
int t = i * 3; // 按比例 1:3 计算出第三个三位数
// 分别验证 i, s, t，判断 9 个数位是否刚好填满 1~9
// 注意：C++ 中 && 具有短路特性，左侧若不合法（返回 false），右侧不会继续执行
// 这样不仅提升了效率，且外层的 memset 会确保数组状态每轮都被重置
if (checkNum(i) && checkNum(s) && checkNum(t)) {
std::cout << i << " " << s << " " << t << std::endl;
}
// 每次枚举完不论成功与否，都要清空统计数组以便下一轮检测
memset(n, 0, sizeof(n));
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
