jjzjj

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（10）

戊子仲秋 2023-06-10 原文

目录

写在前面：

题目：P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输入的第一行为一个单独的整数 n 表示单词数，

以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出格式：

只需输出以此字母开头的最长的“龙”的长度。

输入样例：

5
at
touch
cheat
choose
tact
a

输出样例：

23

解题思路：

我们使用深度优先搜索的时候，

第一个要注意的点是搜索的顺序，

因为我们要保证，

我们写出的递归结构能够遍历所有情况。

（以上递归搜索的基本思路，多熟悉总是好的）

 接下来是具体思路：

根据题意，我们需要解决一些问题：

1. 怎样记录每个单词的使用个数

可以开一个数组来记录，小问题，

2. 怎样判断一个单词能接到另一个单词上？

到时候我们具体情况具体分析，

3. 如何遍历所有情况？

以题目的例子为例：

这个是根据这样的规律往下搜索的：

 单词两两拼接，

 下面是代码实现：

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int N = 30;

int n;

//接收字母
string arr[N];

//计算字母用了几次
int used[N];

//龙
char head;

//第i个单词是否能接到第j个单词后面，g[i][j]的值存的是他们重合的长度
int g[N][N];

//计算最长的字符串
int res;

void dfs(string dragon, int x)
{
    res = max(res, (int)dragon.size());
    
    used[x]++;//计算单词使用次数
    for(int i = 0; i < n; i++)
    {
        //如果能拼接，且该单词使用次数<2
        if(g[x][i] && used[i] < 2)
        {
            //减去重复部分并拼接
            dfs(dragon + arr[i].substr(g[x][i]), i);
        }
    }
    used[x]--;//恢复现场
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    cin >> head;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            //第i个单词        第j个单词
            string a = arr[i], b = arr[j];
            for(int k = 1; k < min(a.size(), b.size()); k++)
            {
                //如果能接到后面，就记录下来
                if(a.substr(a.size() - k, k) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
            }
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        //从第一个字母是龙的单词开始
        if(arr[i][0] == head)
        {
            dfs(arr[i], i);
        }
    }
    
    printf("%d", res);
    return 0;
}

AC ！！！！！！！！！！

写在最后：

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

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

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

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

蓝桥dfsxffBCxff0c蓝桥杯深度优先算法

有关【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（10）的更多相关文章

  1. 深度学习部署：Windows安装pycocotools报错解决方法 - 2

    深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal

  2. 由于 libgmp.10.dylib 的问题，Ruby 2.2.0 无法运行 - 2

    我刚刚安装了带有RVM的Ruby2.2.0，并尝试使用它得到了这个:$rvmuse2.2.0--defaultUsing/Users/brandon/.rvm/gems/ruby-2.2.0dyld:Librarynotloaded:/usr/local/lib/libgmp.10.dylibReferencedfrom:/Users/brandon/.rvm/rubies/ruby-2.2.0/bin/rubyReason:Incompatiblelibraryversion:rubyrequiresversion13.0.0orlater,butlibgmp.10.dylibpro

  3. ruby - ri 有空文件 – Ubuntu 11.10, Ruby 1.9 - 2

    我正在运行Ubuntu11.10并像这样安装Ruby1.9:$sudoapt-getinstallruby1.9rubygems一切都运行良好，但ri似乎有空文档。ri告诉我文档是空的，我必须安装它们。我执行此操作是因为我读到它会有所帮助:$rdoc--all--ri现在，当我尝试打开任何文档时:$riArrayNothingknownaboutArray我搜索的其他所有内容都是一样的。 最佳答案 这个呢？apt-getinstallri1.8编辑或者试试这个:(非rvm)geminstallrdocrdoc-datardoc-da

  4. ruby-on-rails - gem install rmagick -v 2.13.1 错误 Failed to build gem native extension on Mac OS 10.9.1 - 2

    我已经通过提供MagickWand.h的路径尝试了一切，我安装了命令工具。谁能帮帮我？$geminstallrmagick-v2.13.1Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingrmagick:ERROR:Failedtobuildgemnativeextension./Users/ghazanfarali/.rvm/rubies/ruby-1.8.7-p357/bin/rubyextconf.rbcheckingforRubyversion>=1.8.5...yescheckingfor/

  5. ruby - 安装 tiny_tds 在 mac os 10.10.5 上出现错误 - 2

    我正在使用macos，我想使用ruby​​驱动程序连接到sqlserver。我想使用tiny_tds，但它给出了缺少free_tds的错误，但它已经安装了。怎么能过这个？~brewinstallfreetdsWarning:freetds-0.91.112alreadyinstalled~sudogeminstalltiny_tdsBuildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingtiny_tds:ERROR:Failedtobuildgemnativeextension.完整日志如下:/System

  6. ruby - rails 3.2.2(或 3.2.1)+ Postgresql 9.1.3 + Ubuntu 11.10 连接错误 - 2

    我正在使用PostgreSQL9.1.3(x86_64-pc-linux-gnu上的PostgreSQL9.1.3，由gcc-4.6.real(Ubuntu/Linaro4.6.1-9ubuntu3)4.6.1，64位编译)和在ubuntu11.10上运行3.2.2或3.2.1。现在，我可以使用以下命令连接PostgreSQLsupostgres输入密码我可以看到postgres=#我将以下详细信息放在我的config/database.yml中并执行“railsdb”，它工作正常。开发:adapter:postgresqlencoding:utf8reconnect:falsedat

  7. ruby-on-rails - 在 osx 10.9.3 上使用 RVM 安装 ruby​​-1.9.3-p547 时出错 - 2

    如何解决这个错误:$rvminstall1.9.3Searchingforbinaryrubies,thismighttakesometime.Nobinaryrubiesavailablefor:osx/10.9/x86_64/ruby-1.9.3-p547.Continuingwithcompilation.Pleaseread'rvmhelpmount'togetmoreinformationonbinaryrubies.Checkingrequirementsforosx.Certificatesin'/usr/local/etc/openssl/cert.pem'arealr

  8. 深度学习12. CNN经典网络 VGG16 - 2

    深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG

  9. u盘安装系统(win10为例) - 2

    下载微PE工具箱进入官网下载微PE工具箱-下载 安装好后,打开微PE工具箱客户端,选择安装PE到U盘 PE壁纸可选择自己喜欢的壁纸,勾选上包含DOS工具箱,个性化盘符图标 下载原版系统进入网站下载镜像NEXT,ITELLYOU如果没有账号,注册一下就好进入选择开始使用选择win10 这里我们选择消费者版,用迅雷把BT种子下载下来 下面的两个盘符,是PE工具箱安装进U盘后,分成的盘符,注意EFI的盘符,这里面不能删东西,也不能添东西,另一个盘符可以当做正常的U盘空间使用,我们现在需要把下载下来的景象文件复制到正常的U盘空间中去 这个时候我们的系统U盘就只做好了 安装系统我们将U盘插入电脑,开机,

  10. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

随机推荐