【NOIP真题】1998 luogu-P1008 三连击 | GESP三、四级以上可练习
NOIP 1998 普及组真题,主要考察枚举算法与数位分离。题目要求将 1 9 这些数字进行组合,寻找符合特定比例的三位数。这是一个很经典的暴力枚举题。GESP三、四级以上可练习。题目难度⭐⭐☆☆☆,洛谷难度等级普及−。
NOIP 1998 普及组真题,主要考察枚举算法与数位分离。题目要求将 这些数字进行组合,寻找符合特定比例的三位数。这是一个很经典的暴力枚举题。GESP三、四级以上可练习。题目难度⭐⭐☆☆☆,洛谷难度等级普及−。
luogu-P1008 [NOIP 1998 普及组] 三连击
题目要求
题目背景
本题为提交答案题,您可以写程序或手算在本机上算出答案后,直接提交答案文本,也可提交答案生成程序。
题目描述
将 共 个数分成 组,分别组成 个三位数,且使这 个三位数构成 的比例,试求出所有满足条件的 个三位数。
输入格式
无
输出格式
若干行,每行 个数字。按照每行第 个数字升序排列。
输入输出样例 #1
输入 #1
无输出 #1
192 384 576
* * *
...
* * *
(剩余部分不予展示)说明/提示
NOIP1998 普及组 第一题
题目分析
这道题考察了基础的枚举算法,由于要用 组成三个三位数且不出现重复,因此可以利用比例关系确定枚举边界,再对组成的数字进行合法性验证。
1. 确定枚举范围
根据题意,三个三位数的比例是 。因此,只要确定了第一个(最小的)三位数,另外两个数就能被直接计算出来。
- 最小值限定:组成的三位数各数位不能重复且不能包含 ,因此最小可取的合法数字是 。
- 最大值限定:题目要求最大的那个数必须是三位数,也就是乘以 后不能超过 。推算得知,最小的数最大不能超过 。 所以,外层循环控制第一个数字 的范围从 遍历到 即可,极大地缩减了枚举次数,提升了效率。
2. 判断数字的合法性
对于在范围内枚举出来的数字 ,计算出它的两倍 以及三倍 。然后,需要验证 的这 个数位是否恰好使用了 这 个数字各一次。
- 可以使用一个大小为 的计数数组
n[10]来统计每一个数字出现的次数。 - 编写判定函数
checkNum,通过不断取模%和整除/将三位数的百位、十位和个位分离出来。 - 如果分离出的数位包含 ,或者该数字已经被统计过了(记录次数 ),就说明含有重复或不合法的数字。
- 将 三个数结合起来统计,如果三者都依次通过了合法性校验,就说明它们符合条件,输出这组答案。验证完毕后使用
memset将统计数组清零,方便进行下一次循环判定。
示例代码
#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;
}看完题解,马上用 240 关实战检验掌握度
覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。
配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。
同专栏相关推荐
【NOIP真题】2011 luogu-P1003 铺地毯 | GESP三、四级以上可练习
NOIP 2011 提高组真题,枚举与模拟考点应用,重点理解逆向思维(倒序遍历)的优化策略。GESP 三、四级及以上考生可以练习。题目难度⭐⭐★☆☆,洛谷难度等级普及−。
【NOIP真题】2000 luogu-P1023 税收与补贴问题 | 适合 GESP四、五级以上练习
NOIP 2000 普及组真题,综合考察分段线性插值、利润建模与线性不等式求解。解题核心是:对每个竞争价格推导出税/补贴金额 t 的线性约束,求所有约束的交集,最终取绝对值最小的整数 t。适合GESP五级以上考生练习。题目难度⭐⭐⭐,洛谷难度等级普及/提高−。
【NOIP真题】1998 luogu-P1009 阶乘之和 | GESP四、五级以上可练习
NOIP 1998 普及组真题,主要考察高精度加法与高精度乘法,属于GESP五级考点。适合GESP四、五级以上可练习。题目难度⭐⭐☆☆☆,洛谷难度等级普及−。
OneCoder
始于 2012持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com