[NOIP 1998 普及组] 三连击

GitHub跳转原题关系图返回列表

枚举第一个三位数 x，再检查 x、2x、3x 是否刚好使用了数字 1 到 9 各一次。

OJ: luogu

题目 ID: P1008

难度:入门

标签:枚举构造

日期: 2026-06-19 00:30

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

要求把数字 1..9 恰好各用一次，分成三组组成三个三位数 a,b,c，并满足：

a : b : c = 1 : 2 : 3

输出所有满足条件的三元组。

思路

先看一个可以直接验证想法的朴素解：

把 1..9 的排列全部枚举出来，前三位组成第一个数，中间三位组成第二个数，后三位组成第三个数，再检查比例关系。

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int p[10];
int vis[10];

int get_num(int l, int r) {
    int x = 0;
    for (int i = l; i <= r; i++) {
        x = x * 10 + p[i];
    }
    return x;
}

void dfs(int dep) {
    if (dep == 10) {
        int a = get_num(1, 3);
        int b = get_num(4, 6);
        int c = get_num(7, 9);

        if (a * 2 == b && a * 3 == c) {
            cout << a << ' ' << b << ' ' << c << '\n';
        }
        return;
    }

    for (int d = 1; d <= 9; d++) {
        if (vis[d]) {
            continue;
        }
        vis[d] = 1;
        p[dep] = d;
        dfs(dep + 1);
        vis[d] = 0;
    }
}

void solve() {
    dfs(1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

这个办法当然能做，但搜索空间比实际需要的大很多。

真正关键的观察是：

如果第一个数是 x，那么另外两个数一定只能是：

  • 2x
  • 3x

所以我们没必要先排列数字，只要直接枚举第一个三位数 x 即可。

对每个 x，检查：

  • x,2x,3x 中是否出现了 0
  • 数字 1..9 是否都恰好出现一次

如果都满足，就输出这一组答案。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

int used[10];

int check(int x) {
    memset(used, 0, sizeof(used));

    for (int t = x; t <= x * 3; t += x) {
        int cur = t;
        while (cur > 0) {
            int d = cur % 10;
            if (d == 0 || used[d]) {
                return 0;
            }
            used[d] = 1;
            cur /= 10;
        }
    }

    for (int d = 1; d <= 9; d++) {
        if (used[d] == 0) {
            return 0;
        }
    }
    return 1;
}

void solve() {
    for (int x = 123; x <= 329; x++) {
        if (check(x)) {
            cout << x << ' ' << x * 2 << ' ' << x * 3 << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

时间复杂度是常数级，空间复杂度是 O(1)O(1)。

总结

这题的重点在于从比例关系反推搜索范围。

先想到“确定最小的那个数，后两个数就跟着确定”，写法就会简洁很多。