【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)
目录
写在前面:
题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述:
输入格式:
输出格式:
输入样例:
输出样例:
解题思路:
代码:
AC !!!!!!!!!!
写在最后:
写在前面:
怎么样才能学好一个算法?
我个人认为,系统性的刷题尤为重要,
所以,为了学好深度优先搜索,为了用好暴搜应对蓝桥杯,
事不宜迟,我们即刻开始刷题!
题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述:

输入格式:
一个整数 n ( 1 ≤ n ≤ 24 )。
输出格式:
一个整数,能拼成的不同等式的数目。
输入样例:
1.
14
2.
18
输出样例:
1.
2
2.
9
解题思路:
我们使用深度优先搜索的时候,
第一个要注意的点是搜索的顺序,
因为我们要保证,
我们写出的递归结构能够遍历所有情况,
在我们初学搜索的时候,我们一定要画一个递归搜索树观察,
递归非常抽象,画图能很好的帮助我们解题。(以上递归搜索的基本思路,多熟悉总是好的)
接下来是具体思路:
根据题意可知:

这样,我们可以把它想象成,
在ABC这三个位置上填数字,
满足A+B=C以及A+B+C的火柴数等于n-4,
那我们根据这个思路来画递归搜索数:
根节点:

往第一个位置填数字:
继续往下递归搜索,
我们发现其实这是一个指数型的枚举:
我们继续往下搜索:

以此类推,我们能够搜索出所有的情况,
然后再根据题意进行判断和剪枝:
剪枝:
如果A或者A+B的火柴数已经大于题目要求的n,
就直接return,也就是剪枝。
接下来看代码:
代码:
//包常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;//题目n最大是24,如果不确定该开多大,那就开大点
const int N = 10010;int n;//计数最后输出
int res = 0;int st[N];//各个数字的火柴数
int match[10010] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };void dfs(int u, int sum)
{//如果A或者A+B的火柴数已经大于题目要求的n,剪枝if(sum > n)return;if (u > 3){//满足A+B=C以及A+B+C的火柴数等于n-4if (st[1] + st[2] == st[3] && sum == n - 4){res++;}return;}//搜索for (int i = 0; i < 1000; i++){st[u] = i;dfs(u + 1, sum + match[i]);st[u] = 0;}
}int main()
{scanf("%d", &n);//递推取得每个数字的火柴数for(int i = 10; i < 1000; i++){match[i] = match[i / 10] + match[i % 10];}dfs(1, 0);printf("%d", res);return 0;
}
AC !!!!!!!!!!

