【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

TEXT

无

输出 #1

TEXT

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 将统计数组清零，方便进行下一次循环判定。

示例代码

CPP

#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;
}

C++ 算法考级专栏