洛谷刷题 P1008 [NOIP1998 普及组] 三连击

题目链接：P1008 [NOIP1998 普及组] 三连击

思路

此题主要采取枚举的思想，但是直接暴力枚举会导致时间不够，因此我们先进行分析

因为要求三个三位数构成的比例是1：2：3，因此最小的那个数的百位只能在1、2、3选择，这样大大缩小了枚举范围，因此我们可以通过对最小数字的枚举

AC代码

#include<iostream>
using namespace std;

bool check(int a, int b, int c)
{
    if (b >= 1000 || c >= 1000) return false;
    bool list[10]={0}; // 记录数字是否被使用
    // 分别对a，b，c的各位数字进行记录
    for (int i = 0; i < 3; i++) 
    {
        list[a%10] = 1;
        a /= 10;
    }
    for (int i = 0; i < 3; i++)
    {   
        if (list[b%10]) return false; // 判断是否有重复数字
        list[b%10] = 1;
        b /= 10;
    }
    for (int i = 0; i < 3; i++)
    {
        if (list[c%10]) return false; // 判断是否有重复数字
        list[c%10] = 1;
        c /= 10;    
    }
    if (list[0]) return false; // 判断是否有0
    return true;
}
int main()
{
    for (int i = 1; i <= 3; i++) // 确定最小数的百位
    {
        int a = i*100;
        for (int j = 1; j < 10; j++) // 确定最小数十位
        {
            if ( i == j ) 
            {
                continue;
            }
            a += j*10;
            for (int k = 1; k < 10; k++) // 确定最小数个位
            {
                if ( i == k || j == k ) 
                {
                    continue;
                }
                a += k;
                if (check(a, a*2, a*3)) // 判断是否满足条件
                {
                    cout << a << " " << a*2 << " " << a*3 << endl;
                }
                a -= k; // 回溯
            }
            a -= j*10; // 回溯
        }
    }
    return 0;
}