写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)
目录 写在前面: 题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: …...
在Win10以及SDK为33的环境下——小米便签项目的搭建
文章目录0. 我的操作系统和开发环境1. 相关文件下载:2. import project:2.1 用import project导入项目3. make project:3.1 AS中的命令行乱码问题:3.2 依赖库缺失问题:3.3 关于targetSdkVersion3.4 关于Missing URL3.5 关于Manifest merger f…...
FPGA纯verilog实现RIFFA的PCIE通信,提供工程源码和软件驱动
目录1、前言2、RIFFA简介RIFFA概述RIFFA架构RIFFA驱动3、vivado工程详解4、上板调试验证并演示5、福利:工程代码的获取1、前言 PCIE是目前速率很高的外部板卡与CPU通信的方案之一,广泛应用于电脑主板与外部板卡的通讯,PCIE协议极其复杂&…...
Linux网络配置
文章目录一、Linux网络配置原理图二、查看网络IP和网关ping测试主机之间网络连通性三、linux网络环境配置第一种方法(自动获取)第二种方法(指定ip)四、设置主机名和hosts映射设置主机名设置hosts映射五、主机名解析过程分析(Hosts、DNS)Hosts是什么DNS一、Linux网络配置原理图 …...
【Java学习笔记】多线程与线程池
多线程与线程池一、多线程安全与应用1、程序、进程与线程的关系2、创建多线程的三种方式(1)继承Thread类创建线程【不推荐】(2)实现Runnable接口创建线程(3)Callable接口创建线程3、线程的生命周期4、初识线…...
尺取法
尺取法是一种线性的高效率算法。记 (L, R ) 为一个序列内以L为起点的最短合法区间, 如果R随L的增大而增大的,就可以使用尺取法。具体的做法是不断的枚举 L,同时求出R。 因为 R 随 L增大而增大,所以总时间复杂度为 O(n) 指针i、j的两种方向: 反向扫描:i、j方向相反,i从头…...
20.有效的括号
给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括…...
使用QT C++编写一个带有菜单和工具条的文本编辑器
您好,这是必应。我可以帮您生成一段使用QT C编写一个带有菜单和工具条的文本编辑器的代码,但是请注意,这只是我的创造性的输出,并不代表任何权威或专业的观点。如果您想要了解更多的相关知识,请自行搜索或咨询专家。以…...
文法和语言的基本知识
一、什么形式化的方法用一套带有严格规定的符号体系来描述问题的方法二、什么是非形式化的方法对程序设计语言的描述从语法、语义和语用三个方面因素来考虑所谓语法是对语言结构定义所谓语义是描述了语言的含义所谓语用则是从使用的角度去描述语言三、符号串字母表和符号串字母…...
学习其他人的代码,成为更好的程序员
学习其他人的代码,成为更好的程序员1. 广泛阅读2. 分析代码3. 记笔记4. 实验5. 分享你的发现6. 结论参考如何成为一名更好的Python程序员??? 学习编码是一个持续的过程,需要实践、实验和向他人学习的意愿。提高编码技能的最佳方法之一是学习他人的代…...
新星计划-JAVA学习路线及书籍推荐
CSDN的各位友友们你们好,今天千泽为大家带来的是JAVA学习路线及其经典书籍推荐,接下来让我们一起了解一下JAVA的学习路线吧!如果对您有帮助的话希望能够得到您的支持和关注,我会持续更新的! 目录 1.JAVASE及其书籍推荐 2.初级数据结构与算法及其书籍推荐 3.MySQL及其书籍推荐…...
【大数据】Hive系列之- Hive-DML 数据操作
Hive系列-DML 数据操作数据导入向表中装载数据(Load)语法操作用例通过查询语句向表中插入数据(Insert)创建一张表插入数据基本模式插入(根据单张表查询结果)查询语句中创建表并加载数据(As Sele…...
day2 —— 判断字符串中的字符是否唯一
目录 前言 问题描述 代码解释 前言 若是想要了解基本语法的话,请到(7条消息) C语言从练气期到渡劫期_要一杯卡布奇诺的博客-CSDN博客查看相应的语法细节 强烈安利这篇文章 —— (4条消息) 筑基五层 —— 位运算看这篇就行了_要一杯卡布奇诺的博客-CSDN博客 问题…...
176万,GPT-4发布了,如何查看OpenAI的下载量?
大家好,这里是程序员晚枫。 昨天新一代GPT4发布了,今年GPT不断给大家带来惊喜。 在OpenAI的官网,也公开了GPT的Python调用第三方库:openai。 今天我们就来看看,这个Python智能接口~ 1、代码说明 开发过Python项目…...
蓝蓝算法题(一)
讲在前面:1.本人正在逐步学习C,代码中难免有C和C(向下兼容)混用情况。2.算法题目来自蓝蓝知识星球,没有对应的判决系统,运行到判决系统可以会有部分案例不能通过。 求素数 暴力求解(1 - n试探…...
Python截图自动化工具
1、展示部分源码(写的比较乱,哈哈) 2、功能展示 1)首页 2)按钮截图(用于自动翻页) 3)保存位置按钮(选择图片保存的位置) 4)重复次数,就是要截取多少次 5)定位截屏(截取的内容&#x…...
网络作业2【计算机网络】
网络作业2【计算机网络】前言推荐网络作业2一. 单选题(共3题,19.8分)二. 多选题(共1题,6.6分)三. 填空题(共8题,52.8分)四. 判断题(共3题,20.8分&…...
如何给网页加速,如何加速网页速度?
如何加速网页速度?提高移动网页加载的速度,可以从服务器的优化、网页的容量、请求响应等方面入手,这些方面优化后必然可以提高加载速度。1、服务器硬件软件配置要好,网络、读写响应等要做好优化。2、可以开启gzip压缩技术…...
linux kernel 5.0 inline hook框架
github:https://github.com/WeiJiLab/kernel-hook-framework 一、项目介绍 Usually we want to hack a kernel function, to insert customized code before or after a certain kernel function been called, or to totally replace a function with new one. How can we…...
【Java版oj】day12二进制插入、查找组成一个偶数最接近的两个素数
目录 一、二进制插入 (1)原题再现 (2)问题分析 (3)完整代码 二、查找组成一个偶数最接近的两个素数 (1)原题再现 (2)问题分析 (3࿰…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
