洛谷 三连击
内容纲要

三连击(升级版)

题目描述

将 1, 2,..., 9 共 9 个数分成三组,分别组成三个三位数,且使这三个三位数的比例是 A:B:C,试求出所有满足条件的三个三位数,若无解,输出 No!!!

输入格式

三个数,A,B,C。

输出格式

若干行,每行 3 个数字。按照每行第一个数字升序排列。

样例 #1

样例输入 #1

1 2 3

样例输出 #1

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

提示

保证 A<B<C。

暴力枚举法:

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

int flag = 0;
int k1 = 0, k2 = 0, k3 = 0;
int a, b, c;
int main()
{
    cin >> a >> b >> c;
    for (int a1 = 1; a1 < 10; a1++)
    {
        for (int a2 = 1; a2 < 10; a2++)
        {
            if (a2 != a1)
            {
                for (int a3 = 1; a3 < 10; a3++)
                {
                    if (a3 != a1 && a3 != a2)
                    {
                        for (int a4 = 1; a4 < 10; a4++)
                        {
                            if (a4 != a1 && a4 != a2 && a4 != a3)
                            {
                                for (int a5 = 1; a5 < 10; a5++)
                                {
                                    if (a5 != a1 && a5 != a2 && a5 != a3 && a5 != a4)
                                    {
                                        for (int a6 = 1; a6 < 10; a6++)
                                        {
                                            if (a6 != a1 && a6 != a2 && a6 != a3 && a6 != a4 && a6 != a5)
                                            {
                                                for (int a7 = 1; a7 < 10; a7++)
                                                {
                                                    if (a7 != a1 && a7 != a2 && a7 != a3 && a7 != a4 && a7 != a5 && a7 != a6)
                                                    {
                                                        for (int a8 = 1; a8 < 10; a8++)
                                                        {
                                                            if (a8 != a1 && a8 != a2 && a8 != a3 && a8 != a4 && a8 != a5 && a8 != a6 && a8 != a7)
                                                            {
                                                                for (int a9 = 1; a9 < 10; a9++)
                                                                {
                                                                    if (a9 != a1 && a9 != a2 && a9 != a3 && a9 != a4 && a9 != a5 && a9 != a6 && a9 != a7 && a9 != a8)
                                                                    {

                                                                        k1 = a1 * 100 + a2 * 10 + a3;
                                                                        k2 = a4 * 100 + a5 * 10 + a6;
                                                                        k3 = a7 * 100 + a8 * 10 + a9;
                                                                        if (k1 * b == k2 * a && k3 * a == k1 * c)
                                                                        {
                                                                            cout << k1 << " " << k2 << " " << k3 << endl;
                                                                            flag = 1;
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if (flag == 0)
        cout << "No!!!";
    return 0;
}

暴力递归法:

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

vector<int> num(10, 0);
int flag = 0;
int k1 = 0, k2 = 0, k3 = 0;
int a, b, c;

void DFS(int x)
{
    if (x == 9)//递归结束条件
    {
        if (k1 * b == k2 * a && k3 * a == k1 * c)
        {
            cout << k1 << " " << k2 << " " << k3 << endl;
            flag = 1;//找到解
            return;
        }
    }
    for (int i = 1; i < 10; i++)
    {
        if(num[i] == 0)//判断是否已经使用过
        {
            num[i] = 1;
            if (x < 3)//构造第一个数的百位、十位、个位
                k1 = k1 * 10 + i;
            else if(x < 6)//构造第二个数的百位、十位、个位
                k2 = k2 * 10 + i;
            else if(x < 9)//构造第三个数的百位、十位、个位
                k3 = k3 * 10 + i;
            DFS(x + 1);//递归
            //在递归结束后,将当前的数值恢复到上一层的状态
            //这样才能继续构造下一个数
            //因为回溯是从最后一个数个位开始的,所以结果是依次增大
            if (x < 3)
                k1 = k1 / 10;
            else if (x < 6)
                k2 = k2 / 10;
            else if (x < 9)
                k3 = k3 / 10;
            num[i] = 0;
        }

    }

}

int main()
{
    cin >> a >> b >> c;
    DFS(0);
    if(flag == 0)
        cout << "No!!!";

    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