跳到主要内容

三连击

信息

此题目来自 洛谷， 原始题目与提交代码请前往 P1008 [NOIP 1998 普及组] 三连击 - 洛谷。

题目背景​

本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。

题目描述​

将 1,2,…,91,2,\dots,9 共 99 个数分成 33 组，分别组成 33 个三位数，且使这 33 个三位数构成 1:2:31:2:3 的比例，试求出所有满足条件的 33 个三位数。

输入格式​

无

输出格式​

若干行，每行 33 个数字。按照每行第 11 个数字升序排列。

输入输出样例​

输出 #1

192 384 576
* * *
...

* * *
（剩余部分不予展示）

说明/提示​

NOIP1998 普及组 第一题

题目解答​

由于这是一道提交答案题，说明我们可以不考虑时间复杂度与空间复杂度来编写程序。 正常人谁会去手算。

很轻而易举的我们就可以发现，这其中的数字都是三位数 （这不废话吗）， 于是，每个数的取值范围都应为 111≤n≤999{111}\le{n}\le{999}。

又考虑到数字不会重复，那么取值范围应为 123≤n≤987{123}\le{n}\le{987}。 不过，我们也可以直接检查每一位数字看看有没有重复的就可以了。

假设这三个数字分别为 aa、bb、cc。 观察题目，不难发现 a:b:c=1:2:3a:b:c=1:2:3，即 b=2ab=2a，c=3ac=3a。 再由 123≤c≤987{123}\le{c}\le{987} 可得，123≤a≤329{123}\le{a}\le{329}。

那么我们遍历 a 变量即可。

/**
 * 洛谷 P1008 解答程序。
 * @author CoolCLK
 */

#include <iostream>
using namespace std;

/**
 * 检查是否有重复数字，使用贡献法。
 * @author CoolCLK
 */
bool checkDigits(int a, int b, int c) {
    int digits[10] = {0};
    int nums[] = {a, b, c};
    
    for (int num : nums) {
        while (num > 0) {
            int digit = num % 10;
            if (digit == 0 || digits[digit] > 0) {
                return false;
            }
            digits[digit]++;
            num /= 10;
        }
    }
    
    for (int i = 1; i <= 9; i++) {
        if (digits[i] != 1) {
            return false;
        }
    }
    return true;
}

/**
 * @author CoolCLK
 */
int main() {
    for (int a = 123; a <= 329; a++) {
        int b = 2 * a;
        int c = 3 * a;
        if (!checkDigits(a, b, c)) continue;
        cout << a << " " << b << " " << c << endl;
    }
    return 0;
}

结果：

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