洛谷题单指南-暴力枚举-P1618 三连击（升级版）

原题链接：https://www.luogu.com.cn/problem/P1618

题意解读：枚举所有三位数的组合情况，判断是否符合比例。

解题思路：

方法一：枚举第一个数

根据题意，目的是寻找三个符合比例的三位数，可以直接枚举第一个，最小是123，最大是987

设第一个数为x，三个数的比例关系是a：b：c

设另外两个数为y，z

那么，根据比例关系，可以求得y = x * b / a，z = x * c / a （注意要判断a不能为0）

然后，只需要判断x，y，z三个数是否都是三位数，并且所有数字是否正好是1-9即可。

100分代码-枚举第一个数：

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

int h[10];

//提取x的每个数字到桶h
void getn(int x)
{
    while(x)
    {
        h[x % 10] = 1;
        x /= 10;
    }
}

//判断x、y、z是否都是三位数，且所有数字正好包含1-9
bool check(int x, int y, int z)
{
    memset(h, 0, sizeof(h));
    if(y > 999 || y < 100 || z > 999 || z < 100) return false;
    getn(x), getn(y), getn(z);
    for(int i = 1; i <= 9; i++)
    {
        if(h[i] == 0) return false;
    }
    return true;
}

int main()
{
    int a, b, c, x, y, z, cnt = 0;
    cin >> a >> b >> c;

    for(x = 123; x <= 987; x++) //枚举第一个三位数x
    {
        if(a == 0) continue; //除数不能为0
        y = x * b / a; //根据比例计算y
        z = x * c / a; //根据比例计算z
        if(check(x, y, z)) //判断x、y、z是否有效
        {
            cout << x << " " << y << " " << z << endl;
            cnt++;
        }
    }
    
    if(!cnt) cout << "No!!!";
}

方法二：枚举排列(DFS)

要枚举所有三位数的组合情况，根据题意，可以对1-9的数字进行全排列，然后将每3个数字组成一个整数，并由小到大排列，判断是否符合比例。

时间复杂度分析：

对1-9数字进行全排列，复杂度为9!，可以直接写段代码计算：

int ans = 1;
for(int i = 1; i <= 9; i++)
{
   ans *= i;
}
cout << ans; // 输出：362880

对每一组排列进行数字提取、3个数排序等操作，复杂度小于10，总体复杂度在百万级别，因此不会超时。

当找到一组排列，按照每三位数字组成一个整数，得到三个整数，由小到大排序；

再判断三个整数是否符合比例关系，如果要判断x、y、z三个数是否符合a：b：c，只需要判断x * b == y * a && y * c == z * b是否成立即可。

另外，需要注意，全排列组成的三位数中，会出现重复情况，如123/456/789和789/456/123三个数由小到大排序后是一样的，因此需要去重。

去重很显然要借助hash，可以将三个数拼接在一起，判断是否出现过即可，由于拼接后最长有9位数，如果用数组则要开10⁹的空间，可能爆内存，

而所有9个数的排列一共只有36万多，因此用map。

100分代码-DFS：

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

int tmp[10];
bool flag[10], yes;
int res[5];
map<int, int> h;

int a, b, c;

void dfs(int k)
{
    if(k == 10) //当找到一个排列
    {
        for(int i = 1; i <= 3; i++) //按照每三个数字组成一个整数，填入res数组
            res[i] = tmp[(i - 1) * 3 + 1] * 100 + tmp[(i - 1) * 3 + 2] * 10 + tmp[(i - 1) * 3 + 3];
        sort(res + 1, res + 4); //将三个整数排序
        if(res[1] * b == res[2] * a && res[2] * c == res[3] * b) //判断是否符合a:b:c
        {
            int value = res[1] * 1000000 + res[2] * 1000 + res[3];
            if(!h[value]) //判断三个数字是否已经出现过，因为排列会导致重复，如123,456,789和456,123,789是一样的
            {
                cout << res[1] << " " << res[2] << " " << res[3] << endl;
                yes = true; //yes=true说明找到了一组结果
                h[value] = 1;
            }
        }    
    }

    for(int i = 1; i <= 9; i++) // 枚举1-9的全排列
    {
        if(!flag[i])
        {
            flag[i] = true;
            tmp[k] = i; //数据存入tmp
            dfs(k + 1);
            flag[i] = false;
        }
    }
}

int main()
{
    cin >> a >> b >> c;
    dfs(1);
    if(!yes) cout << "No!!!";
}