【洛谷 P1618】三连击(升级版)题解(深度优先搜索+位集合)

简介: `三连击(升级版)` 是一道编程题,要求将数字 19 分成三组,构成三个三位数,其比例为 A:B:C。给定 A, B, C,程序应找到所有可能的组合并按首位升序输出。输入为 A, B, C,输出是满足比例的三位数或"No!!!"(当无解时)。解决方案涉及全排列搜索和比例验证。提供的AC代码使用C++,通过位集记录数字使用情况,递归实现全排列。

三连击(升级版)

题目描述

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

//感谢黄小U饮品完善题意

输入格式

三个数,A,B,C

输出格式

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

样例 #1

样例输入 #1

1 2 3
AI 代码解读

样例输出 #1

192 384 576
219 438 657
273 546 819
327 654 981
AI 代码解读

提示

保证 A<B<C


upd 2022.8.3:新增加二组 Hack 数据。

思路

搜索得到全排列,用乘法判断是否符合比例关系。

AC代码

#include <iostream>
#include <bitset>
#include <cmath>
#define AUTHOR "HEX9CF"
using namespace std;

int a, b, c;
int x, y, z;
bitset<15> bs;
int arr[15];
int flg;

void f()
{
   
    if (9 == bs.count())
    {
   
        a = 0;
        b = 0;
        c = 0;
        for (int i = 0; i < 3; i++)
        {
   
            a += arr[i + 1] * pow(10, 2 - i);
            b += arr[i + 4] * pow(10, 2 - i);
            c += arr[i + 7] * pow(10, 2 - i);
        }
        if ((a * y == b * x) && (a * z == c * x) && (b * z == c * y))
        {
   
            cout << a << " " << b << " " << c << endl;
            flg = 1;
        }
        return;
    }
    for (int i = 1; i <= 9; i++)
    {
   
        if (!bs[i])
        {
   
            bs[i] = 1;
            arr[bs.count()] = i;
            f();
            bs[i] = 0;
        }
    }
}

int main()
{
   
    bs.reset();
    cin >> x >> y >> z;
    f();
    if(!flg){
   
        cout << "No!!!" << endl;
    }
    return 0;
}
AI 代码解读
HEX9CF
+关注
目录
打赏
0
0
0
0
1
分享
相关文章
轻松入门MySQL:深入理解MySQL日志,二进制日志、中继日志、回滚日志和重做日志(19)
轻松入门MySQL:深入理解MySQL日志,二进制日志、中继日志、回滚日志和重做日志(19)
830 0
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
193 6
数据库五种基本运算
【5月更文挑战第15天】数据库的关系代数包括并、差、投影、笛卡尔积和选择等基本运算,以及交、连接、除、广义投影和外连接等扩展运算。在这些操作中,笛卡尔积通常最消耗资源,因为它会大幅增加元组数量和计算量。
1115 4
数据库五种基本运算
优雅的参数校验,告别冗余if-else
本文介绍了在 Java Spring Boot 开发中如何使用 JSR 303 和 Hibernate Validator 进行参数校验,以避免冗余的if-else判断。文章涵盖了基本注解的使用、全局异常处理、分组校验、嵌套对象校验、快速失败配置以及自定义校验规则等实用技巧。
124 10
优雅的参数校验,告别冗余if-else
【洛谷 P1618】三连击(升级版)题解(循环枚举+全排列)
该编程题目要求将数字1到9分为三组,形成三个三位数,使得这三个数成比例A:B:C。输入为A、B、C的值,输出符合条件的三位数组合,按首个数字升序排列。样例输入为1 2 3,输出多组解。代码使用全排列遍历数字,检查比例关系。若无解,则输出&quot;No!!!&quot;。
163 0
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
114 15
在Linux中,如何在Linux中安装和配置KVM?
在Linux中,如何在Linux中安装和配置KVM?
深度剖析 RocketMQ 5.0,消息基础:RocketMQ 在业务消息场景的基础优势是什么?
本文主要介绍业务消息的应用解耦场景,具体解耦什么? RocketMQ 在业务消息场景的基础特性。业界那么多消息队列能实现应用解耦,RocketMQ 在基础特性上有哪些增强?
125712 2
深度剖析 RocketMQ 5.0,消息基础:RocketMQ 在业务消息场景的基础优势是什么?
Elasticsearch 查询革新:探索 Wildcard 类型的高效模糊匹配策略
Elasticsearch 查询革新:探索 Wildcard 类型的高效模糊匹配策略
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问