P1008 三连击

calendar May 4, 2026 · 5 分钟阅读 · 枚举  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1008
难度 橙题（普及-）
知识点 枚举

题目描述

将 1, 2, …, 9 共 9 个数分成三组，分别组成三个三位数，且使这三个三位数的比例正好是 1:2:3。

要求：

  • 三个三位数必须全部由 1~9 组成，每个数字恰好用一次，不能重复也不能遗漏
  • 找出所有满足条件的三个三位数，按格式输出

解题思路

核心思想

使用枚举 + 去重检查的方法：

  1. 最小的那个三位数最小是 123，最大不超过 329（因为 329×3=987，再大就超出三位数范围了）
  2. 枚举最小数 a，则另外两个数分别为 b = 2a，c = 3a
  3. 将 a、b、c 的每一位数字拆出来，共 9 个数字
  4. 检查这 9 个数字是否恰好是 1~9 各出现一次（用数组计数即可）

为什么这样枚举？

  • 如果比例是 1:2:3，那么设最小的数为 a，另外两个数就唯一确定了
  • 只需枚举 a，避免了复杂的全排列，时间复杂度从 O(9!) 降到了 O(329)

完整代码

C++

#include <iostream>
#include <array>

using namespace std;

// 检查三个数 a, b, c 的各位数字是否恰好包含 1~9 各一次
bool Check(int a, int b, int c) {
    array<int, 10> count{0};

    // 拆出 a 的每一位
    count[a / 100]++;
    count[a / 10 % 10]++;
    count[a % 10]++;

    // 拆出 b 的每一位
    count[b / 100]++;
    count[b / 10 % 10]++;
    count[b % 10]++;

    // 拆出 c 的每一位
    count[c / 100]++;
    count[c / 10 % 10]++;
    count[c % 10]++;

    // 检查 1~9 是否各出现一次，且不包含 0
    for (int i = 1; i <= 9; i++) {
        if (count[i] != 1) {
            return false;
        }
    }
    return true;
}

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

    // 枚举最小的数 a，范围是 123 ~ 329
    for (int a = 123; a <= 329; a++) {
        int b = a * 2;
        int c = a * 3;
        if (Check(a, b, c)) {
            cout << a << " " << b << " " << c << "\n";
        }
    }

    return 0;
}

关键代码讲解

数字拆解

count[a / 100]++;      // 百位数
count[a / 10 % 10]++;  // 十位数
count[a % 10]++;       // 个位数

用整除和取余操作拆出每一位数字，比转成字符串更高效。

范围为什么是 123~329？

  • 最小三位数的百位最小是 1，所以 a ≥ 123（三个数字不重复的最小三位数）
  • c = 3a 必须是三位数，所以 3a ≤ 987，即 a ≤ 329

复杂度分析

方法 时间复杂度 空间复杂度
枚举法 O(200) O(1)

实际上只需要循环约 200 次，每次检查 9 个数字，是非常高效的暴力解法。

易错点

  1. 数字不能包含 0：1~9 各用一次，不能出现数字 0，计数检查时要注意
  2. 输出顺序：按第一个数从小到大输出，题目要求的格式是 a b c（空格分隔）
  3. 边界范围：a 的上界是 329 不是 333，因为 333×3=999 但数字有重复

其他语言解法

Python

"""P1008 三连击 - Python 实现"""
from typing import List


