【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（4）
创始人
2025-05-30 15:02:12

目录

写在前面：

题目：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 
#include 
#include 
#include 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 ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Gocator 3D线扫相机专业名称解释说明

下一篇：飞碟Q2V飞碟Q2V最新报价-图片-参数（飞碟20） 飞碟Q2V评测 飞碟q2v最新报价

相关内容

热门资讯

SpringMVC-前后台协议... SpringMVC-前后台协议联调 4，前后台协议联调 4.1 环境准备 创建一个We...
【C语言】你真的了解结构体吗 引言✨我们知道C语言中存在着整形(int、short...)，字符型(char)&#x...
一人一世界一叶一菩提什么意思,... 一人一世界一叶一菩提什么意思目录一人一世界一叶一菩提什么意思一花一世界,一叶一菩提的意思是什么？佛家...
国家的含义是什么 极速百科网 ... 国家的含义是什么目录国家的含义是什么国家的含义是什么对国家最本质的解释是什么？国家的含义是什么？国家...
如何用word制作宣传单,wo... 如何用word制作宣传单目录如何用word制作宣传单word业务传单在哪如何利用word排版制作广告...
怎么练习穿高跟鞋,很多女生穿不... 怎么练习穿高跟鞋目录怎么练习穿高跟鞋很多女生穿不惯高跟鞋，该如何舒适的驾驭高跟鞋呢？请问一下..怎么...
linux交换分区和逻辑卷 交换分区 查看交换分区： [root@localhost ~]# free ...
AGV小车的运动是怎么控制的呢... 随着市场的竞争加剧，有一家位于城市中心的酒店开始引入一些新的科技设备来提高服务水平&#...
火车票开售时间,火车票早上几点... 今天给各位分享火车票开售时间,火车票早上几点开售的知识，其中也会对火车票预订早上几点开始发售进行解释...
康熙容妃历史原型 极速百科网 ... 康熙容妃历史原型目录康熙容妃历史原型康熙容妃历史原型康熙大帝里面的容妃是历史上的真人真事吗？死后被追...
怎么鉴别镀银和纯银,纯银和镀银... 怎么鉴别镀银和纯银目录怎么鉴别镀银和纯银纯银和镀银怎么区别怎么能看出是纯银还是镀银如何鉴别银饰物品是...
麻辣烫的菜单有哪些,麻辣烫的菜... 麻辣烫的菜单有哪些目录麻辣烫的菜单有哪些麻辣烫的菜单麻辣烫的菜品有哪些？麻辣烫菜单(尽享中国特色小吃...
dhtmlx.Gantt 8.... 最新消息 如果您的当前版本的 dhtmlxGantt 早于 2.0，请查看从旧版本迁...
docker版jxTMS使用指... 本文讲解docker版jxTMS的数据查询，整个系列的文章请查看：doc...
Class文件解析 目录 Class文件格式总览 常量池(Constant Pool) 数据类型描述规则 成员变量描述规...
瑞士是什么之国,瑞士是什么之国... 瑞士是什么之国目录瑞士是什么之国瑞士是什么之国?意大利,加拿大,日本,瑞士,泰国的别称是什么？瑞士是...
带坏字的成语,带“坏”字的成语... 带坏字的成语目录带坏字的成语带“坏”字的成语有哪些？表示坏的成语？坏字开头的成语带坏字的成语 ...
伤痕累累怎么读,伤痕累累的拼音... 伤痕累累怎么读目录伤痕累累怎么读伤痕累累的拼音是什么伤痕累累的意思伤痕累累的累发什么音?伤痕累累怎么...
随车电话的咨询方法（随车电话是... 本篇文章极速百科给大家谈谈随车电话的咨询方法，以及随车电话是什么意思对应的知识点，希望对各位有所帮助...
九九乘法表-第14届蓝桥杯ST...  [导读]：超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成࿰...
DS1307 RTC模块使用 主要特性DS1307是Maxim的串行、I2C实时时钟芯片。主要特性有：工作电压&#x...
Vue学习之Vue的生命周期详... Vue学习之Vue的生命周期详细解释概览详细解释每个生命周期的应用beforeCreate(创建前)...
手机键盘输入法怎么设置,手机输... 方法一： 2. 找到并点击“系统设置”。 3. 在“系统设置”中，点击“键盘与输入法”。...
水泥由什么组成,水泥组成材料有... 水泥由什么组成目录水泥由什么组成水泥组成材料有哪些水泥的主要成份是什么？它是用什么做的？水泥的主要成...
一个银行卡可以绑几个微信,银行... 一个银行卡可以绑几个微信目录一个银行卡可以绑几个微信银行卡能绑定几个微信号一张银行卡可以绑几个微信一...
表结构是什么（表结构是啥） 表... 本篇文章极速百科给大家谈谈表结构是什么，以及表结构是啥对应的知识点，希望对各位有所帮助，不要忘了收藏...
微信小程序实现多语言方案|中英... 不管哪个系统，多语言方案套路都是一样的 1、建立多语言映射库 2、记录并存储用户选...
管理技术债 管理技术债 Philippe Kruchten, Robert Nord, Ipek Ozkaya ...
Matlab中exp(x)函数... 目录1.语法2.说明3.示例e的数字表示形式欧拉恒等式为指数函数绘图4.参考来源： 1...
拯救会议纪要！快用这三个音频转... Hello，大家好，我是指尖科技君~不知道小伙伴们平时有录音的习惯吗&#...