def check(a: int, b: int, c: int) -> bool:
    """检查三个数的各位数字是否恰好包含 1~9 各一次"""
    count = [0] * 10

    for num in (a, b, c):
        count[num // 100] += 1
        count[num // 10 % 10] += 1
        count[num % 10] += 1

    for i in range(1, 10):
        if count[i] != 1:
            return False
    return True


def main() -> None:
    """枚举最小的数 a（范围 123~329），检查 2a 和 3a 是否满足条件"""
    results: List[str] = []
    for a in range(123, 330):
        b = a * 2
        c = a * 3
        if check(a, b, c):
            results.append(f"{a} {b} {c}")

    print("\n".join(results))


if __name__ == "__main__":
    main()

Java

import java.io.IOException;

public class Main {
    // 洛谷强制要求类名为 Main，且禁止使用 Scanner（MLE），使用 BufferedInputStream
    private static final byte[] buffer = new byte[1 << 16];
    private static int ptr = 0;
    private static int len = 0;

    private static int read() throws IOException {
        if (ptr >= len) {
            len = System.in.read(buffer);
            ptr = 0;
            if (len <= 0) return -1;
        }
        return buffer[ptr++];
    }

    private static boolean check(int a, int b, int c) {
        int[] count = new int[10];

        // 拆出 a 的每一位
        count[a / 100]++;
        count[a / 10 % 10]++;
        count[a % 10]++;

        // 拆出 b 的每一位
        count[b / 100]++;
        count[b / 10 % 10]++;
        count[b % 10]++;

        // 拆出 c 的每一位
        count[c / 100]++;
        count[c / 10 % 10]++;
        count[c % 10]++;

        // 检查 1~9 是否各出现一次
        for (int i = 1; i <= 9; i++) {
            if (count[i] != 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();

        // 枚举最小的数 a，范围是 123 ~ 329
        for (int a = 123; a <= 329; a++) {
            int b = a * 2;
            int c = a * 3;
            if (check(a, b, c)) {
                sb.append(a).append(" ").append(b).append(" ").append(c).append('\n');
            }
        }

        System.out.print(sb.toString());
    }
}

Go

package main

import (
    "fmt"
    "strings"
)

// check 检查三个数的各位数字是否恰好包含 1~9 各一次
func check(a, b, c int) bool {
    count := [10]int{0}

    // 拆出 a 的每一位
    count[a/100]++
    count[a/10%10]++
    count[a%10]++

    // 拆出 b 的每一位
    count[b/100]++
    count[b/10%10]++
    count[b%10]++

    // 拆出 c 的每一位
    count[c/100]++
    count[c/10%10]++
    count[c%10]++

    // 检查 1~9 是否各出现一次
    for i := 1; i <= 9; i++ {
        if count[i] != 1 {
            return false
        }
    }
    return true
}

func main() {
    var results []string

    // 枚举最小的数 a，范围是 123 ~ 329
    for a := 123; a <= 329; a++ {
        b := a * 2
        c := a * 3
        if check(a, b, c) {
            results = append(results, fmt.Sprintf("%d %d %d", a, b, c))
        }
    }

    fmt.Print(strings.Join(results, "\n"))
}

JavaScript

'use strict';

/**
 * 检查三个数的各位数字是否恰好包含 1~9 各一次
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @returns {boolean}
 */
function check(a, b, c) {
    /** @type {number[]} */
    const count = Array(10).fill(0);

    // 拆出 a 的每一位
    count[Math.floor(a / 100)]++;
    count[Math.floor(a / 10) % 10]++;
    count[a % 10]++;

    // 拆出 b 的每一位
    count[Math.floor(b / 100)]++;
    count[Math.floor(b / 10) % 10]++;
    count[b % 10]++;

    // 拆出 c 的每一位
    count[Math.floor(c / 100)]++;
    count[Math.floor(c / 10) % 10]++;
    count[c % 10]++;

    // 检查 1~9 是否各出现一次
    for (let i = 1; i <= 9; i++) {
        if (count[i] !== 1) {
            return false;
        }
    }
    return true;
}

/**
 * 主函数：枚举最小的数 a（范围 123~329），检查 2a 和 3a 是否满足条件
 */
function main() {
    const results = [];

    for (let a = 123; a <= 329; a++) {
        const b = a * 2;
        const c = a * 3;
        if (check(a, b, c)) {
            results.push(`${a} ${b} ${c}`);
        }
    }

    console.log(results.join('\n'));
}

main();

正确答案

本题共有 4 组解：

192 384 576
219 438 657
273 546 819
327 654 981